明天（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。

範例

輸入

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

輸出

NIE
TAK
TAK

說明

在第一組測試資料中，有兩個人的餘額為 $a = (20, -20)$。第一個人應該向第二個人轉帳金額為 20 的資金，但最多只能轉帳 $c_1 = 10$。因此答案為 NIE（否）。

下圖展示了第二組測試資料，其中頂點內寫有餘額 $a = (0, 1, 1, 1, -3)$，邊上寫有限制 $c_j$。

以下是兩個合法的轉帳方案示例。在這兩個方案中，均未超過轉帳限制，且每個人的最終餘額都變為 0。因此答案為 TAK（是）。