First, let us introduce the game of Kakuro.

The rules of the game are: Fill the square cells with integers from $1$ to $k$. In cells divided by a diagonal line, the number in the upper-right corner equals the sum of the numbers in the consecutive cells immediately to its right, and the number in the lower-left corner equals the sum of the numbers in the consecutive cells immediately below it. * Numbers in any consecutive sequence of cells (either horizontally or vertically) cannot repeat.

Apia gave Rimbaud a Kakuro puzzle. Rimbaud, who is not very clever or dexterous, found that she could never solve Kakuro puzzles. She suspected that the reason was that the puzzles Apia gave were too difficult, rather than her own lack of skill. Therefore, she wanted to evaluate the difficulty of this puzzle.

Rimbaud defines the difficulty of a Kakuro puzzle as the sum of the number of candidate values for each empty cell. We define the candidate values for each cell as the set of numbers that can be placed in that cell, considering only the constraints imposed by the row and column clues in the initial puzzle and the condition that numbers cannot repeat within a sequence.

If the clue for a sequence of 4 empty cells is 10, then these four numbers can only be $1+2+3+4$, meaning the set of candidate values for these cells under this clue's constraint is $\{1, 2, 3, 4\}$.

More generally, if the clue for a sequence of $c$ empty cells is $s$, then considering all $c$-tuples of distinct values between $1$ and $k$ that sum to $s$, the set of candidate values for these cells under this clue's constraint is the set of all numbers that appear in any of these $c$-tuples. For each cell, its set of candidate values is the intersection of the candidate values allowed by its row constraint and its column constraint.

In this puzzle, consider the empty cell at row 2, column 2. The row clue for this cell is 16, and the corresponding set of candidate values is $\{7, 9\}$. The column clue for this cell is 23, and the corresponding set of candidate values is $\{6, 8, 9\}$, so the set of candidate values for this cell is $\{9\}$. For the empty cell at row 2, column 3, the row clue's corresponding set of candidate values is $\{7, 9\}$, and the column clue's corresponding set of candidate values is $\{6, 7, 8, 9\}$, so the set of candidate values for this cell is $\{7, 9\}$. Note that although we could determine the number in the cell at row 2, column 2 first and then deduce the number in the cell at row 2, column 3 based on the row clue, Rimbaud only considers the initial clues.

Please help Rimbaud calculate the difficulty of this puzzle, which is the sum of the number of candidate values for all empty cells.

Input

The first line contains four positive integers $n, m, k, T$, representing the number of rows, columns, the range of values, and the total number of clues, respectively.

The next $T$ lines each contain five positive integers $t, x, y_1, y_2, s$ ($t \in \{0, 1\}, y_1 \leq y_2$). Here, $t$ represents the type of clue. If $t = 0$, it indicates a row clue, where the sum of the numbers in row $x$ from column $y_1$ to $y_2$ is $s$. If $t = 1$, it indicates a column clue, where the sum of the numbers in column $x$ from row $y_1$ to $y_2$ is $s$. Rows and columns are 1-indexed.

The empty cells of this puzzle are the union of all cells corresponding to the clues. The input guarantees that this is a valid Kakuro puzzle in terms of format, meaning that every sequence of consecutive empty cells has a clue to its left or above it, and every empty cell appears exactly twice.

In the data, it is possible that the set of candidate values for some positions is empty or that the puzzle has no solution. In such cases, you should still calculate the difficulty of the puzzle according to the definition.

Output

Output a single integer representing the answer.

Examples

Input 1

8 8 9 24
0 2 2 3 16
0 2 6 8 24
0 3 2 3 17
0 3 5 8 29
0 4 2 6 35
0 5 3 4 7
0 5 6 7 8
0 6 4 8 16
0 7 2 5 21
0 7 7 8 5
0 8 2 4 6
0 8 7 8 3
1 2 2 4 23
1 2 7 8 11
1 3 2 5 30
1 3 7 8 10
1 4 4 8 15
1 5 3 4 17
1 5 6 7 7
1 6 2 6 27
1 7 2 3 12
1 7 5 8 12
1 8 2 3 16
1 8 6 8 7

Output 1

127

Constraints

• For 10% of the data, $n, m \leq 3$.
• For 30% of the data, $n, m \leq 50$.
• For 50% of the data, $n, m \leq 500$.
• For another 20% of the data, only the first row and first column contain clues, and all other cells are empty.
• For 100% of the data, $3 \leq n, m, T \leq 10^5$, $1 \leq k \leq 10^5$, $s \leq 10^{18}$.

Figure 1. A Kakuro puzzle