Problem Description

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

In this task, we will study some polygons with $N$ colored edges (there are three colors in total), and the vertices are numbered clockwise from $1$ to $N$.

Your task is to find a triangulation of the polygon, i.e., dividing the polygon into $N-2$ triangles by drawing diagonals, such that each triangle's three adjacent edges are of three different colors.

Input Format

The first line contains an integer $N$ as mentioned in the problem.

The second line is an integer with $N$ digits, representing the colors of the polygon's edges. The first digit represents the color of edge $(1,2)$, the second digit represents the color of edge $(2,3)$, and so on, with the $N$-th digit representing the color of edge $(N,1)$. Each digit will be one of $1, 2, 3$.

Output Format

If there is no valid way to divide the polygon, output NE and terminate the program.

Otherwise, output DA on the first line and then output $N-3$ lines, each describing a diagonal and its color.

Each line should be in the format X Y C, where $X, Y$ are the two vertices of the diagonal, and $C$ is the color number ($1 \le X, Y \le N, 1 \le C \le 3$), without considering the order of the diagonal's vertices.

If there are multiple valid ways to divide the polygon, output any one of them.

Sample Input and Output

Sample Input #1

4
1212

Sample Output #1

DA
1 3 3

Sample Input #2

4
1213

Sample Output #2

NE

Sample Input #3

7
1223121

Sample Output #3

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

Notes

Data Range and Constraints

Notes

This problem's score is set according to the original COCI contest, with a full score of $110$.

This problem uses a non-official Special Judge, and you are welcome to hack it (either by private message or by posting directly).

The problem is translated from COCI2019-2020 CONTEST #1 T4 Trobojnica.

见题面 Input 部分

见题面 Output 部分