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 sides (there are three colors in total). The vertices are numbered clockwise from $1$ to $N$.

Your task is to find a triangulation of the polygon, i.e., split the polygon into $N-2$ triangles along diagonals, such that for every triangle in the triangulation, its three adjacent sides have three different colors, one of each color.

Input Format

The first line contains the integer $N$ as described in the statement.

The second line is an integer with exactly $N$ digits, describing the colors of the polygon sides. The first digit is the color of side $(1,2)$, the second digit is the color of side $(2,3)$, and so on. The $N$-th digit is the color of side $(N,1)$. Each digit will be one of $1,2,3$.

Output Format

If there is no valid triangulation, output NE and terminate.

Otherwise, output DA on the first line, and then output each diagonal used in the triangulation together with its color on the next $N-3$ lines.

Each line should be in the format X Y C, where $X,Y$ are the two endpoints of the diagonal and $C$ is its color index ($1 \le X,Y \le N, 1 \le C \le 3$). The order of $X$ and $Y$ does not matter.

If there are multiple valid triangulations, output any one of them.

4
1212

DA
1 3 3

4
1213

NE

7
1223121

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

Hint

Constraints

Notes

The scoring for this problem follows the original COCI problem settings, with a full score of $110$.

This problem uses an unofficial Special Judge. You are welcome to hack (you may send a private message or post directly).

Translated from COCI2019-2020 CONTEST #1 T4 Trobojnica.

Translated by ChatGPT 5