"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 clockwise order. A triangulation of a polygon is a decomposition of its area into a set of non-overlapping 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.

Input Specification

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~.

Output Specification

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.

Constraints

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.

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