エイプリルフールは過ぎ去りましたが、少女の心を忘れない小リスは、まだ何か面白いことをしたいと考えています。

小リスの教室には、真っ白な壁があります。この壁は $N$ 行 $M$ 列の矩形グリッドとみなすことができます。彼女は合計 $K$ 回の壁塗り操作を順番に行う予定です。$i$ 回目の操作では、連続するいくつかの行または連続するいくつかの列を選び、それらを色 $c_i$ で塗りつぶします（各色は異なる非負整数で表され、$0$ は白色を表します）。

塗り終わった後の壁は、例えばこのようになります！（サンプル3に対応）

同じマス目において、後に塗られた色はそれ以前の色を完全に上書きします。

小リスの好奇心を満たすために、すべての塗りつぶし操作が完了した後に、隣接するマス同士で色が同じであるペアがいくつあるか求めてください。

入力

1行目に4つの非負整数 $N, M, K, q$ が空白区切りで与えられます（$q \in \{0, 1\}$、出力形式の説明を参照）。

続く $K$ 行の各行には、4つの非負整数 $type_i, l_i, r_i, c_i$ （$type_i \in \{0, 1\}$、$0 \leq c_i \leq K$）が空白区切りで与えられ、1回の塗りつぶし操作を表します。$type_i = 0$ の場合、第 $l_i$ 行から第 $r_i$ 行までを選択したことを表します（$1 \leq l_i \leq r_i \leq N$）。$type_i = 1$ の場合、第 $l_i$ 列から第 $r_i$ 列までを選択したことを表します（$1 \leq l_i \leq r_i \leq M$）。

出力

整数を1つ出力してください。

$q = 0$ の場合、辺で隣接するマス同士で色が同じであるペアの数を出力してください（辺で隣接するとは、共通の辺を持つことを指します）。

$q = 1$ の場合、辺または角で隣接するマス同士で色が同じであるペアの数を出力してください（角で隣接するとは、共通の角を持つことを指します）。

入出力例

入力 1

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

出力 1

8

注記 1

下図を参照してください。各短い線分が、色が同じである隣接するマスのペアに対応しています。

入力 2

5 4 1 1
1 2 4 0

出力 2

55

入力 3

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

出力 3

33

制約

すべてのテストケースにおいて、$1 \leq N, M, K \leq 10^5$ です。

各テストケースの詳細を以下の表に示します。