Under construction

Still being built. Things may change

Coloring Practice

Time limit1sMemory limit512 MB

Summary
Count how many 3x3 subgrids contain exactly i black cells for each i from 0 to 9, given up to 1e5 black cells on a huge grid.
Level

Medium6 of 10

Topics
Prefix sum, Hash map, Implementation, Combinatorics
Solved
No attempts yet

Problem

There is a grid of size H×WH \times W, divided into 1×11 \times 1 cells. Of these, NN cells are black and the rest are white.

For every 3×33 \times 3 subgrid, find how many subgrids contain exactly ii black cells. (0≤i≤90 \le i \le 9)

Input

The first line gives the size of the grid HH, WW and the number of black cells NN.

Each of the following NN lines gives the position rr, cc of a black cell, one per line. No cell is given more than once.

Output

Output the answers on 10 lines. On line i+1i+1, output the number of subgrids that contain exactly ii black cells. (0≤i≤90 \le i \le 9)

Constraints

  • 3≤H,W≤1093 \le H, W \le 10^9
  • 0≤N≤min⁡(105,H×W)0 \le N \le \min(10^5, H \times W)
  • 1≤r≤H1 \le r \le H
  • 1≤c≤W1 \le c \le W

Examples3

  1. Example 1

    Input
    4 5 8
1 1
1 4
1 5
2 3
3 1
3 2
3 4
4 4
    Expected output
    0
0
0
2
4
0
0
0
0
0

  2. Example 2

    Input
    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
    Expected output
    4
26
22
10
2
0
0
0
0
0

  3. Example 3

    Input
    1000000000 1000000000 0
    Expected output
    999999996000000004
0
0
0
0
0
0
0
0
0