Mirko đã nhận được một bài tập về nhà thú vị: thiết kế bộ xử lý nhỏ của riêng mình (Mirkoprocessor). Bộ xử lý có ~N~ thanh ghi với các chỉ số từ ~1~ đến ~N~ và mỗi thanh ghi chứa một số nguyên ~32~ bit không dấu ở định dạng nhị phân thông thường (các giá trị có thể nằm trong khoảng từ ~0~ đến ~2^{32} – 1~). Bộ xử lý có khả năng thực hiện các loại lệnh sau:

• ~1 K M~ : Xoay các bit của thanh ghi ~K~ theo vị trí ~M~ sang phải, ghi lại kết quả vào thanh ghi ~K~.

Ví dụ: 00000000000000000010001111111011 → (M = 1010) → 111111101100000000000000000001000 (trong cơ số 10: 9211 → (M = 10) → 4 273 995 784)

• ~2 K L~ : Tính toán XOR theo bit của các thanh ghi K và L, xuất kết quả ra bus hệ thống.

Ví dụ: 000000000000000000000001111000111 XOR 000000000000011111000000000000111 = 00000000000001111100001111000000 (trong cơ số 10: 967 XOR 507 911 = 508 864)

Mirko đã xây dựng một mô hình bộ xử lý và chỉ sau đó mới nhận ra rằng anh ấy đã quên đưa vào thao tác để đọc nội dung của một thanh ghi. Bây giờ, lựa chọn duy nhất của anh ta là thực thi một số lượng lớn lệnh loại 1 và loại 2 và suy ra nội dung thanh ghi từ kết quả. Sau khi thực hiện một chuỗi lệnh, anh ta nhờ bạn giúp anh ta lấy được nội dung đăng ký ban đầu phù hợp với kết quả thu được.

Nếu có nhiều khả năng cho sự kết hợp trạng thái thanh ghi ban đầu, hãy tìm cái nhỏ nhất về mặt từ điển. (Nếu hai kết hợp có giá trị bằng nhau trong ~K – 1~ thanh ghi đầu tiên và các giá trị khác nhau trong thanh ghi ~K~, thì kết hợp nhỏ hơn về mặt từ điển là kết hợp có giá trị nhỏ hơn trong thanh ghi ~K~.)

Input

Dòng đầu tiên của đầu vào chứa hai số nguyên dương: ~N~ ~(2 \le N \le 100 000)~, số lượng thanh ghi và ~E~ ~(1 \le E \le 100 000)~, số lượng lệnh được thực hiện.

Các dòng đầu vào còn lại mô tả các lệnh theo thứ tự chúng được thực thi bởi Mirkoprocessor, được định dạng như mô tả trong bảng trên, mỗi dòng một lệnh. Tất cả các hướng dẫn đều hợp pháp (các điều kiện sau giữ: ~1 \le K, L \le N, 0 \le M < 32)~. Mỗi lệnh loại ~2~ được theo sau bởi một dòng khác chứa số nguyên dương từ ~0~ đến ~2^{32} – 1~, bao gồm – kết quả của thao tác đó (giá trị XOR theo bit) trong cơ số ~10~.

Output

Dòng đầu ra đầu tiên và duy nhất phải chứa ~N~ giá trị thanh ghi bắt buộc, cách nhau bằng dấu cách.

Nếu không thể kết hợp các giá trị ban đầu phù hợp với đầu vào, chỉ xuất số ~-1~ để thông báo cho Mirko rằng bộ xử lý của anh ấy có lỗi

Scoring

Trong dữ liệu thử nghiệm có tổng điểm là 64 điểm, các số ~N~ và ~E~ sẽ nhỏ hơn ~1000~.

Sample Input 1

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

Sample Output 1

0 1 2

Sample Input 2

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

Sample Output 2

5 0 14 3

Sample Input 3

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

Sample Output 3

15 6 7 12 5