Bajtazar 终于找到了建造新巴伊托沃（Nowe Bajtowo）的理想区域。他还不确定城市会有多大，但他已经确定了一个直角坐标系，并决定城市将是一个边平行于坐标轴的矩形，其中一个顶点位于 $(0, 0)$。该矩形的对角顶点将位于某个尚未确定的点 $(W, H)$，其中 $W, H > 0$ 为整数。

Bajtazar 计划修建 $n+1$ 条平行于 $y$ 轴的林荫道，编号从 $0$ 到 $n$，其中第 $i$ 条林荫道连接点 $(x_i, 0)$ 和 $(x_i, H)$。他还计划修建 $m+1$ 条平行于 $x$ 轴的街道，编号从 $0$ 到 $m$，其中第 $j$ 条街道连接点 $(0, y_j)$ 和 $(W, y_j)$。出于技术原因，所有（尚未确定的）坐标 $x_i$ 和 $y_j$ 必须是满足 $0 = x_0 < x_1 < \dots < x_n = W$ 以及 $0 = y_0 < y_1 < \dots < y_m = H$ 的整数。林荫道和街道将城市划分为 $n \cdot m$ 个矩形地块，其中位于第 $i-1$ 条与第 $i$ 条林荫道之间以及第 $j-1$ 条与第 $j$ 条街道之间的地块记为 $(i, j)$。

Bajtazar 与新巴伊托沃的 $l$ 位未来居民保持联系，并收集了他们的偏好信息。他知道第 $k$ 位未来居民（对于 $k = 1, 2, \dots, l$）希望住在地块 $(a_k, b_k)$，并要求该地块的面积恰好为 $p_k$ 平方米（其中 $1 \le p_k \le r$，参数 $r$ 在输入中给出）。你可以假设对于 $i \neq j$，满足 $a_i \neq a_j$ 或 $b_i \neq b_j$。没有任何未来居民感兴趣的地块可以具有任意面积。Bajtazar 请你检查是否有可能满足所有未来居民的要求，如果可以，请确定整个城市可能的最小面积。

输入格式

输入的第一行包含四个整数 $n, m, l$ 和 $r$ ($1 \le n, m \le 10^3, 1 \le l \le n \cdot m, 1 \le r \le 10^6$)。接下来的 $l$ 行描述了未来居民的要求；第 $i$ 行包含三个整数：$a_i, b_i$ 和 $p_i$ ($1 \le a_i \le n, 1 \le b_i \le m, 1 \le p_i \le r$)。

输出格式

输出的第一行应包含一个单词 TAK（如果可以满足所有未来居民的要求），否则输出 NIE。如果可以满足所有要求，则标准输出的第二行应包含一个整数 $p$，表示满足所有未来居民要求的城市可能具有的最小面积。

样例

样例输入 1

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

样例输出 1

NIE

样例输入 2

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

样例输出 2

TAK
24

说明 2

在第二个样例中，可以注意到我们必须有 $x_0 = 0, x_1 = 7, x_2 = 8$ 以及 $y_0 = 0, y_1 = 1, y_2 = 3$。这种布局如下图所示。每个地块上的数字表示其面积。加粗的数字表示未来居民要求的面积。未加粗的数字表示没有要求的地块。

子任务

测试集分为以下子任务。每个子任务的测试由一个或多个独立的测试组组成。

如果仅第一行正确，你的程序将获得该测试点 50% 的分数。