Hide

Problem A
Cinema Seating

The United Cinema Crowd Association of Stockholm plans to have a showing of Old computer scientists and their pieings at the local KTH Royal Institute of Technology cinema. They have received bookings from $N$ computer scientists to attend the showing. The cinema itself is a grid of seats with dimensions $R \times C$.

Not until far too late did the auditor of the association point out to the board that computer scientists are stereotypically introverted. They might even go so far as to leave the showing if they have too many people sitting nearby!

For a given person, the number of adjacent seats to them are the 8 seats which are located at most a single row or column away from the person. Your task is to compute how many people have $k$ adjacent occupied seats, for every $k$.

Input

The first line of the input contains the integers $R$ ($1 \le R \le 1000$) and $C$ ($1 \le C \le 1000$), the number of rows and columns of seats in the cinema.

The next line contains the integer $N$ ($0 \le N \le 1\, 000\, 000$), the number of people who have booked a seat at the cinema. The next $N$ lines each contains two integers $r$ ($1 \le r \le R$) and $c$ ($1 \le c \le C$), meaning that someone have booked the seat on row $r$ and column $c$.

No two bookings will be for the same seat.

Output

Output $9$ integers – the number of people who have exactly $k$ adjacent occupied seats, for $k = 0, 1, \dots , 8$.

Explanation of the sample

In the first example, the cinema is a fully occupied $3 \times 3$ grid. This means that the four people sitting in the corners have three adjacent occupied seats, the four people sitting on the sides have five adjacent occupied seats, and the person in the middle has eight adjacent occupied seats.

In the second example, the situation is similar, except there is nobody in the middle. Thus, the people in the corners only have two adjacent occupied seats now, and the people on the sides have four adjacent occupied seats.

Sample Input 1 Sample Output 1
3 3
9
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
0 0 0 4 0 4 0 0 1
Sample Input 2 Sample Output 2
3 3
8
1 1
1 2
1 3
2 1
2 3
3 1
3 2
3 3
0 0 4 0 4 0 0 0 0

Please log in to submit a solution to this problem

Log in