Художник Тюбик учит Незнайку рисовать. Он дал ему сетку с H строками и W столбцами. Все клетки сетки изначально выкрашены в белый цвет. Тюбик попросил Незнайку закрасить N из этих ячеек в черный цвет. I-я (1<=i<=N) ячейка, которую закрасил Незнайка, является ячейкой в a
i-й строке и b
i -м столбце. Для каждого целого числа j (0<=j<=9), определите сколько в сетке подпрямоугольников размером 3×3 содержит ровно j черных ячеек после того, как Незнайка закрасил N ячеек?
Входные данные
В первой строке заданы 3 целых числа: H, W (3<=H,W<=10
9) и N (0<=N<=min(10
5,H×W)). Далее идут N строк по 2 числа в каждом a
i (1<=a
i<=H) и b
i (1<=b
i<=W), 1<=i<=N, (a
i,b
i)≠(a
j,b
j), i ≠ j.
Выходные данные
Выведите 10 строк. В (j + 1)-й (0<=j<=9) строке должно быть указано количество подпрямоугольников размером 3 × 3 сетки, содержащей ровно j черных ячеек.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4 5 8
1 1
1 4
1 5
2 3
3 1
3 2
3 4
4 4 |
0
0
0
2
4
0
0
0
0
0 |
| 2 |
10 10 20
1 1
1 4
1 9
2 5
3 10
4 2
4 7
5 9
6 4
6 6
6 7
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 |