Prima Aprilis właśnie minął, ale mała wiewiórka, wciąż pełna dziewczęcego entuzjazmu, chce zrobić coś jeszcze ciekawszego.
W klasie wiewiórki znajduje się czysto biała ściana. Ścianę tę można postrzegać jako prostokątną siatkę o $N$ wierszach i $M$ kolumnach. Wiewiórka planuje wykonać kolejno $K$ operacji malowania. W każdej $i$-tej operacji wybiera ona pewną liczbę kolejnych wierszy lub kolejnych kolumn i maluje je na kolor $c_i$ (każdy kolor można przedstawić jako inną nieujemną liczbę całkowitą, gdzie $0$ oznacza kolor biały).
Tak może wyglądać ściana po pomalowaniu! (odpowiada przykładowi 3)
Na tym samym polu nowszy kolor całkowicie przykrywa poprzedni.
Pomóż wiewiórce zaspokoić jej ciekawość i oblicz, ile par sąsiadujących ze sobą pól ma ten sam kolor po wykonaniu wszystkich operacji malowania.
Wejście
Pierwsza linia zawiera cztery nieujemne liczby całkowite $N, M, K, q$ ($q \in \{0, 1\}$, patrz opis w sekcji Wyjście).
Kolejne $K$ linii zawiera po cztery nieujemne liczby całkowite $type_i, l_i, r_i, c_i$ ($type_i \in \{0, 1\}$, $0 \leq c_i \leq K$), opisujące operację malowania. Jeśli $type_i = 0$, oznacza to, że wybrano wiersze od $l_i$ do $r_i$ ($1 \leq l_i \leq r_i \leq N$). Jeśli $type_i = 1$, oznacza to, że wybrano kolumny od $l_i$ do $r_i$ ($1 \leq l_i \leq r_i \leq M$).
Wyjście
Jedna liczba całkowita.
Jeśli $q = 0$, wypisz liczbę par pól sąsiadujących bokami, które mają ten sam kolor (sąsiedztwo bokami oznacza pola mające wspólny bok).
Jeśli $q = 1$, wypisz liczbę par pól sąsiadujących bokami lub rogami, które mają ten sam kolor (sąsiedztwo rogami oznacza pola mające wspólny róg).
Przykład
Przykład 1
3 4 3 1 0 2 3 2 1 3 3 0 1 2 2 1
Wyjście 1
8
Uwagi 1
Zobacz poniższy rysunek. Każda krótka kreska odpowiada parze sąsiadujących pól o tym samym kolorze.
Przykład 2
5 4 1 1 1 2 4 0
Wyjście 2
55
Przykład 3
6 6 4 0 0 3 6 1 1 2 2 2 0 4 5 4 1 4 5 1
Wyjście 3
33
Ograniczenia
Dla wszystkich przypadków testowych $1 \leq N, M, K \leq 10^5$.
Poniższa tabela zawiera szczegółowe informacje o każdym teście.
| Numer testu | $N, M \leq$ | $K \leq$ | $q =$ | Inne założenia |
|---|---|---|---|---|
| 1 | $5000$ | $5000$ | $1$ | $l_i = r_i$ |
| 2 | $5000$ | $5000$ | $1$ | brak |
| 3 | $5000$ | $10^5$ | $1$ | brak |
| 4, 5 | $10^5$ | $10^5$ | $0$ | $l_i = r_i$ |
| 6, 7, 8 | $10^5$ | $10^5$ | $0$ | brak |
| 9, 10 | $10^5$ | $5000$ | $1$ | brak |
| 11, 12 | $10^5$ | $10^5$ | $1$ | $c_i = i$ |
| 13, 14, 15, 16 | $10^5$ | $10^5$ | $1$ | $c_i \in \{0, 1\}$ |
| 17, 18, 19, 20 | $10^5$ | $10^5$ | $1$ | brak |