أُعطيت لوحة بحجم $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