Задано дошку розміром $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