题目背景

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

题目描述

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

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

提示

样例 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 CONTEST #2 T2 Kocka。