“Everything will be in flames once red, white and blue start running through your veins” – Slaven Bilić

Trong bài toán này, chúng ta sẽ quan sát các đa giác đều với ~N~ cạnh, mỗi cạnh được tô bằng một trong ba màu và các đỉnh của đa giác được đánh số từ ~1~ đến ~N~ theo chiều kim đồng hồ. Phép phân chia tam giác của một đa giác là sự phân chia diện tích của nó thành tập hợp các tam giác không chồng chéo nhau, với các cạnh nằm trên các cạnh của đa giác hoặc các đường chéo bên trong của nó. Tất nhiên, trong bài toán này, mỗi đường chéo dùng để phân chia tam giác của đa giác cũng được tô một trong ba màu.

Phép phân chia tam giác được gọi là yêu nước nếu mỗi trong số ~N - 2~ tam giác của nó đều có ba cạnh với ba màu khác nhau.

Nhiệm vụ của bạn là xác định một phép phân chia tam giác yêu nước của một đa giác cho trước.

Input

• Dòng đầu tiên chứa một số nguyên ~N~ từ mô tả bài toán.
• Dòng thứ hai chứa một số nguyên gồm ~N~ chữ số đại diện cho màu sắc của các cạnh của đa giác. Cụ thể, chữ số đầu tiên đại diện cho màu của cạnh ~(1, 2)~, chữ số thứ hai đại diện cho màu của cạnh ~(2, 3)~, và cứ tiếp tục cho đến chữ số thứ ~N~ đại diện cho màu của cạnh ~(N, 1)~. Các màu sẽ luôn được biểu diễn bằng các chữ số ~1, 2~ và ~3~.

Output

• Nếu không có phép phân chia tam giác yêu nước của đa giác cho trước, in ra ~NE~ và kết thúc chương trình.
• Ngược lại, dòng đầu tiên in ra ~DA~ và trong các dòng tiếp theo in ra mỗi đường chéo dùng trong phép phân chia tam giác yêu nước. Mỗi đường chéo được xác định là ~X~ ~Y~ ~C~, trong đó ~X~ và ~Y~ là các điểm cuối của đường chéo và ~C~ là màu của nó ~(1 \leq X, Y \leq N, 1 \leq C \leq 3)~. Thứ tự của các đường chéo trong đầu ra không quan trọng. Nếu có nhiều giải pháp đúng, in ra bất kỳ giải pháp nào trong số đó.

Chú ý

• ~20~ điểm thỏa mãn ~4 \leq N \leq 11~.
• ~40~ điểm thỏa mãn ~4 \leq N \leq 10^3~
• ~50~ điểm thỏa mãn ~4 \leq N \leq ~2 \times 10^5~.

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