愚人節剛剛過去，少女心不減的小松鼠卻還想做一些更有意思的事情。

在小松鼠的教室裡，有一堵純白色的牆。這堵牆可以被看作 $N$ 行 $M$ 列的矩形網格。她計畫依序進行 $K$ 次刷牆操作。對於第 $i$ 次操作，她都選擇了連續的若干整行或者連續的若干整列，並把它們刷成顏色 $c_i$（每種顏色可以表示為一個不同的非負整數，其中 $0$ 表示白色）。

刷完之後的牆可能就是這個樣子的！（對應著範例 3）

在同一個格子上，後刷的顏色會完全覆蓋掉之前的顏色。

請你幫助小松鼠滿足她的好奇心，告訴她完成全部刷牆操作之後，有多少對相鄰的格子顏色相同。

輸入格式

第一行包含四個用空格隔開的非負整數 $N, M, K, q$（$q \in \{0, 1\}$，見輸出格式中的說明）。

對於接下來的 $K$ 行，第 $i$ 行包含四個用空格隔開的非負整數 $type_i, l_i, r_i, c_i$（$type_i \in \{0, 1\}$，$0 \leq c_i \leq K$），描述了一次刷牆操作。如果 $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$）。

輸出格式

一行一個整數。

如果 $q = 0$，輸出有多少對邊相鄰的格子顏色相同（邊相鄰即有公共邊的格子）；

如果 $q = 1$，輸出有多少對邊相鄰或角相鄰的格子顏色相同（角相鄰即有公共角的格子）。

範例

輸入格式 1

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

輸出格式 1

8

說明

見下圖。每條小短線對應著一對顏色相同的相鄰格子。

輸入格式 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$。

以下部分描述了每個測試點的詳細資訊。