明天（11 月 17 日）是“无债日”（Debt-Free Day）。在这个日子里，$n$ 个朋友决定彻底结清他们过去多次旅行中产生的共同债务。他们总是将开销记录在一个应用程序中，现在该程序已经汇总并简化了所有账目。对于每个人，程序会显示其总余额 $a_i$——如果该人为债权人（别人欠他钱），则余额为正；如果该人需要还钱，则余额为负。当然，所有显示余额的总和等于零：$\sum_{i=1}^n a_i = 0$。我们希望规划若干笔转账（转账金额为整数），使得每个人的余额最终都变为零。

这 $n$ 个人之间存在 $m$ 条信任关系，由三元组 $(u_j, v_j, c_j)$ 描述——人 $u_j$ 和 $v_j$ 之间有足够的信任，因此他们中的任何一人都可以向另一人进行金额不超过 $c_j$ 的单次转账。未直接通过信任关系连接的人之间不能直接转账。无序对 $\{u_j, v_j\}$ 不会重复，且整个信任网络是连通的——任意两个人之间都通过一条（可能包含多个步骤的）信任关系路径相连。

该程序显示了总债务 $A$（等价于所有正 $a_i$ 值的总和）。在这群朋友中，信任度相当高——对于由信任关系连接的每一对人，均满足 $c_j \ge \lceil \frac{A}{2} \rceil$。

例如，对于序列 $a = (10, -5, 0, 3, -4, -4)$，我们有 $A = 5 + 4 + 4 = 10 + 3 = 13$，因此 $c_j \ge 7$。

这群 $n$ 个人能否商定转账的方向和金额，以完全结清所有债务——即让每个人的余额都变为零？对于 $t$ 个独立的测试用例，若可以则输出 TAK（是），否则输出 NIE（否）。

你可以假设每个人都有足够的资金来执行任何必要的转账。

输入格式

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

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 10^6$；$n-1 \le m \le 10^6$)，分别表示人数和信任关系的数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$；$\sum_{i=1}^n a_i = 0$)，表示每个人的初始余额。其中至少有一个 $a_i$ 是非零的。

我们定义 $A = \sum_{i=1}^n \max(0, a_i)$。由前述条件可知 $A \ge 1$。

接下来的 $m$ 行描述信任关系；其中第 $j$ 行包含三个整数 $u_j$、$v_j$ 和 $c_j$ ($1 \le u_j, v_j \le n$；$u_j \ne v_j$；$\lceil \frac{A}{2} \rceil \le c_j \le 10^{15}$)。

由 $n$ 个人和 $m$ 条信任关系构成的网络是连通的，且在给定的测试用例中，每个无序对 $\{u, v\}$ 最多出现一次。

所有测试用例中 $n$ 的总和不超过 $10^6$；同样，所有测试用例中 $m$ 的总和不超过 $10^6$。

输出格式

输出 $t$ 行。对于每个测试用例，如果可以结清所有账户，则输出单词 TAK，否则输出 NIE。

样例

输入样例 1

3
2 1
20 -20
1 2 10
5 6
0 1 1 1 -3
1 2 2
2 3 3
3 4 5
2 4 7
1 5 2
4 5 2
3 2
1 2 -3
1 2 1000000000000000
2 3 999997235527681

输出样例 1

NIE
TAK
TAK

说明

在第一个测试用例中，有两个人的余额为 $a = (20, -20)$。第一个人应该向第二个人转账金额为 20 的资金，但最多只能转账 $c_1 = 10$。因此答案为 NIE（否）。

下图展示了第二个测试用例，其中顶点内写有余额 $a = (0, 1, 1, 1, -3)$，边上写有限制 $c_j$。

以下是两个合法的转账方案示例。在这两个方案中，均未超过转账限制，且每个人的最终余额都变为 0。因此答案为 TAK（是）。