The stars are so beautiful, and you feel like this moment could last forever. Until a few suddenly go supernova, bursting with brilliant energy! Although arguably more beautiful, you wonder how the radiation will affect the space ahead of you.

The space you can see can be represented as an ~n \times m~ grid. There are ~k~ stars that will go supernova at some row ~r~ and ~c~, irradiating all cells in the four cardinal directions, up, down, left, and right, as far as you can see. After each explosion, you wonder many total cells have been irradiated in total.

Input

The first line consists of two integers ~n~ ~(1 \leq n \leq 10^9)~ and ~m~ ~(1 \leq m \leq 10^9)~, the space you can see out the window.

The next line consists of a single integer ~s~ ~(1 \leq s \leq 10^5)~, the number of supernovae that will occur.

The next ~s~ lines contain two integers ~r~ ~(0 \leq r \leq n-1)~ and ~c~ ~( 0 \leq c \leq m-1)~, describing the positions of the stars that go supernova.

Output

After each supernova, count the number of cells that are irradiated.

Clarifications

• A cell can't be irradiated more than once, so don't count them twice!

Example

Input 1

5 5
4
1 3
4 0
4 1
4 1

Output 1

9
16
19
19

See below for how the supernova irradiate space.

Input 2

2 2
3
0 0
1 1
0 0

Output 2

3
4
4