403191: GYM101063 I Lazy Painting

The high commanders of GEMA are very interested in how to boost the productivity of the explorers and tried to do so in many ways. Their latest attempt is to paint the research labs in avant-garde (weird) ways. The research lab can be represented as a matrix with N rows and M columns and N * M tiles.

This time, the high commanders want to paint the tiles of the floor of the lab, but they could not decide on what colors to use. After a long useless discussion, they decided that they will give Q instructions to paint a rectangular area of the floor. As they want their job to be as easy as possible, all the rectangles have constant height H and width W and may overlap. To check if the floor is fully painted, they want to know, after each instruction, how many tiles are still unpainted.

The thing is, GEMA explorers are highly skilled scientists and hate petty jobs, but somebody has got to do them. Margarida was chosen to paint the floor of the main research lab. She is very sly and lazy, so she interpreted the instructions in a way that she would check the left border of the rectangle and if all of its tiles are painted, she wouldn't paint any tile. Also, if there was an unpainted tile in the left border, she would paint all the unpainted tiles reachable from that tile. One tile is reachable from another if it is possible to reach it using only unpainted tiles inside the rectangle.

The first line contains five integers N, M (1 ≤ N, M ≤ 10⁵ and 1 ≤ N * M ≤ 3 * 10⁶), H, W (1 ≤ H ≤ N, 1 ≤ W ≤ M) and Q (1 ≤ Q ≤ 10⁵). Then, Q lines follow. The i-th line contains two integers r_i and c_i (1 ≤ r_i ≤ N - H + 1, 1 ≤ c_i ≤ M - W + 1) — the upper left tile of the rectangular area to be painted. The topmost leftmost tile of the research lab is (1, 1).

Output the number of unpainted tiles after each instruction that Margarida has executed.

10 8 4 4 4
3 1
6 4
4 4
4 3

64
49
49
48

10 10 3 2 10
1 3
3 1
1 5
7 1
8 5
6 8
4 3
5 5
6 9
2 9

94
88
82
76
70
64
58
52
52
46