คุณได้รับกระดานขนาด $n \times n$ โดยแต่ละช่องจากทั้ง $n^2$ ช่องจะมีตัวเลข $-1$, $0$ หรือ $1$ อยู่หนึ่งตัว นอกจากนี้คุณยังได้รับจำนวนเต็มสี่จำนวน $A_L, A_D, A_R$ และ $A_U$ เราต้องการลากเส้นหยักสองเส้น:
- เส้นหนึ่งเชื่อมมุมบนซ้ายของกระดานเข้ากับมุมล่างขวา โดยเคลื่อนที่ไปตามขอบของช่องไปทางขวาและลงล่างเท่านั้น
- และอีกเส้นหนึ่งเชื่อมมุมล่างซ้ายของกระดานเข้ากับมุมบนขวา โดยเคลื่อนที่ไปทางขวาและขึ้นบนเท่านั้น
เส้นหยักทั้งสองจะแบ่งกระดานออกเป็นสี่บริเวณ (ซึ่งอาจว่างเปล่าได้) ได้แก่ ซ้าย ล่าง ขวา และบน จงตรวจสอบว่ามีเส้นหยักสองเส้นที่ทำให้ผลรวมของช่องในสี่บริเวณนี้เท่ากับ $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