Дана доска размера $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