Telephone Plans

Η υπηρεσία τηλεφωνίας «Dormi's Fone Service» είναι πλέον ο μοναδικός πάροχος τηλεφωνικών υπηρεσιών στη χώρα CCOland. Υπάρχουν ~N~ σπίτια στην CCOland, αριθμημένα από το 1 έως το ~N~. Κάθε τηλεφωνική γραμμή συνδέει δύο διαφορετικά σπίτια, έτσι ώστε όλες οι τηλεφωνικές γραμμές που υπάρχουν ή υπήρξαν ποτέ να σχηματίζουν ένα δάσος.

Υπάρχει ένα πρόβλημα με τις τηλεφωνικές γραμμές, καθώς είναι ελαττωματικές και κάθε τηλεφωνική γραμμή υπάρχει μόνο για ένα συγκεκριμένο χρονικό διάστημα. Δύο σπίτια μπορούν να καλέσουν το ένα το άλλο σε μια συγκεκριμένη χρονική στιγμή, αν υπάρχει εκείνη τη στιγμή μια διαδρομή τηλεφωνικών γραμμών που ξεκινά από το ένα σπίτι και καταλήγει στο άλλο.

Θέλουμε να επεξεργαστούμε ~Q~ ερωτήματα των ακόλουθων μορφών:

• 1 x y: Προσθήκη μιας τηλεφωνικής γραμμής μεταξύ των σπιτιών ~x~ και ~y~. Εγγυάται ότι δεν έχει προστεθεί ποτέ προηγουμένως τηλεφωνική γραμμή μεταξύ των σπιτιών ~x~ και ~y~.
• 2 x y: Αφαίρεση της τηλεφωνικής γραμμής μεταξύ των σπιτιών ~x~ και ~y~. Εγγυάται ότι υπάρχει αυτή τη στιγμή τηλεφωνική γραμμή μεταξύ των σπιτιών ~x~ και ~y~.
• 3 t: Υπολογισμός του αριθμού των ζευγών διαφορετικών σπιτιών που μπορούν να επικοινωνήσουν μεταξύ τους κάποια χρονική στιγμή από το τρέχον ερώτημα έως και ~t~ ερωτήματα νωρίτερα.

Για να γίνει πιο σαφές, έστω ~G_q~ η κατάσταση της CCOland μετά το ~q~-οστό ερώτημα, όπου το ~G_0~ είναι η κατάσταση της CCOland πριν από οποιοδήποτε ερώτημα. Αν το τρέχον ερώτημα είναι το ~s~-οστό, πρέπει να μετρήσεις τον αριθμό των ζευγών σπιτιών που είναι συνδεδεμένα σε τουλάχιστον ένα από τα γράφηματα ~G_{s-t}, G_{s-t+1}, \ldots, G_s~.

Επιπλέον, ορισμένες περιπτώσεις ελέγχου ενδέχεται να είναι κρυπτογραφημένες. Στις κρυπτογραφημένες περιπτώσεις, τα ορίσματα ~x~, ~y~ ή ~t~ δίνονται ως το bitwise XOR του πραγματικού ορίσματος με την απάντηση στο τελευταίο ερώτημα τύπου ~3~. Αν δεν έχει προηγηθεί κανένα ερώτημα τύπου ~3~, τα ορίσματα παραμένουν αμετάβλητα.

Είσοδος

Η πρώτη γραμμή της εισόδου θα περιέχει έναν ακέραιο ~E~ (~E \in \{0,1\}~). Η τιμή ~E = 0~ σημαίνει ότι η είσοδος δεν είναι κρυπτογραφημένη, ενώ η τιμή ~E = 1~ σημαίνει ότι η είσοδος είναι κρυπτογραφημένη.

Η δεύτερη γραμμή θα περιέχει δύο ακέραιους αριθμούς, ~N~ και ~Q~, χωρισμένους με κενό, οι οποίοι αντιστοιχούν στον αριθμό των σπιτιών στην CCOland και στον αριθμό των ερωτημάτων, αντίστοιχα.

Καθεμία από τις επόμενες ~Q~ γραμμές θα περιέχει ένα ερώτημα, σύμφωνα με τις παραπάνω προδιαγραφές. Τα ερωτήματα είναι κρυπτογραφημένα ή μη, ανάλογα με την τιμή του ~E~.

Για το ~q~-οστό ερώτημα (~1 \le q \le Q~), εγγυάται ότι, μετά την αποκρυπτογράφηση αν ~E = 1~, ισχύουν τα εξής:

• Για ερωτήματα τύπου ~1~ και ~2~: ~1 \le x,y \le N~.
• Για ερωτήματα τύπου ~3~: ~0 \le t \le q~.

Έξοδος

Για κάθε ερώτημα τύπου ~3~, να εμφανίσετε την απάντηση σε ξεχωριστή γραμμή.

Βαθμολογία

Βαθμοί	Περιορισμοί	Κρυπτογράφηση
~3~	~1 \le N \le 30~, ~1 \le Q \le 150~	~E = 0~
~2~	~1 \le N \le 30~, ~1 \le Q \le 150~	~E = 1~
~4~	~1 \le N \le 2000~, ~1 \le Q \le 6000~	~E = 0~
~2~	~1 \le N \le 2000~, ~1 \le Q \le 6000~	~E = 1~
~4~	~1 \le N \le 100.000~, ~1 \le Q \le 300.000~	~E = 0~
~5~	~1 \le N \le 100.000~, ~1 \le Q \le 300.000~	~E = 1~
~5~	~1 \le N \le 500.000~, ~1 \le Q \le 1.500.000~	~E = 1~

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

input

0
4 12
3 0
1 1 2
3 0
1 1 3
3 0
3 5
2 2 1
3 0
3 8
1 1 4
3 0
3 11

output

0
1
3
3
1
3
3
5

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

Αυτή η περίπτωση δοκιμής δεν είναι κρυπτογραφημένη.

• Για το ~1~ο ερώτημα, κανένα ζεύγος διαφορετικών σπιτιών δεν μπορούσε να επικοινωνήσει.
• Για το ~3~ο ερώτημα, μόνο τα σπίτια ~1~ και ~2~ μπορούσαν να επικοινωνήσουν.
• Για το ~5~ο ερώτημα, το σύνολο των ζευγών που μπορούσαν να επικοινωνήσουν ήταν ~\{(1,2),(1,3),(2,3)\}~.
• Το ~6~ο ερώτημα έχει την ίδια απάντηση.
• Για το ~8~ο ερώτημα, μόνο τα σπίτια ~1~ και ~3~ μπορούσαν να επικοινωνήσουν.
• Για το ~9~ο ερώτημα, υπήρξε μια χρονική στιγμή κατά την οποία τα ζεύγη ~\{(1,2),(1,3),(2,3)\}~ μπορούσαν να επικοινωνήσουν.
• Για το ~11~ο ερώτημα, το σύνολο των ζευγών που μπορούσαν να επικοινωνήσουν ήταν ~\{(1,3),(1,4),(3,4)\}~.
• Για το ~12~ο ερώτημα, το σύνολο των ζευγών που μπορούσαν να επικοινωνήσουν σε οποιαδήποτε προηγούμενη χρονική στιγμή ήταν ~\{(1,2),(1,3),(1,4),(2,3),(3,4)\}~.

input

1
4 12
3 0
1 1 2
3 0
1 0 2
3 1
3 6
2 1 2
3 3
3 9
1 2 7
3 3
3 8

output

0
1
3
3
1
3
3
5

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

Η κρυπτογραφημένη εκδοχή του πρώτου παραδείγματος.