Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:64 MB
统计

题目背景

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

题目描述

给定一个 $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

样例输入 #1

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

样例输出 #1

DA

样例 #2

样例输入 #2

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

样例输出 #2

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$。