Submit
 

M : Monochrome Tile

Time Limit : 8 sec, Memory Limit : 524288 KB

Problem M: Monochrome Tile

Problem

白い正方形のタイルが横方向に W 個、縦方向に H 個、合計 W × H 個敷き詰められている。

太郎君は、 i 日目の朝に、左から axi 番目で上から ayi 番目のタイルを左上、 左から bxi 番目で上から byi 番目のタイルを右下にした長方形領域に存在しているタイルがすべて白いかどうかを確認する。 もしすべてのタイルが白かった場合、それらのタイルをすべて黒く塗りつぶす。それ以外のときは何もしない。

N 日間のそれぞれの日において、その日の作業が終了した時点で黒く塗りつぶされたタイルが何枚あるかを出力せよ。

Input

入力は以下の形式で与えられる。

H W
N
ax1 ay1 bx1 bx1
ax2 ay2 bx2 bx2
...
axN ayN bxN bxN
W H
N
ax1 ay1 bx1 by1
ax2 ay2 bx2 by2
...
axN ayN bxN byN

1行目に、2つの整数 HW が空白区切りで与えられる。 1行目に、2つの整数 WH が空白区切りで与えられる。 2行目に、1つの整数 N が与えられる。 3行目からの N 行のうち i 行目には i 日目の朝に確認する長方形領域を表す 4つの整数 axi ayi bxi bxi axi ayi bxi byi が空白区切りで与えられる。

Constraints

入力は以下の制約を満たす。

  • 2 ≤ W ≤ 100000
  • 2 ≤ H ≤ 100000
  • 2 ≤ N ≤ 100000
  • 1 ≤ axibxiW (1 ≤ iN )
  • 1 ≤ ayibyiH (1 ≤ iN )

Output

N 日間のそれぞれの日において、i 日目の作業が終了した時点で黒く塗りつぶされたタイルの枚数を i 行目にを出力せよ。

Sample Input 1

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

Sample Output 1

9
9
13
13
14

□□□□□
□□□□□
□□□□□
□□□□□

↓ 1 1 3 3

■■■□□
■■■□□
■■■□□
□□□□□

↓ 3 2 4 2 (なにもしない)

■■■□□
■■■□□
■■■□□
□□□□□

↓ 4 3 5 4

■■■□□
■■■□□
■■■■■
□□□■■

↓ 1 4 5 4 (なにもしない)

■■■□□
■■■□□
■■■■■
□□□■■

↓ 4 1 4 1

■■■■□
■■■□□
■■■■■
□□□■■

よって出力は、 9 → 9 → 13 → 13 → 14 となる。