サイズ $n \times n$ の盤面が与えられます。その $n^2$ 個の各マスには $-1$、$0$、$1$ のいずれかの数が書かれています。また、4 つの整数 $A_L, A_D, A_R$ および $A_U$ が与えられます。以下の 2 本の折れ線を引きたいと考えています：
- 1 本目は盤面の左上隅と右下隅を結び、マスの境界に沿って右と下にのみ移動する。
- もう 1 本は盤面の左下隅と右上隅を結び、右と上にのみ移動する。
これら 2 本の折れ線は、盤面を左・下・右・上の 4 つの（空である可能性もある）領域に分割します。これら 4 つの領域内のマスの総和がそれぞれ $A_L, A_D, A_R$ および $A_U$ に等しくなるような 2 本の折れ線が存在するかどうかを判定してください。$t$ 個の独立したテストケースそれぞれについて、TAK（はい）または NIE（いいえ）を出力してください。
上の図はサンプルテストと同じ $5 \times 5$ の盤面を表しています。
左の図は、総和が $(1, 0, -2, 1)$（$A_L, A_D, A_R, A_U$ の順）となる領域への分割を示しています。1 本目の折れ線は文字列 RDDDRRDRDR で、2 本目は 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$ となる領域に分割することはできません。左の図にも同じ値が登場しますが、順序が異なることに注意してください —— 順序は重要です。
入力
入力の 1 行目には、テストケースの個数を表す 1 つの整数 $t$ ($1 \le t \le 100\,000$) が含まれます。
各テストケースの 1 行目には、盤面の 1 辺の長さと 4 つの領域の目標総和を表す 5 つの整数 $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$ 行目には $i$ 行目を表す $n$ 個の整数 $a_{i1}, a_{i2}, \dots, a_{in}$ ($a_{ij} \in \{-1, 0, 1\}$) が含まれます。盤面全体の総和は $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
注記
最初の 3 つのテストケースは問題文中に示された例に対応しています。これらは同じ盤面を持ち、総和 $(A_L, A_D, A_R, A_U)$ に対するクエリが順番に与えられています：
- $(1, 0, -2, 1)$、答えは
TAK - $(0, 2, -3, 1)$、答えは
TAK - $(-2, 0, 1, 1)$、答えは
NIE