聽日（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（係）。