← 返回题目列表

AtCoder · arc061_b

D. Snuke 的着色

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

我们有一个网格 H 行和 W 列。起初,所有细胞都被漆成白色。

蛇核涂装 这些细胞的 N 。 i-th ( 1 \leq i \leq N ) 他画的单元格是位于 a_i第行和 b_i第列。

计算以下内容:

  • 对于每个整数 j ( 0 \leq j \leq 9 ),有多少个大小的子矩形 网格的 3×3 恰好包含 j 黑色单元格,Snuke 绘制后 N 细胞?

约束

  • 3 \leq H \leq 10^9
  • 3 \leq W \leq 10^9
  • 0 \leq N \leq min(10^5,H×W)
  • 1 \leq a_i \leq H (1 \leq i \leq N)
  • 1 \leq b_i \leq W (1 \leq i \leq N)
  • (a_i, b_i) \neq (a_j, b_j) (i \neq j)

输入

输入由标准输入按以下格式给出:

H W N
a_1 b_1
:
a_N b_N

输出

打印 10 行。 的 (j+1)-th ( 0 \leq j \leq 9 )行应包含大小的子矩形的数量 3×3 的网格恰好包含 j 黑色细胞。


示例输入 1

4 5 8
1 1
1 4
1 5
2 3
3 1
3 2
3 4
4 4

示例输出 1

0
0
0
2
4
0
0
0
0
0

有六个大小的子矩形 3×3。其中两个每个包含三个黑色单元,其余四个每个包含四个黑色单元。


示例输入 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

示例输出 2

4
26
22
10
2
0
0
0
0
0

示例输入 3

1000000000 1000000000 0

示例输出 3

999999996000000004
0
0
0
0
0
0
0
0
0