The artist Tubik teaches Dunno to draw. He gave him a grid with H rows and W columns. All grid cells are initially painted white. Tube asked Dunno to color N of these cells black. The i-th (1<=i<=N) cell that Dunno filled in is the cell in the a
i-th row and b
i-th column. For each integer j (0<=j<=9), determine how many 3×3 subrectangles in the grid contain exactly j black cells after Dunno has filled in N cells?
Input
The first line contains 3 integers: H, W (3<=H,W<=10
9) and N (0<=N<=min(10
5 ,H×W)). Next come N lines of 2 numbers each a
i (1<=a
i<=H) and b
i (1< ;=b
i<=W), 1<=i<=N, (a
i,b
i) ≠(a
j,b
j), i ≠ j.
Imprint
Output 10 lines. The (j + 1)th (0<=j<=9) line must contain the number of sub-rectangles of size 3 × 3 grid containing exactly j black cells.
Examples
# |
Input |
Output |
1 |
4 5 8
1 1
14
15
23
3 1
3 2
34
4 4 |
0
0
0
2
4
0
0
0
0
0 |
2 |
10 10 20
1 1
14
19
25
3 10
4 2
47
5 9
6 4
66
67
7 1
7 3
7 7
8 1
8 5
8 10
9 2
10 4
10 9
| 4
26
22
10
2
0
0
0
0
0 |
3 |
1000000000 1000000000 0 |
999999996000000004
0
0
0
0
0
0
0
0
0 |