Byteasar 是 Byteland Worldbeat Publishers (BWP) 的一名经理。公司雇佣了 $n$ 名作曲家和 $m$ 名作词家。艺术家们以“一名作曲家和一名作词家”为一对进行工作。

Byteasar 了解 BWP 员工的技能，因此他可以评估每一对作曲家-作词家组合的效率。每一对潜在组合的效率以每周创作的歌曲数量来衡量。

Byteasar 希望将员工安排成 $\min(n, m)$ 对互不重叠的组合，使得每周创作的歌曲总数尽可能高。未配对的艺术家将不会工作。

在分析了所有数据后，Byteasar 怀疑 BWP 每周创作的歌曲总数与配对方式无关。Byteasar 对此感到惊讶，因此他请求你编写一个程序来验证这一观察结果。

输入格式

输入的第一行包含一个整数 $t$ ($1 \le t \le 10$)，表示测试用例的数量。

每个测试用例的第一行包含三个整数 $n$、$m$ 和 $k$ ($1 \le n, m \le 100\,000$，$1 \le k \le 300\,000$)，分别表示作曲家的数量、作词家的数量以及描述组合效率的行数。作曲家的编号为 $1$ 到 $n$，作词家的编号为 $1$ 到 $m$。

接下来的 $k$ 行，每行包含四个整数 $a_{i}$、$b_{i}$、$c_{i}$ 和 $p_{i}$ ($1 \le a_{i} \le n$，$1 \le b_{i} \le c_{i} \le m$，$1 \le p_{i} \le 10^{9}$)，表示作曲家 $a_{i}$ 与范围在 $b_{i}$ 到 $c_{i}$（包含边界）内的任何作词家组成的搭档，每周将创作 $p_{i}$ 首歌曲。

每对作曲家-作词家组合最多被描述一次。如果某一对组合未在输入中提及，则假设他们擅长的音乐流派不兼容，因此他们的工作效率为每周 $0$ 首歌曲。尽管如此，这样的组合在 BWP 中仍然可以形成。

输出格式

你的程序应输出 $t$ 行，对应每个测试用例的答案。对于每个测试用例，如果对于每种 $\min(n, m)$ 对的安排方式，总效率都相同，则输出 TAK（波兰语中的“是”）；否则，输出 NIE（波兰语中的“否”）。

样例

输入 1

2
2 3 3
1 1 3 3
2 1 1 3
2 2 3 3
3 3 7
1 1 1 5
1 2 2 6
2 1 1 5
2 2 2 6
3 1 1 8
3 2 2 9
3 3 3 10

输出 1

TAK
NIE