Mirko has received an interesting homework assignment: to design his own little processor (Mirkoprocessor). The processor has N registers with indices from 1 to N, and each register holds one unsigned 32-bit integer in the usual binary format (the possible values range from 0 to 2^32 - 1). The processor is capable of executing the following instruction types:

Mirko has already built a model of the processor, and only then realized that he'd forgotten to include an operation to read the contents of a register. Now, his only option is to execute a large number of type 1 and type 2 instructions and infer the register contents from the results. Having executed a sequence of commands, he has asked you to help him derive the initial register contents consistent with the obtained results.

If there are multiple possibilities for the initial register state combination, find the lexicographically smallest one. (If two combinations have equal values in the first K - 1 registers and different values in register K, the lexicographically smaller combination is the one with the smaller value in register K.)

입력

• The first line of input contains two positive integers: N (2 ≤ N ≤ 100 000), the number of registers, and E (1 ≤ E ≤ 100 000), the number of executed instructions.
• The remaining input lines describe the instructions in the order that they were executed by Mirkoprocessor, formatted as described in the table above, one per line. All instructions are legal (the following conditions hold: 1 ≤ K, L ≤ N, 0 ≤ M < 32). Each instruction of type 2 is followed by another line containing a positive integer between 0 and 2^32 - 1, inclusive - the result of that operation (the bitwise XOR value) in base 10.

출력

입출력 예

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

출처:coci/2012-2013/contest3/6 번