题目描述

"Everything will be in flames once red, white, and blue start running through your veins." - Slaven Bilić

在该任务中，我们将会研究一些多边形，它们具有 $N$ 条被涂成颜色的边（总共有三种颜色），而顶点的编号沿顺时针依次为 $1$ 至 $N$。

你的任务是找到一个多边形的三角形分割方式，即将一个多边形沿对角线分成 $N-2$ 个三角形，使得多边形的每个三角形的三条邻边都各分别为三种不同的颜色。

输入格式

第一行包含一个题中所提的整数 $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

样例输入 #1

4
1212

样例输出 #1

DA
1 3 3

样例 #2

样例输入 #2

4
1213

样例输出 #2

NE

样例 #3

样例输入 #3

7
1223121

样例输出 #3

DA
1 3 3
3 5 1
5 7 3
7 3 2

提示

数据范围及约定