April Fools' Day has just passed, but the little squirrel, still full of youthful spirit, wants to do something more interesting.

In the squirrel's classroom, there is a pure white wall. This wall can be viewed as an $N \times M$ rectangular grid. She plans to perform $K$ wall-painting operations in sequence. For the $i$-th operation, she chooses a contiguous range of rows or a contiguous range of columns and paints them with color $c_i$ (each color can be represented as a distinct non-negative integer, where $0$ represents white).

The wall might look like this after painting! (This corresponds to Example 3)

On the same cell, a later paint color will completely cover the previous color.

Please help the little squirrel satisfy her curiosity by telling her how many pairs of adjacent cells have the same color after all painting operations are completed.

Input

The first line contains four non-negative integers $N, M, K, q$ separated by spaces ($q \in \{0, 1\}$, see the explanation in the Output section).

For the next $K$ lines, the $i$-th line contains four non-negative integers $type_i, l_i, r_i, c_i$ ($type_i \in \{0, 1\}$, $0 \leq c_i \leq K$), describing a painting operation. If $type_i = 0$, it means she chose rows $l_i$ through $r_i$ ($1 \leq l_i \leq r_i \leq N$); if $type_i = 1$, it means she chose columns $l_i$ through $r_i$ ($1 \leq l_i \leq r_i \leq M$).

Output

A single integer.

If $q = 0$, output the number of pairs of edge-adjacent cells that have the same color (edge-adjacent means cells sharing a common edge).

If $q = 1$, output the number of pairs of edge-adjacent or corner-adjacent cells that have the same color (corner-adjacent means cells sharing a common corner).

Examples

Input 1

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

Output 1

8

Note 1

See the figure below. Each small line segment corresponds to a pair of adjacent cells with the same color.

Input 2

5 4 1 1
1 2 4 0

Output 2

55

Input 3

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

Output 3

33

Constraints

For all test cases, $1 \leq N, M, K \leq 10^5$.

The following table describes the details of each test case.