P7309 [COCI 2018/2019 #2] Kocka

In a children's playground, the author was attracted by a cube made of metal bars, and then came up with an interesting problem. This is the 2D version.

You are given an $N \times N$ matrix. Some cells are blocked, and some cells are empty. During observation, he looks at the matrix from $4$ directions. First, he looks from the left side. For each row, he records how many empty cells appear before the first blocked cell. If there is no blocked cell in that row, he records $-1$. Then he does the same from the right side, the top side, and the bottom side, and records the results. In total, he wrote down $4N$ numbers, with $N$ numbers for each direction. However, an unknown villain destroyed the matrix, and all that remains are the numbers he wrote down. You need to determine whether there is any mistake in these numbers, that is, whether it is possible to reconstruct an $N \times N$ matrix consistent with these numbers.

The first line contains a positive integer $N$, the size of the matrix. The second line contains $N$ integers $L_i$, the recorded numbers when observing from the left. The third line contains $N$ integers $R_i$, the recorded numbers when observing from the right. The fourth line contains $N$ integers $U_i$, the recorded numbers when observing from the top. The fifth line contains $N$ integers $D_i$, the recorded numbers when observing from the bottom.

If the given numbers can correspond to some $N \times N$ matrix, output `DA`. Otherwise, output `NE`.

#### Explanation for Sample 1  #### Constraints For $40\%$ of the testdata, $N \le 1000$. For $100\%$ of the testdata, $1 \le N \le 10^5$, $-1 \le L_i, R_i, U_i, D_i \lt N$. #### Notes **The score of this problem follows the original COCI setting, with a full score of $70$.** **Translated from [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #2](https://hsin.hr/coci/archive/2018_2019/contest2_tasks.pdf) _T2 Kocka_.** Translated by ChatGPT 5