מחר (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 (כן).