Trobojnica

"Όλα θα είναι στις φλόγες όταν το κόκκινο, το λευκό και το μπλε αρχίσουν να τρέχουν στις φλέβες σου" - Slaven Bilić

Σε αυτήν την εργασία, θα παρατηρήσουμε κανονικά πολύγωνα που έχουν κάθε μία από τις ~N~ πλευρές τους χρωματισμένη σε ένα από τα τρία χρώματα και των οποίων οι κορυφές συμβολίζονται από το 1 έως το ~N~ με δεξιόστροφη σειρά. Ένα τρίγωνο ενός πολυγώνου είναι η αποσύνθεση της περιοχής του σε ένα σύνολο μη επικαλυπτόμενων τριγώνων των οποίων οι πλευρές είτε βρίσκονται στις πλευρές του πολυγώνου είτε στις εσωτερικές του διαγώνιες. Φυσικά, σε αυτήν την εργασία, κάθε μία από τις διαγώνιες που χρησιμοποιούνται για τον τριγωνισμό πολυγώνων χρωματίζεται επίσης σε ένα από τα τρία χρώματα.

Ο τριγωνισμός λέγεται πατριωτικός εάν καθένα από τα ~N - 2~ τρίγωνά του έχει και τις τρεις πλευρές του σε διαφορετικά χρωμάτα. Το καθήκον σας είναι να προσδιορίσετε έναν πατριωτικό τριγωνισμό ενός δεδομένου πολυγώνου.

Είσοδος

Η πρώτη γραμμή περιέχει έναν ακέραιο ~N~ από την περιγραφή της εργασίας.
Η δεύτερη γραμμή περιέχει έναν ακέραιο αριθμό που αποτελείται από ~N~ ψηφία που αντιπροσωπεύουν τα χρώματα των πλευρών του πολυγώνου. Πιο συγκεκριμένα, το πρώτο ψηφίο αντιπροσωπεύει το χρώμα της πλευράς ~(1,\;2)~, το δεύτερο ψηφίο αντιπροσωπεύει το χρώμα της πλευράς ~(2,\;3)~ και ούτω καθεξής μέχρι το ~N~ -οστό ψηφίο που αντιπροσωπεύει το χρώμα της πλευράς ~(N, 1)~. Τα χρώματα θα συμβολίζονται πάντα με τα ψηφία ~1, 2~ και ~3~.

Έξοδος

Εάν δεν υπάρχει πατριωτικός τριγωνισμός του δεδομένου πολυγώνου, βγάζουμε NE και τερματίζουμε το πρόγραμμα. Διαφορετικά, στην πρώτη γραμμή εξόδου DA και στις επόμενες ~N - 3~ γραμμές εξάγετε κάθε διαγώνιο που χρησιμοποιείται στον πατριωτικό τριγωνισμό. Κάθε διαγώνιος πρέπει να προσδιορίζεται ως ~X\;Y\;C~ όπου ~X~ και ~Y~ είναι τα άκρα μιας διαγώνιου και ~C~ είναι το χρώμα της ~(1 \le X, Y \le N,\;1 \le C \le 3)~. Η σειρά των διαγωνίων στην έξοδο δεν είναι σημαντική. Εάν υπάρχουν πολλές σωστές λύσεις, εξάγετε οποιαδήποτε από αυτές.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	20	~4 \le N \le 11~
2	40	~4 \le N \le 1000~
3	50	~4 \le N \le 2 \cdot 10^5~

Εάν το πρόγραμμά σας εξάγει σωστά την πρώτη γραμμή σε κάθε δοκιμαστική περίπτωση ενός υποπροβλήματος, θα συγκεντρώσετε το 10% των πόντων που διατίθενται για αυτό το υποπρόβλημα.

Παραδείγματα

input

4
1212

output

DA
1 3 3

input

4
1213

output

ΝΕ

input

7
1223121

output

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