Snuke's Coloring

AtCoder
IDarc061_b
Time3000ms
Memory256MB
Difficulty
We have a grid with $H$ rows and $W$ columns. At first, all cells were painted white. Snuke painted $N$ of these cells. The $i$\-th ( $1 \leq i \leq N$ ) cell he painted is the cell at the $a_i$\-th row and $b_i$\-th column. Compute the following: * For each integer $j$ ( $0 \leq j \leq 9$ ), how many subrectangles of size $3×3$ of the grid contains exactly $j$ black cells, after Snuke painted $N$ cells? ## Constraints * $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)$ ## Input The input is given from Standard Input in the following format: $H$ $W$ $N$ $a_1$ $b_1$ : $a_N$ $b_N$ [samples]
Samples
Input #1
4 5 8
1 1
1 4
1 5
2 3
3 1
3 2
3 4
4 4
Output #1
0
0
0
2
4
0
0
0
0
0

![image](https://atcoder.jp/img/arc061/30326702be007759dce81231012a8353.png)
There are six subrectangles of size $3×3$. Two of them contain three black cells each, and the remaining four contain four black cells each.
Input #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
Output #2
4
26
22
10
2
0
0
0
0
0
Input #3
1000000000 1000000000 0
Output #3
999999996000000004
0
0
0
0
0
0
0
0
0
API Response (JSON)
{
  "problem": {
    "name": "Snuke's Coloring",
    "description": {
      "content": "We have a grid with $H$ rows and $W$ columns. At first, all cells were painted white. Snuke painted $N$ of these cells. The $i$\\-th ( $1 \\leq i \\leq N$ ) cell he painted is the cell at the $a_i$\\-th r",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc061_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "We have a grid with $H$ rows and $W$ columns. At first, all cells were painted white.\nSnuke painted $N$ of these cells. The $i$\\-th ( $1 \\leq i \\leq N$ ) cell he painted is the cell at the $a_i$\\-th r...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments