시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 1 1 1 100.000%

문제

K 理事長は占いが好きで,いつも様々な占いをしている.今日はカードを使って今年の IOI での日本選 手団の出来を占うことにした. 占いの方法は次のようなものである.

  • まずカードを縦 M 行,横 N 列の長方形状に全て表にして並べる.
  • i = 1, ··· , K について,「上から数えて Ai 行目から Bi 行目かつ,左から数えて Ci 列目から Di 列目に ある全てのカードの表裏をひっくり返す」という操作を行う.すなわち,上から a 行目で左から b 列 目にあるカードを (a, b) と書いたとき,各 i について,Ai ≤ a ≤ Bi かつ Ci ≤ b ≤ Di をみたすカード (a, b) を全てひっくり返す操作を行う.
  • 操作が終わった後,表になっているカードの枚数によって占いの結果が出る.

K 理事長は途中でカードをひっくり返す回数があまりに多いことに気付いたので,カードを実際に使っ て占うのはやめて,操作が終わった後に表になっているカードの枚数だけを求めることにした.

行の長さ M,列の長さ N,操作の回数 K および K 回の操作の指示が与えられたとき,操作後に表になっ ているカードの枚数を求めるプログラムを作成せよ.

입력

標準入力から以下の入力を読み込め.

  • 1 行目には整数 M, N, K が空白を区切りとして書かれており,カードが M 行 N 列に並んでいること と,操作を行う回数が K 回であることを表す.
  • 1 + i 行目 (1 ≤ i ≤ K) には 4 つの整数 Ai, Bi, Ci, Di (1 ≤ Ai ≤ Bi ≤ M, 1 ≤ Ci ≤ Di ≤ N) が書かれており, i 回目の操作は上から Ai 行目から Bi 行目かつ,左から Ci 列目から Di 列目のカードを全てひっくり 返すことを表す.

출력

標準出力に,K 回の操作後に表になっているカードの枚数を 1 行で出力せよ.

제한

  • 1 ≤ M ≤ 1 000 000 000 (= 109) 行の長さ
  • 1 ≤ N ≤ 1 000 000 000 (= 109) 列の長さ
  • 1 ≤ K ≤ 100 000 (= 105) 操作の回数

예제 입력 1

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

예제 출력 1

11

この例では,K = 3 回の操作は以下のように行われる.

表のカードを□,裏のカードを■で表すと,

初期状態

最終状態

最終状態で表になっているカードの枚数 11 を出力する.