P7309 [COCI 2018/2019 #2] Kocka

在儿童游乐场里，编者被一个由金属横杠组成的立方体所吸引，于是他想出了一个有趣的问题。这里是二维的版本。

给定一个 $N \times N$ 的矩阵。有些区域被堵塞，而有些区域是空白的。在观察的过程中，他从 $4$ 个方向对该矩阵进行观察。先从左侧开始，记录下每一行的第一个堵塞处前有几排是空出的。如果没有堵塞，则记下 $-1$。接着他如法炮制，分别从右侧、上方和下方进行观察并记录。 这样，他总共写下了 $4N$ 个数字，其中每个方位均写下了 $N$ 个数字。然而，未知的恶棍摧毁了矩阵，他所剩的只有他写下的数字。 编者想问你他写的数字是否存在错误，即是否可以通过这些数字还原出一个 $N \times N$ 的矩阵。

第一行输入正整数 $N$，表示矩阵的规模。 第二行包含 $N$ 个整数 $L_i$，表示从左侧观察所记下的数字。 第三行包含 $N$ 个整数 $R_i$，表示从右侧观察所记下的数字。 第四行包含 $N$ 个整数 $U_i$，表示从上方观察所记下的数字。 第五行包含 $N$ 个整数 $D_i$，表示从下方观察所记下的数字。

如果给定的数字可以还原出一个 $N \times N$ 的矩阵，则输出 `DA`，否则输出 `NE`。

#### 样例 1 解释  #### 数据规模与约定 对于 $40\%$ 的数据，$N \le 1000$。 对于 $100\%$ 的数据，$1 \le N \le 10^5$，$-1 \le L_i,R_i,U_i,D_i \lt N$。 #### 说明 **本题分值按 COCI 原题设置，满分 $70$。** **题目译自 [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #2](https://hsin.hr/coci/archive/2018_2019/contest2_tasks.pdf) _T2 Kocka_。**