Fortune Telling(占い) - joi2012-day3
時間制限: 2秒
メモリ制限: 64MB
K 理事長は占いが好きで，いつも様々な占いをしている．
今日はカードを使って今年の IOI での日本選手団の出来を占うことにした．
占いの方法は次のようなものである．
- まずカードを縦 M 行，横 N 列の長方形状に全て表にして並べる．
- i = 1,…,K について，「上から数えて A_i 行目から B_i 行目かつ，左から数えて C_i 列目から D_i 列目にある全てのカードの表裏をひっくり返す」という操作を行う．すなわち，上から a 行目で左から b 列目にあるカードを (a,b) と書いたとき，各 i について，A_i \leqq a \leqq B_i かつ C_i \leqq b \leqq D_i をみたすカード (a,b) を全てひっくり返す操作を行う．
- 操作が終わった後，表になっているカードの枚数によって占いの結果が出る．
K 理事長は途中でカードをひっくり返す回数があまりに多いことに気付いたので，カードを実際に使って占うのはやめて，操作が終わった後に表になっているカードの枚数だけを求めることにした．
課題
行の長さ M，列の長さN，操作の回数 K および K 回の操作の指示が与えられたとき，操作後に表になっているカードの枚数を求めるプログラムを作成せよ．
制限
| 1 \leqq M \leqq 1\,000\,000\,000\,(=10^9) | 行の長さ |
| 1 \leqq N \leqq 1\,000\,000\,000\,(=10^9) | 列の長さ |
| 1 \leqq K \leqq 100\,000\,(=10^5) | 操作の回数 |
入力
標準入力から以下の入力を読み込め．
- 1 行目には整数 M, N, K が空白を区切りとして書かれており，カードが M 行 N 列に並んでいることと，操作を行う回数が K 回であることを表す．
- 1 + i 行目 (1 \leqq i \leqq K) には 4 つの整数 A_i, B_i, C_i, D_i (1 \leqq A_i \leqq B_i \leqq M, 1 \leqq C_i \leqq D_i \leqq N) が書かれており，i 回目の操作は上から A_i 行目から B_i 行目かつ，左から C_i 列目から D_i 列目のカードを全てひっくり返すことを表す．
出力
標準出力に，K 回の操作後に表になっているカードの枚数を 1 行で出力せよ．
採点基準
- 採点用データのうち，配点の 30% 分については，K \leqq 3\,000を満たす．
入出力例
| 入力例1 | 出力例1 |
|---|---|
| 6 5 3 2 4 1 4 4 6 3 5 1 2 3 5 |
11 |
この例では，K = 3 回の操作は以下のように行われる．
表のカードを□，裏のカードを■で表すと，
初期状態 □□□□□ □□□□□ □□□□□ □□□□□ □□□□□ □□□□□ ↓ □□□□□ ■■■■□ ■■■■□ ■■■■□ □□□□□ □□□□□ ↓ □□□□□ ■■■■□ ■■■■□ ■■□□■ □□■■■ □□■■■ ↓ □□■■■ ■■□□■ ■■■■□ ■■□□■ □□■■■ □□■■■ 最終状態
最終状態で表になっているカードの枚数 11 を出力する．