נתון לוח בגודל $n \times n$, כאשר כל אחד מ-$n^2$ התאים שלו מכיל אחד מהמספרים $-1$, $0$, או $1$. כמו כן נתונים ארבעה מספרים שלמים $A_L, A_D, A_R$ ו-$A_U$. ברצוננו לצייר שני קווים שבורים (polylines):

• אחד המחבר את הפינה השמאלית העליונה של הלוח עם הפינה הימנית התחתונה; הנע לאורך גבולות התאים רק ימינה ולמטה,
• והשני המחבר את הפינה השמאלית התחתונה של הלוח עם הפינה הימנית העליונה, הנע רק ימינה ולמעלה.

שני הקווים השבורים מחלקים את הלוח לארבעה אזורים (שייתכן שהם ריקים): שמאל, למטה, ימין ולמעלה. בדקו האם קיימים שני קווים שבורים כך שסכומי התאים בארבעת האזורים הללו שווים ל-$A_L, A_D, A_R$ ו-$A_U$, בהתאמה. הדפיסו TAK (כן) או NIE (לא) עבור כל אחד מ-$t$ מקרי הבדיקה הבלתי תלויים.

האיורים מציגים את אותו לוח $5 \times 5$ ממקרה הבדיקה לדוגמה.

האיור השמאלי מציג חלוקה לאזורים עם סכומים $(1, 0, -2, 1)$ (לפי הסדר $A_L, A_D, A_R, A_U$). ניתן לתאר את הקו השבור הראשון באמצעות המילה RDDDRRDRDR, ואת השני באמצעות RURUURRUUR (כאשר D, U ו-R מציינים תנועות לאורך הגבולות למטה, למעלה וימינה, בהתאמה). לדוגמה, האזור הימני מכיל 8 תאים שסכומם $A_R = 0 - 1 - 1 + 0 - 1 + 0 + 1 + 0 = -2$.

האיור הימני מציג חלוקה לאזורים עם סכומים $(0, 2, -3, 1)$. האזור השמאלי ריק, ולכן סכום התאים שלו הוא אפס. ניתן לתאר את הקווים השבורים באמצעות המילים DRRRRDDRDD ו-UUUURURRRR.

לא ניתן לחלק את אותו הלוח לאזורים עם סכומים $(-2, 0, 1, 1)$, כלומר $A_L = -2, A_D = 0, A_R = 1, A_U = 1$. שימו לב שאותם ערכים, אך בסדר שונה, מופיעים באיור השמאלי – לסדר יש חשיבות.

קלט

השורה הראשונה של הקלט מכילה מספר שלם יחיד $t$ ($1 \le t \le 100\,000$), המציין את מספר מקרי הבדיקה.

השורה הראשונה של מקרה בדיקה מכילה חמישה מספרים שלמים $n, A_L, A_D, A_R, A_U$ ($1 \le n \le 2000; -n^2 \le A_L, A_D, A_R, A_U \le n^2$), המציינים את אורך צלע הלוח ואת הסכומים הרצויים של ארבעת האזורים.

כל אחת מ-$n$ השורות הבאות של מקרה הבדיקה מתארת את הלוח; השורה ה-$i$ מכילה $n$ מספרים שלמים $a_{i1}, a_{i2}, \dots, a_{in}$ ($a_{ij} \in \{-1, 0, 1\}$), המתארים את השורה ה-$i$. הסכום הכולל של הלוח שווה ל-$A_L + A_D + A_R + A_U$.

הסכום הכולל של $n^2$ על פני כל מקרי הבדיקה אינו עולה על $4\,000\,000$.

פלט

הדפיסו בדיוק $t$ שורות – עבור כל מקרה בדיקה הדפיסו את המילה TAK (כן) אם קיימים קווים שבורים המחלקים את הלוח לאזורים עם הסכומים המצוינים, או את המילה NIE (לא) אחרת.

דוגמה

קלט

5
5 1 0 -2 1
1 0 -1 0 0
1 0 0 1 -1
0 1 -1 0 -1
0 0 0 0 1
-1 0 0 0 0
5 0 2 -3 1
1 0 -1 0 0
1 0 0 1 -1
0 1 -1 0 -1
0 0 0 0 1
-1 0 0 0 0
5 -2 0 1 1
1 0 -1 0 0
1 0 0 1 -1
0 1 -1 0 -1
0 0 0 0 1
-1 0 0 0 0
2 1 -1 0 1
1 0
-1 1
1 0 0 0 0
0

פלט

TAK
TAK
NIE
NIE
TAK

הערה

שלושת מקרי הבדיקה הראשונים מתאימים לדוגמאות המוצגות בניסוח הבעיה. הם מכילים את אותו הלוח ושאילתות עבור הסכומים $(A_L, A_D, A_R, A_U)$ לפי הסדר:

1. $(1, 0, -2, 1)$, תשובה TAK
2. $(0, 2, -3, 1)$, תשובה TAK
3. $(-2, 0, 1, 1)$, תשובה NIE