Bạn được cho một bảng kích thước $n \times n$, với mỗi ô trong số $n^2$ ô của nó chứa một trong các số $-1$, $0$ hoặc $1$. Bạn cũng được cho bốn số nguyên $A_L, A_D, A_R$ và $A_U$. Ta muốn vẽ hai đường gấp khúc:
- một đường nối góc trên bên trái của bảng với góc dưới bên phải; chỉ di chuyển dọc theo cạnh của các ô sang phải và xuống dưới,
- và đường còn lại nối góc dưới bên trái của bảng với góc trên bên phải, chỉ di chuyển sang phải và lên trên.
Hai đường gấp khúc chia bảng thành bốn miền (có thể rỗng): trái, dưới, phải và trên. Hãy kiểm tra xem có tồn tại hai đường gấp khúc sao cho tổng các ô trong bốn miền này lần lượt bằng $A_L, A_D, A_R$ và $A_U$ hay không. In ra TAK (có) hoặc NIE (không) cho mỗi bộ kiểm tra độc lập trong số $t$ bộ kiểm tra.
Các hình vẽ minh họa cùng một bảng $5 \times 5$ trong bộ kiểm tra ví dụ.
Hình bên trái minh họa một cách chia thành các miền có tổng $(1, 0, -2, 1)$ (theo thứ tự $A_L, A_D, A_R, A_U$). Đường gấp khúc thứ nhất có thể được mô tả bởi từ RDDDRRDRDR, và đường thứ hai bởi RURUURRUUR (trong đó D, U và R lần lượt biểu thị các bước di chuyển dọc theo cạnh xuống dưới, lên trên và sang phải). Ví dụ, miền bên phải chứa 8 ô với tổng $A_R = 0 - 1 - 1 + 0 - 1 + 0 + 1 + 0 = -2$.
Hình bên phải minh họa một cách chia thành các miền có tổng $(0, 2, -3, 1)$. Miền bên trái rỗng nên tổng các ô của nó bằng không. Các đường gấp khúc có thể được mô tả bởi các từ DRRRRDDRDD và UUUURURRRR.
Cùng bảng đó không thể được chia thành các miền có tổng $(-2, 0, 1, 1)$, tức là $A_L = -2, A_D = 0, A_R = 1, A_U = 1$. Lưu ý rằng các giá trị tương tự nhưng theo thứ tự khác xuất hiện ở hình bên trái – thứ tự rất quan trọng.
Dữ liệu vào
Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $t$ ($1 \le t \le 100\,000$), biểu thị số lượng bộ kiểm tra.
Dòng đầu tiên của mỗi bộ kiểm tra chứa năm số nguyên $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$), biểu thị độ dài cạnh của bảng và tổng mong muốn của bốn miền.
Mỗi dòng trong $n$ dòng tiếp theo của bộ kiểm tra mô tả bảng; dòng thứ $i$ chứa $n$ số nguyên $a_{i1}, a_{i2}, \dots, a_{in}$ ($a_{ij} \in \{-1, 0, 1\}$), mô tả hàng thứ $i$. Tổng toàn bộ bảng bằng $A_L + A_D + A_R + A_U$.
Tổng của $n^2$ trên tất cả các bộ kiểm tra không vượt quá $4\,000\,000$.
Kết quả
In ra đúng $t$ dòng – với mỗi bộ kiểm tra, in ra từ TAK (có) nếu tồn tại các đường gấp khúc chia bảng thành các miền có tổng như chỉ định, hoặc từ NIE (không) trong trường hợp ngược lại.
Ví dụ
Dữ liệu vào
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
Kết quả
TAK TAK NIE NIE TAK
Ghi chú
Ba bộ kiểm tra đầu tiên tương ứng với các ví dụ được nêu trong đề bài. Chúng chứa cùng một bảng và các truy vấn cho các tổng $(A_L, A_D, A_R, A_U)$ theo thứ tự:
- $(1, 0, -2, 1)$, đáp án
TAK - $(0, 2, -3, 1)$, đáp án
TAK - $(-2, 0, 1, 1)$, đáp án
NIE