给你一个大小为 $n \times n$ 的网格棋盘，棋盘上的 $n^2$ 个格子中的每一个都包含数字 $-1$、$0$ 或 $1$ 之一。同时给定四个整数 $A_L, A_D, A_R$ 和 $A_U$。我们希望在棋盘上画两条折线：
- 一条连接棋盘的左上角 and 右下角，且只能沿着格子的边界向右和向下移动；
- 另一条连接棋盘的左下角 and 右上角，且只能沿着格子的边界向右和向上移动。
这两条折线将棋盘划分为四个（可能为空的）区域：左（left）、下（down）、右（right）和上（up）。请判断是否存在两条折线，使得这四个区域内格子的数值之和分别等于 $A_L, A_D, A_R$ 和 $A_U$。对于 $t$ 个独立的测试用例，若存在则输出 TAK（是），否则输出 NIE（否）。
上图展示了样例中相同的 $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（否）。
样例
输入格式 1
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
输出格式 1
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