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

Trong bài này, chúng ta sẽ quan sát đa giác đều có ~N~ cạnh. Mỗi cạnh và đường chéo của đa giác được tô bằng ~1~ trong ~3~ màu. Các đỉnh của chúng được đánh số từ ~1~ đến ~N~ theo chiều kim đồng hồ. Một cách phân chia tam giác của đa giác là cách chia đa giác thành các tam giác không chồng lên nhau, có các cạnh trùng với cạnh hoặc đường chéo của đa giác.

Cách phân chia tam giác được xem là thỏa mãn nếu mỗi hình trong ~N - 2~ hình tam giác có ~3~ cạnh với ~3~ màu phân biệt. Nhiệm vụ của bạn là tìm một cách phân chia tam giác thỏa mãn.

Input

Dòng đầu tiên chứa số nguyên ~N~.

Dòng thứ hai chứa một số nguyên gồm ~N~ chữ số thể hiện màu sắc của các cạnh đa giác. 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 như vậy cho đến chữ số thứ ~N~ đại diện cho màu của cạnh (~N~, ~1)~. Màu sắc sẽ luôn được ký hiệu bằng các chữ số ~1~, ~2~ và ~3~.

Output

Nếu không có cách phân chia tam giác nào thỏa mãn, in ra NE và kết thúc chương trình.

Nếu có cách phân chia thỏa mãn:

• Dòng đầu tiên in ra DA .
• ~N - 3~ dòng tiếp theo in ra các đường chéo được sử dụng. Mỗi đường chéo được biểu diễn dưới dạng ~X~ ~Y~ ~C~ với ~X~, ~Y~ là ~2~ chỉ số ~2~ đầu mút của đường chéo, ~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 không quan trọng. Nếu có nhiều cách phân chia tam giác thỏa mãn, in ra cách bất kì.

Subtask

• ~10~ test của bài có ~4 \leq N \leq 7~
• ~10~ test của bài có ~4 \leq N \leq 10^3~
• ~10~ test của bài có ~4 \leq N \leq 2 \times 10^5~

Nếu bạn in ra đúng dòng đầu tiên của mỗi test trong ~1~ subtask nhất định, bạn sẽ nhận được ~10\%~ số điểm của subtask đó.

Examples

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