明日（11 月 17 日）は「無借金デー」（Debt-Free Day）です。この機会に、$n$ 人の友人はこれまでの数々の旅行で生じた互いの貸し借りをついに精算することにしました。彼らは常にアプリに支出を記録しており、アプリが今回すべてを集計・簡略化しました。各人について合計残高 $a_i$ が表示されます — その人がお金を受け取る側であれば正、返済しなければならない側であれば負です。もちろん、表示されるすべての値の合計は 0 に等しいです：$\sum_{i=1}^n a_i = 0$。各人の残高が 0 になるように、（整数値の）送金計画を立てたいと考えています。

$n$ 人の人々は $m$ 個の信頼関係で結ばれており、三つ組 $(u_j, v_j, c_j)$ で表されます — 人 $u_j$ と人 $v_j$ は互いを十分に信頼しているため、どちらか一方が他方へ最大 $c_j$ の金額の送金を 1 回行うことができます。信頼関係で直接結ばれていない人同士は互いに送金できません。順序なしペア $\{u_j, v_j\}$ は重複せず、信頼ネットワーク全体は連結です — どの 2 人も（複数ステップかもしれない）信頼関係の経路で結ばれています。

アプリには負債総額 $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$ 人のグループは、すべての貸し借りを完全に精算する — すなわち全員の残高を 0 にする — ように送金の向きと金額を決めることができるでしょうか？ $t$ 個の独立したテストケースのそれぞれについて、TAK（はい）または NIE（いいえ）を出力してください。

すべての人は必要な送金を行うのに十分なお金を持っていると仮定して構いません。

入力

1 行目には、テストケースの個数を表す整数 $t$ ($1 \le t \le 10^5$) が与えられます。

各テストケースの 1 行目には、それぞれ人数と信頼関係の個数を表す 2 つの整数 $n$ と $m$ ($2 \le n \le 10^6$; $n - 1 \le m \le 10^6$) が与えられます。

各テストケースの 2 行目には、各人の初期残高を表す $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$ のうち少なくとも 1 つは 0 ではありません。

$A = \sum_{i=1}^n \max(0, a_i)$ と定義します。前の条件より $A \ge 1$ が従います。

続く $m$ 行は信頼関係を表し、$j$ 行目には 3 つの整数 $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\}$ は高々 1 回しか現れません。

すべてのテストケースにわたる $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

注記

1 つ目のテストケースでは、残高 $a = (20, -20)$ の 2 人がいます。1 人目は 2 人目に金額 20 の送金を行うべきですが、最大でも $c_1 = 10$ までしか送れません。答えは NIE（いいえ）です。

下の図は、頂点内に残高 $a = (0, 1, 1, 1, -3)$ が書かれ、辺上に上限 $c_j$ が書かれた 2 つ目のテストケースを表しています。

下に有効な送金計画の例を 2 つ示します。どちらの計画でも送金上限は超えておらず、全員の最終残高が 0 になります。答えは TAK（はい）です。