“一旦红、白、蓝在你的血管中流淌，一切都将燃烧。” —— 斯拉文·比利奇 (Slaven Bilić)
在本题中，我们考虑一个正 $N$ 边形，其 $N$ 条边中的每一条都涂有三种颜色之一，且其顶点按顺时针方向依次标记为 $1$ 到 $N$。多边形的三角剖分是指将其面积分解为一组互不重叠的三角形，这些三角形的边要么位于多边形的边上，要么位于其内部对角线上。当然，在本题中，用于多边形三角剖分的每条对角线也涂有三种颜色之一。
如果一个三角剖分满足其 $N - 2$ 个三角形的每一个，其三条边的颜色都互不相同，则称该三角剖分是“爱国的”（patriotic）。
你的任务是确定给定多边形的一个爱国三角剖分。
输入格式
第一行包含任务描述中的整数 $N$。
第二行包含一个由 $N$ 个数字组成的整数，表示多边形各边的颜色。更具体地，第一个数字表示边 $(1, 2)$ 的颜色，第二个数字表示边 $(2, 3)$ 的颜色，依此类推，直到第 $N$ 个数字表示边 $(N, 1)$ 的颜色。颜色将始终用数字 1、2 和 3 表示。
输出格式
如果给定的多边形不存在爱国三角剖分，则输出 NE 并结束程序。
否则，在第一行输出 DA，并在接下来的 $N - 3$ 行中输出爱国三角剖分中使用的每条对角线。
每条对角线应表示为 X Y C，其中 $X$ 和 $Y$ 是对角线的端点，$C$ 是其颜色（$1 \le X, Y \le N$，$1 \le C \le 3$）。
输出中对角线的顺序并不重要。如果存在多个正确解，输出其中任意一个。
子任务
| 子任务 | 分数 | 数据范围 |
|---|---|---|
| 1 | 20 | $4 \le N \le 11$ |
| 2 | 40 | $4 \le N \le 10^3$ |
| 3 | 50 | $4 \le N \le 2 \cdot 10^5$ |
如果你的程序在某个子任务的每个测试用例中都正确输出了第一行，你将获得该子任务所分配分数的 10%。
样例
输入样例 1
4 1212
输出样例 1
DA 1 3 3
输入样例 2
4 1213
输出样例 2
NE
输入样例 3
7 1223121
输出样例 3
DA 1 3 3 3 5 1 5 7 3 7 3 2