我又在立方体里了！ 我又在立方体里了！

清晨，在看着孩子们玩耍的游乐场时，本题的作者注意到一个有趣的物体：一个由金属条制成的立方体，它由许多单位大小的金属条立方体组成。

在观察这个立方体时，他脑海中浮现出一个有趣的问题。由于没有人喜欢涉及三维物体的问题，以下是该问题的二维版本：

给你一个 $N \times N$ 的矩阵（即正方形）。正方形中的一些格子是障碍格，一些是空格。作者从正方形的四个方向观察它。首先，他从左侧观察正方形，对于其 $N$ 行中的每一行，他记录了从左边看过去，在第一个障碍格之前有多少个空格。如果某一行中没有障碍格，他就写下数字 $-1$。然后，他按照右侧、上方和下方的顺序，重复相同的步骤观察正方形。

通过这种方式，他总共写下了 $4N$ 个数字，即正方形的每个方向都写下了 $N$ 个数字。然而，神秘的恶棍摧毁了他的正方形，只留下了他写下的那些数字。本题的作者想知道这些数字是否有意义，即是否可能构造出一个正方形，使得通过上述步骤可以得到完全相同的数字序列。

输入格式

第一行包含一个正整数 $N$ ($1 \le N \le 100\,000$)，表示正方形的维度。

第二行包含 $N$ 个整数 $L_i$ ($-1 \le L_i < N$)，表示从左侧观察正方形得到的数字，顺序为第 $1$ 行到第 $N$ 行。

第三行包含 $N$ 个整数 $R_i$ ($-1 \le R_i < N$)，表示从右侧观察正方形得到的数字，顺序为第 $1$ 行到第 $N$ 行。

第四行包含 $N$ 个整数 $U_i$ ($-1 \le U_i < N$)，表示从上方观察正方形得到的数字，顺序为第 $1$ 列到第 $N$ 列。

第五行包含 $N$ 个整数 $D_i$ ($-1 \le D_i < N$)，表示从下方观察正方形得到的数字，顺序为第 $1$ 列到第 $N$ 列。

输出格式

如果可以构造出满足给定条件的正方形，输出 DA（克罗地亚语中的“是”，不加引号），否则输出 NE（克罗地亚语中的“否”）。

子任务

对于 $40\%$ 的测试数据，满足 $N \le 1000$。

样例

输入 1

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

输出 1

DA

输入 2

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

输出 2

NE

说明

样例 1 说明：