غدًا (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$ أشخاص الاتفاق على اتجاهات ومبالغ التحويلات لتسوية جميع الديون بالكامل — أي جعل رصيد الجميع صفرًا؟ اطبع TAK (نعم) أو NIE (لا) لكل حالة من حالات الاختبار المستقلة البالغ عددها $t$.

يمكنك افتراض أن كل شخص لديه ما يكفي من المال لإجراء أي تحويلات لازمة.

الإدخال

يحتوي السطر الأول على عدد صحيح $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 (نعم).