День смеха только что прошел, но маленькая белка, не теряющая своего детского задора, хочет сделать что-то еще более интересное.

В классе у белки есть чисто белая стена. Эту стену можно представить как прямоугольную сетку размером $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

Примечание 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$.

В следующей таблице приведена подробная информация о каждом тестовом случае.