내일(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$만큼의 금액을 한 번 송금할 수 있습니다. 신뢰 관계로 직접 연결되지 않은 사람들은 서로 돈을 보낼 수 없습니다. 순서 없는 쌍 $\{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$명의 그룹이 모든 빚을 완전히 정산하도록 — 즉, 모든 사람의 잔액을 0으로 만들도록 — 송금 방향과 금액을 정할 수 있을까요? $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$ 중 적어도 하나는 0이 아닙니다.

$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(예)입니다.