Bajtazar has finally found the perfect area to build New Bajtowo. He is not yet sure how large it will be, but he has defined a rectangular coordinate system and decided that the city will be a rectangle with sides parallel to the coordinate axes, with one vertex at the point $(0, 0)$. The opposite vertex of this rectangle will be at some as-yet-undetermined point $(W, H)$, for some integers $W, H > 0$.

Bajtazar plans to lay out $n+1$ parallel avenues numbered from $0$ to $n$, where the $i$-th avenue will connect the points $(x_i, 0)$ and $(x_i, H)$. He also plans to lay out $m+1$ parallel streets numbered from $0$ to $m$, where the $j$-th street will connect the points $(0, y_j)$ and $(W, y_j)$. For technical reasons, all (as-yet-undetermined) coordinates $x_i$ and $y_j$ must be integers satisfying the conditions $0 = x_0 < x_1 < \dots < x_n = W$ and $0 = y_0 < y_1 < \dots < y_m = H$. The avenues and streets will divide the city into $n \cdot m$ rectangular plots, where the plot between avenues $i-1$ and $i$ and streets $j-1$ and $j$ is denoted by the pair $(i, j)$.

Bajtazar is in contact with $l$ future residents of New Bajtowo and has collected information about their preferences. He knows that the $k$-th future resident (for $k = 1, 2, \dots, l$) would like to live on plot $(a_k, b_k)$ and demands that its area be exactly $p_k$ square meters (where $1 \le p_k \le r$ for a parameter $r$ given in the input). You may assume that $a_i = a_j$ or $b_i = b_j$ for $i \neq j$. Plots that no future resident is interested in may have any area. Bajtazar asks you to check whether it is possible to satisfy the demands of all future residents, and if so, to determine the minimum possible area of the entire city.

Input

The first line of the input contains four integers $n, m, l$ and $r$ ($1 \le n, m \le 10^3$, $1 \le l \le n \cdot m$, $1 \le r \le 10^6$). The next $l$ lines describe the requirements of the future residents; the $i$-th of these contains three integers: $a_i, b_i$ and $p_i$ ($1 \le a_i \le n, 1 \le b_i \le m, 1 \le p_i \le r$).

Output

The first line of the output should contain the word TAK if it is possible to satisfy the requirements of all future residents, or the word NIE otherwise. If it is possible to satisfy the requirements of all residents, the second line of the standard output should contain a single integer $p$ equal to the minimum area that the city can have while satisfying all the requirements of the future residents.

Examples

Input 1

2 2 3 100
1 1 7
1 2 13
2 1 1

Output 1

NIE

Input 2

2 2 3 100
1 1 7
1 2 14
2 1 1

Output 2

TAK
24

Note

In the second example, it can be observed that we must have $x_0 = 0, x_1 = 7, x_2 = 8$ and $y_0 = 0, y_1 = 1, y_2 = 3$. Such an arrangement is shown in the figure below. The number on each plot indicates its area. Bold numbers indicate areas that are required by future residents. Non-bold numbers indicate areas for which there are no requirements.

The layout of the city from the second example.

Subtasks

If only the first line is correct, your program will receive 50% of the points for a given test.