Description

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.

Input Format

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.

Output Format

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

3
-1 2 0
-1 0 1
2 2 1
0 0 1

DA

3
-1 0 1
-1 2 1
-1 2 -1
1 0 -1

NE

Hint

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 CONTEST #2 T2 Kocka.

Translated by ChatGPT 5