Zamjene

Ο Dominik έχει οραματιστεί έναν πίνακα θετικών ακεραίων ~p_1,\;\ldots,\;p_n~. Ας υποδηλώσουμε την ταξινομημένη έκδοση αυτού του πίνακα ως ~q_1,\;\ldots,\;q_n~.

Επίσης, οραματίστηκε ένα σύνολο επιτρεπόμενων αντικαταστάσεων. Εάν ένα ζεύγος ~(X,\;Y)~ είναι μέλος του συνόλου των επιτρεπόμενων αντικαταστάσεων, ο Dominik μπορεί να ανταλλάξει τους αριθμούς στις θέσεις ~X~ και ~Y~ στον πίνακα ~p~.

Η Marin δίνει στον Dominik ~Q~ ερωτήματα και καθένα από αυτά είναι ενός από τους παρακάτω τύπους:

1. Αλλάξτε τους αριθμούς στις θέσεις ~A~ και ~B~.
2. Προσθέστε ζεύγος ~(A,\;B)~ στο σύνολο των επιτρεπόμενων αντικαταστάσεων.
   Ο Marin μπορεί να δώσει ζευγάρι ~(A,\;B)~ που βρίσκεται ήδη στο σετ των επιτρεπόμενων αντικαταστάσεων.
3. Δείτε αν είναι δυνατή η ταξινόμηση του πίνακα χρησιμοποιώντας μόνο τις επιτρεπόμενες αντικαταστάσεις;
   Οι αντικαταστάσεις μπορούν να χρησιμοποιηθούν με αυθαίρετη σειρά και κάθε αντικατάσταση μπορεί να γίνει αυθαίρετες φορές.
4. Ας ονομάσουμε ένα ζεύγος θέσεων ~(A,\;B)~ συνδεδεμένο εάν ο αριθμός από τη θέση ~A~ είναι δυνατό να μεταφερθεί στη θέση ~B~ χρησιμοποιώντας μόνο επιτρεπόμενες αντικαταστάσεις.
   Ας ονομάσουμε το σύνολο όλων των θέσεων που συνδέονται με τη θέση ~A~ το σύννεφο του ~A~.
   Ένα σύννεφο είναι καλό αν είναι δυνατό για κάθε θέση ~j~ από το νέφος να επιτυγχάνεται ~p_j = q_j~ χρησιμοποιώντας μια σειρά επιτρεπόμενων αντικαταστάσεων.

Πρέπει να απαντήσετε πόσα ζεύγη διαφορετικών θέσεων ~(A,\;B)~ υπάρχουν έτσι ώστε να ισχύει:

1. Οι θέσεις ~A~ και ~B~ δεν συνδέονται.
2. Το σύννεφο του ~B~ δεν είναι καλό και το σύννεφο του ~B~ δεν είναι καλό.
3. Αν προσθέσουμε ζεύγος ~(A,\;B)~ στο σύνολο των επιτρεπόμενων αντικαταστάσεων, το νέφος του ~A~ (που δημιουργήθηκε συνδέοντας το σύννεφο του ~A~ και το σύννεφο του ~B~) γίνεται καλό.

Σημείωση: Τα ζεύγη ~(A,\;B)~ και ~(B,\;A)~ θεωρούνται πανομοιότυπα ζεύγη.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει ακέραιους αριθμούς ~N~ και ~Q\;(1 \le N, Q \le 1\,000\,000)~.
Η δεύτερη γραμμή εισόδου περιέχει ~N~ ακέραιους ~p_1,\;\ldots,\;p_n~ ~(1 \le p_1,\;\ldots,\;p_n \le 1\,000\,000)~. Κάθε μία από τις ακόλουθες γραμμές ~Q~ περιέχει ένα ερώτημα στην ακόλουθη μορφή:

• Ο πρώτος αριθμός στη γραμμή είναι ο τύπος του ερωτήματος ~T~ από το σύνολο ~\{1,\;2,\;3,\;4\}~.
• Εάν ο τύπος του ερωτήματος ~T~ είναι ~1~ ή ~2~, ακολουθούν δύο διαφορετικοί​ ακέραιοι ~A~ και ~B\;(1 \le A, B \le N)~ που αντιπροσωπεύουν την αντικατάσταση ~(A,\;B)~.

Έξοδος

Για κάθε ερώτημα τύπου ~3~ ή ~4~, τυπώστε την απάντηση σε ξεχωριστή γραμμή.
Η απάντηση στο ερώτημα του τύπου ~3~ είναι "DA" (στα Κροατικά το "ΝΑΙ") ή "NE" (στα Κροατικά το "ΟΧΙ"), χωρίς τα εισαγωγικά και η απάντηση στο ερώτημα του τύπου ~4~ είναι ένας μη αρνητικός ακέραιος από την περιγραφή εργασίας.

Βαθμολογία

Σε περιπτώσεις δοκιμής αξίας 50% των συνολικών πόντων, θα ισχύει ~N, Q \le 1\,000~.

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

input

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

output

1
NE
0
DA

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

Η απάντηση στο πρώτο ερώτημα είναι 1 επειδή το ζεύγος θέσεων ~(2, 3)~ πληροί όλες τις δεδομένες απαιτήσεις.
Η απάντηση στο δεύτερο ερώτημα είναι ΝΕ (όχι) γιατί είναι αδύνατο να μεταφερθούν οι αριθμοί 2 και 3 στις αντίστοιχες θέσεις, επειδή το σύνολο των επιτρεπόμενων αντικαταστάσεων είναι κενό.
Μετά το τρίτο ερώτημα, προσθέτουμε το ζεύγος ~(2, 3)~ στο σύνολο των επιτρεπόμενων αντικαταστάσεων.
Η απάντηση στο τέταρτο ερώτημα είναι τώρα 0 επειδή τα 2 και 3 είναι ήδη συνδεδεμένα και η απάντηση στο πέμπτο ερώτημα είναι DA (ναι), επειδή είναι δυνατή η ταξινόμηση του πίνακα εφαρμόζοντας την επιτρεπόμενη αντικατάσταση ~(2, 3)~.

input

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

output

NE
1
DA
0

input

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

output

NE
2
NE
1
3
DA