„Everything will \(be\) \(in\) flames once red, white and blue start running through your veins” – Slaven Bilić
In this task, we will observe regular polygons that have each of their \(N\) sides colored in one of three
colors and whose vertices are denoted from 1 to \(N\) in a clockwise order. A triangulaton of a polygon
is a decomposition of its area into a set of n\(on-ov\)erlapping triangles whose sides either lie on the sides
of the polygon or its internal diagonals. Of course, in this task, each of the diagonals used for polygon
triangulation is also colored in one of three colors.
The triangulation is said to be patriotic if each of its \(N - 2\) triangles has all three sides of different colors.
Your task is to determine a patriotic triangulation of a given polygon.

Subtask
Score
Constraints
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}\)
If your program correctly outputs the first line in each test case of a certain subtask, you will score 10%
of the points allocated for that subtask.

The first line contains an integer \(N\) from the task description.
The second line contains an integer consisting of \(N\) digits which represent the colors of polygon sides.
More precisely, the first digit represents the color of side (1, 2), the second digit represents the color of
side (2, 3), and so on until the \(N-th\) digit which represents the color of side (N, 1). The colors will always
be denoted with digits 1, 2 and 3.

If there is no patriotic triangulation of the given polygon, output NE and terminate the program. Otherwise,
in the first line output DA and in the next \(N - 3\) lines output each diagonal used in the patriotic triangulation.
Each diagonal should be specified as \(X\) \(Y\) \(C\) where \(X\) and \(Y\) are the endpoints of a diagonal and \(C\) is its
color (\(1 \le X\), \(Y \le N\), \(1 \le C \le 3\)). The order of diagonals in the output is not important. If there are
multiple correct solutions, output any of them.

생성자가 기록되지 않았습니다.

출처 COCI 2019/2020 Contest 1