Procesor

Ο Mirko έλαβε μια ενδιαφέρουσα εργασία για το σπίτι: να σχεδιάσει τον δικό του μικρό επεξεργαστή (Mirkoprocessor). Ο επεξεργαστής έχει $N$ καταχωρητές με δείκτες από $1$ έως $N$ και κάθε καταχωρητής περιέχει έναν μη προσημασμένο (unsigned) ακέραιο αριθμό 32-bit στη συνηθισμένη δυαδική μορφή (οι πιθανές τιμές κυμαίνονται από 0 έως $2^{32}-1$). Ο επεξεργαστής είναι σε θέση να εκτελέσει τους ακόλουθους τύπους εντολών:

Τύπος οδηγιών	Περιγραφή	Παράδειγμα
1 K M	Περιστρέψτε τα bit του καταχωρητή K κατά θέσεις M προς τα δεξιά. Γράψτε ξανά το αποτέλεσμα στον καταχωρητή Κ.	00000000000000000010001111111011 $\to (M=1010)\to$ 11111110110000000000000000001000 ($inbase10:9211\to (M=10)\to 4273995784)$
2 K L	Υπολογίστε το bitwise XOR των καταχωρητών Κ και L. Τυπώστε το αποτέλεσμα στο σύστημα του λεωφορείου.	00000000000000000000001111000111 XOR 00000000000001111100000000000111 = 00000000000001111100001111000000 $(inbase10:967XOR507911=508864)$

Ο Mirko έχει ήδη κατασκευάσει ένα μοντέλο του επεξεργαστή και τότε συνειδητοποίησε ότι είχε ξεχάσει να συμπεριλάβει μια λειτουργία για την ανάγνωση των περιεχομένων ενός καταχωρητή. Τώρα, η μόνη του επιλογή είναι να εκτελέσει έναν μεγάλο αριθμό εντολών τύπου 1 και τύπου 2 και να συμπεράνει τα περιεχόμενα του καταχωρητή από τα αποτελέσματα. Έχοντας εκτελέσει μια ακολουθία εντολών, σας ζήτησε να τον βοηθήσετε να τυπώσει τα αρχικά περιεχόμενα του καταχωρητή σύμφωνα με τα ληφθέντα αποτελέσματα.
Εάν υπάρχουν πολλαπλές δυνατότητες για τον συνδυασμό αρχικής κατάστασης καταχωρητή, βρείτε τη λεξικογραφικά μικρότερη. (Αν δύο συνδυασμοί έχουν ίσες τιμές στους πρώτους καταχωρητές $K-1$ και διαφορετικές τιμές στον καταχωρητή $K$, ο λεξικογραφικά μικρότερος συνδυασμός είναι αυτός με τη μικρότερη τιμή στον καταχωρητή $K$.)

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει δύο θετικούς ακέραιους: $N(2\le N\le 100000)$, τον αριθμό των καταχωρητών και $E(1\le Ele100000)$, τον αριθμό των εκτελεσμένων εντολών.
Οι υπόλοιπες γραμμές εισόδου περιγράφουν τις οδηγίες με τη σειρά που εκτελέστηκαν από τον Mirkoprocessor, μορφοποιημένες, όπως περιγράφεται στον παραπάνω πίνακα, μία ανά γραμμή. Όλες οι οδηγίες είναι νόμιμες (ισχύουν οι ακόλουθες προϋποθέσεις: $1\le K,L\le N,0\le M<32)$. Κάθε εντολή τύπου 2 ακολουθείται από μια άλλη γραμμή που περιέχει έναν θετικό ακέραιο μεταξύ 0 και $2^{32}-1$, κλειστό διάστημα – του αποτελέσματος αυτής της λειτουργίας (η τιμή bitwise XOR) στη βάση 10.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει τις απαιτούμενες τιμές καταχωρητή $N$, διαχωρισμένες με κενά.
Εάν δεν υπάρχει δυνατός συνδυασμός αρχικών τιμών που να συνάδουν με την είσοδο, τυπώστε μόνο τον αριθμό -1, για να ειδοποιήσετε τον Mirko ότι ο επεξεργαστής του έχει σφάλμα.

Βαθμολογία

Σε περιπτώσεις δοκιμής συνολικής αξίας 64 πόντων, οι αριθμοί $N$ και $E$ θα είναι μικρότεροι από $1000$.

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

input

3 3
2 1 2
1
2 1 3
2
2 2 3
3

output

0 1 2

input

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

output

5 0 14 3

input

5 6
2 4 2
10
2 5 3
2
2 2 3
1
2 1 4
3
1 3 1
2 3 4
2147483663

output

15 6 7 12 5