Dirigent

Με παραδοσιακό χορό ολοκληρώνεται η χειμερινή σχολή πληροφορικής. Συμμετέχουν ~n~ μαθητές. Κάθε ένας από αυτούς έχει μια μοναδική ετικέτα μεταξύ ~1~ και ~n~. Αρχικά, ο μαέστρος Krešo διατάζει τους μαθητές να σχηματίσουν έναν κύκλο έτσι ώστε κάθε μαθητής να κρατιέται χέρι-χέρι με δύο άλλους μαθητές.

Η Alenka αναρωτιέται αν είναι δυνατόν να σπάσει ο κύκλος κάνοντας ακριβώς ένα ζευγάρι γειτονικών μαθητών να σταματήσει να κρατιέται χέρι-χέρι και ότι η νεοσυσταθείσα ακολουθία μαθητών ταξινομείται με βάση τις ετικέτες τους. Για παράδειγμα, αν η σειρά τους είναι ~3~ ~4~ ~1~ ~2~, τότε ο κύκλος μπορεί να σπάσει μεταξύ των μαθητών με τις ετικέτες ~4~ και ~1~, αλλά αν η σειρά τους είναι ~2~ ~1~ ~4~ ~3~, τότε δεν υπάρχει τρόπος να σπάσει ο κύκλος με αυτόν τον τρόπο.

Κατά τη διάρκεια της νύχτας ο Krešo πρόκειται να δώσει οδηγίες ~q~. Σε καθεμία από αυτές, πρόκειται να διατάξει δύο μαθητές να ανταλλάξουν θέσεις. Μετά από κάθε ανταλλαγή πρέπει να βοηθήσετε την Alenka να απαντήσει στην ερώτησή της.

Είσοδος

Η πρώτη γραμμή περιέχει δύο ακέραιους αριθμούς ~n~ και ~q~ (~1~ ~\le~ ~n~, ~q~ ~\le~ ~300~ ~000~), τον αριθμό των μαθητών και τον αριθμό των ανταλλαγών.

Η δεύτερη γραμμή περιέχει ~n~ ακέραιους ~a_i~ (~1~ ~\le~ ~a_i~ ~\le~ ~n~), που περιγράφουν την αρχική τοποθέτηση των μαθητών στον κύκλο.

Σε καθεμία από τις επόμενες ~q~ γραμμές υπάρχουν δύο ακέραιοι ~x_i~, ~y_i~ (~1~ ~\le~ ~x_i~, ~y_i~ ~\le~ ~n~, ~x_i~ ~\ne~ ~y_i~), που περιγράφουν την ~i~-οστή οδηγία του Krešo στην οποία οι μαθητές με τις ετικέτες ~x_i~ και ~y_i~ αλλάζουν θέσεις.

Έξοδος

Στην ~i~-οστή των ~q~ γραμμών βάλτε την απάντηση στην ερώτηση της Alenka αφού πραγματοποιηθούν οι ανταλλαγές ~i~. Εάν η απάντηση είναι καταφατική τυπώστε DA, διαφορετικά NE.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	15	~n~, ~q~ ~\le~ ~500~
2	20	~n~, ~q~ ~\le~ ~500~ ~000~
3	35	Κανένας επιπλέον περιορισμός.

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

input

5 2
2 3 4 5 1
1 3
3 1

output

NE
DA

input

4 2
2 3 1 4
4 2
3 4

output

NE
DA

Επεξήγηση του 2ου παραδείγματος:

Οι μαθητές στην αρχή, μετά την πρώτη και μετά τη δεύτερη ανταλλαγή.

input

6 5
2 1 5 6 3 4
3 1
3 4
3 2
4 5
5 4

output

NE
NE
DA
NE
DA