C - Checkered Stamps /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800

問題文

10^9 \times 10^9 のグリッドがあります。上から i 行目、左から j 列目のマスを (i,j) と表すことにします。グリッドのそれぞれのマスは白か黒のどちらかの色になります。最初は全てのマスの色は白です。

今から高橋君は、合計 N 個のスタンプを押します。i 回目 (1 ≤ i ≤ N) は、縦 H_i マス、横 W_i マスの長方形のスタンプを、 左上が (R_i, C_i) と重なるように押します (スタンプの押される部分がグリッドからはみ出すことはありません)。このスタンプは、全体が白いグリッドに押したときに市松模様ができるように設計されており、スタンプの上から p 行目、左から q 列目 (1 ≤ p ≤ H_i, 1 ≤ q ≤ W_i) が押されたマスは、 p+q が偶数ならば白と黒が反転し、奇数ならば変化しません。

N 個のスタンプを押した後、グリッドに黒いマスがいくつあるかを求めてください。

制約

  • 1 ≤ N ≤ 10^5
  • 1 ≤ H_i ≤ 10^9
  • 1 ≤ W_i ≤ 10^9
  • 1 ≤ R_i ≤ 10^9
  • 1 ≤ C_i ≤ 10^9
  • H_i + R_i - 1 ≤ 10^9
  • W_i + C_i - 1 ≤ 10^9
  • 入力は全て整数

入力

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

N
H_1 W_1 R_1 C_1
:
H_N W_N R_N C_N

出力

N 個のスタンプを押した後の黒いマスの個数を出力せよ。


入力例 1

3
3 3 1 1
2 3 2 1
1 2 3 1

出力例 1

7

下の画像はグリッドの左上 3 \times 3 マスの変化を表しています。


入力例 2

5
66518928 212072708 158598694 334005903
54102801 860639145 839206374 16401163
226949335 660240556 476286324 65656871
153262413 54385827 719562883 5920096
496820604 90893558 460217283 428740659

出力例 2

130526013386872287