Tenis

Ο Vito λατρεύει το τένις. Σύντομα, θα διοργανώσει ένα τεράστιο τουρνουά με ~N~ παίκτες, που συμβολίζονται με ~1, 2, \cdots, N~. O Vito παρακολουθεί τα στατιστικά των παικτών τα τελευταία δύο χρόνια. Έτσι, έχει καθορίσει τις δυνάμεις τους σε τρεις διαφορετικές επιφάνειες γηπέδου: χώμα, γρασίδι και σκληρό γήπεδο. Δηλαδή για κάθε επιφάνεια έχει καθόρισει τη λίστα κατάταξης των παικτών, από τον πιο δυνατό έως τον πιο αδύναμο παίκτη σε αυτή την επιφάνεια.
Οι κανόνες του τουρνουά του Vito είναι αρκετά ασυνήθιστοι. Θα διεξαχθούν συνολικά ~N - 1~ αγώνες. Σε κάθε αγώνα, δύο παίκτες που δεν έχουν ακόμη αποκλειστεί θα παίξουν μεταξύ τους σε μία συγκεκριμένη επιφάνεια. Ο παίκτης που είναι πιο αδύναμος σε αυτή την επιφάνεια θα χάσει τον αγώνα και έτσι θα αποκλειστεί από το τουρνουά. Ο μόνος παίκτης που θα παραμείνει στο τουρνουά μετά από όλους τους αγώνες ~N - 1~ θα είναι ο νικητής του τουρνουά.
Ο Vito είναι ένας άνθρωπος με επιρροή και μπορεί να χειραγωγήσει το αποτέλεσμα του τουρνουά. Δηλαδή για κάθε αγώνα του τουρνουά, ο Vito μπορεί να επιλέξει τόσο τους παίκτες όσο και την επιφάνεια του γηπέδου του αγώνα. Φυσικά μπορεί να επιλέξει μόνο παίκτες που δεν έχουν αποκλειστεί ακόμα.
Ο Vito συχνά ενημερώνει τα στατιστικά στοιχεία στα βιβλία του με τέτοιο τρόπο που μερικές φορές ανταλλάσσει τις θέσεις δύο παικτών στη λίστα κατάταξης μιας συγκεκριμένης επιφάνειας. Άλλωστε, ο Vito έχει πολλούς φίλους, κάποιοι από τους οποίους έρχονται σε αυτόν με ερωτήσεις όπως αυτή: Ο παίκτης ~X~ είναι ανιψιός μου, υπάρχει πιθανότητα να κερδίσει το τουρνουά (κλείνω το μάτι, κλείνω το μάτι); Για να απαντήσει στις απορίες τους, ο Vito σας έκανε μια προσφορά που είναι δύσκολο να αρνηθείτε. Θα πρέπει να γράψετε ένα πρόγραμμα που θα ενημερώνει τις λίστες κατάταξης και θα απαντά στις ερωτήσεις των φίλων του Vito με βάση τις λίστες κατάταξης εκείνη τη στιγμή.

Είσοδος

Η πρώτη γραμμή περιέχει ακέραιους αριθμούς ~N~ και ~Q (1 \le N,\,Q \le 100\,000)~, τον αριθμό των παικτών και τον αριθμό των γεγονότων.
Κάθε μία από τις επόμενες τρεις γραμμές περιέχει μια μετάθεση ακεραίων ~{1, 2, \cdots, N}~ — την κατάταξη των παικτών σε μια συγκεκριμένη επιφάνεια γηπέδου, από τoν πιο δυνατό έως τον πιο αδύναμο.
Κάθε μία από τις ακόλουθες γραμμές ~Q~ είναι ενός από τους ακόλουθους τύπους:

• "~1~ ~X~", όπου ~1 \le X \le N~ — Ο φίλος του Vito θέλει να μάθει εάν ο παίκτης ~X~ μπορεί να κερδίσει το τουρνουά.
  
• "~2\,P\,A\,B~", όπου ~1 \le P \le 3~ και ~1 \le A \neq B \le N~ — ο Vito έχει συνειδητοποιήσει ότι πρέπει να αλλάξει το θέσεις των παικτών Α και Β στην ~P~-οστή λίστα κατάταξης.

Έξοδος

Για κάθε ερώτημα τύπου ~1~, εκτυπώστε "DA" ή "NE" (κροατικές λέξεις για "ΝΑΙ" και "ΟΧΙ") σε ξεχωριστή γραμμή.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	7	~N \le 15,\,Q \le 10~
2	11	~N \le 1\,000,\,Q \le 10~
3	12	~Q \le 10~
4	21	Όλα τα γεγονότα είναι τύπου ~1~.
5	49	Κανένας επιπλέον περιορισμός.

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

input

4 4
1 2 3 4
2 1 3 4
2 4 3 1
1 1
1 4
2 3 1 4
1 4

output

DA
DA
NE

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

Εάν όλοι οι αγώνες παίζονται στην επιφάνεια του πρώτου γηπέδου, ο παίκτης ~1~ θα κερδίσει το τουρνουά.
Παράδειγμα τουρνουά όπου ο παίκτης ~4~ κερδίζει:
• Οι παίκτες ~3~ και ~4~ παίζουν στην επιφάνεια του τρίτου γηπέδου – ο παίκτης ~4~ κερδίζει.
• Οι παίκτες ~1~ και ~2~ παίζουν στην επιφάνεια του πρώτου γηπέδου – ο παίκτης ~1~ κερδίζει.
• Οι παίκτες ~1~ και ~4~ παίζουν στην επιφάνεια του τρίτου γηπέδου – ο παίκτης ~4~ κερδίζει.
Μετά την ενημέρωση της λίστας κατάταξης του τρίτου γηπέδου (νέα κατάταξη: ~2\,1\,3\,4~), ο παίκτης ~4~ είναι ο πιο αδύναμος από όλους σε όλες τις επιφάνειες και έτσι δεν μπορεί να κερδίσει το τουρνουά.

input

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

output

DA
NE
NE
DA