Today is a special day for AUCPL.inc: the whole office is being remodelled. To prove that you are able to handle more responsibility (and because you seem skilled at putting holes into walls), your manager has assigned you the task of tearing down all the walls on the executive floor.

The executive floor is a grid of private offices, with ~n~ rows and ~m~ columns. The top-left office is at ~(1, 1)~, and the bottom-right office is at ~(n, m)~. Each office is a square, with an area of ~100~ square meters.

You are given ~q~ commands. Each command consists of four integers ~r_1, c_1, r_2, c_2~, indicating that the wall between the offices at ~(r_1, c_1)~ and ~(r_2, c_2)~ should be removed.

It is guaranteed that the wall has not been removed before, and that the two offices are adjacent. Either:

• ~r_2 = r_1 + 1~ and ~c_2 = c_1~ (the offices are vertically adjacent).
• ~r_2 = r_1~ and ~c_2 = c_1 + 1~ (the offices are horizontally adjacent).

Initially, all offices are separate. As walls are removed, offices may merge into larger connected components.

After each tear-down, report the total area of the room containing these offices after removing the wall.

Input

The first line of the input contains three integers ~n~, ~m~ and ~q~ (~1 \leq n, m \leq 10^3~), (~1 \leq q \leq 10^5~), the number of rows and columns of offices on the executive floor of AUCPL.inc, and the number of commands.

The next ~q~ lines contain four integers ~r_1~, ~c_1~, ~r_2~ and ~c_2~ (~1 \leq r_1, r_2 \leq n~), (~1 \leq c_1, c_2 \leq m~), indicating that the wall between the offices at ~(r_1, c_1)~ and ~(r_2, c_2)~ should be removed. It is guaranteed these offices are either vertically or horizontally adjacent.

Output

After each wall is torn down, output the area of the resulting office, in square meters.

Example

Input 1

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

Output 1

200
300
200
400
600

The offices that are created from each tear-down are visualised in red below. As more walls are torn down, the office spaces combine, creating increasingly large rooms.

Input 2

2 3 4
1 2 1 3
1 2 2 2
2 2 2 3
1 3 2 3

Output 2

200
300
400
400

The offices that are created from each tear-down are visualised in red below. A connected office space may still contain internal walls that were not removed earlier. These do not affect connectivity, as long as all offices are connected through some path.

Input 3

4 4 10
1 2 1 3
2 2 2 3
3 2 3 3
4 2 4 3
1 3 2 3
2 2 3 2
3 3 4 3
3 2 4 2
1 1 2 1
1 1 1 2

Output 3

200
200
200
200
400
600
800
800
200
1000