נתון לוח בגודל $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, 0, -2, 1)$, תשובה
TAK - $(0, 2, -3, 1)$, תשובה
TAK - $(-2, 0, 1, 1)$, תשובה
NIE