Problem Description

Mirko has received an interesting assignment: designing his own small processor. The processor has \( n \) registers numbered from \( 1 \) to \( n \), each storing an unsigned 32-bit integer in binary form (possible values range from \( 0 \) to \( 2^{32} - 1 \)).

In addition, the processor is required to perform the following two operations:

• 1 k m: Shift the last \( m \) bits of the binary representation of the number in register \( k \) to the front, and then write the new number back into register \( k \). For example:
  \[ \begin{aligned} &00000000000000000010001111111011 \\ \xrightarrow{m=10} &11111110110000000000000000001000 \end{aligned} \]
• 2 k l: Compute the XOR result of the numbers in registers \( k \) and \( l \) and output the result to the system. For example:
  \[ \begin{aligned} &00000000000000000000001111000111 \\ \text{XOR } &00000000000001111100000000000111 \\ \text{=} &00000000000001111100001111000000 \end{aligned} \]

Mirko realized only after setting up the processor model that he forgot to implement an operation to read the register contents. Therefore, the only thing he can do now is to perform a large number of operations of type 1 and type 2 and deduce the register contents from the results. After executing a series of commands, he asks you to help him derive the initial register contents combination that is consistent with the obtained results.

If there are multiple possible initial register content combinations, you need to find the combination with the smallest lexicographical order (if two combinations have equal values in the first \( k-1 \) registers but differ in register \( k \), the smaller lexicographical combination is the one with the smaller value in register \( k \)).

Input Format

The input consists of several lines.

The first line contains two integers \( n \) and \( e \), representing the total number of registers and the number of operations, respectively.

The following lines describe each operation. For an operation, the first line contains three integers \( op \), \( k \), and \( l \), representing the operation type and its two parameters. If \( op = 2 \), the next line contains an integer representing the result of the previous operation 2, followed by the input for the next operation on the subsequent line. Otherwise, the next line directly contains the input for the next operation.

Refer to the sample input for a better understanding of the input format.

Output Format

If there is no initial register content combination consistent with the input, output a single integer \(-1\). Otherwise, output one line containing \( n \) integers, where the \( i \)-th integer represents the initial number in the \( i \)-th register.

Sample Input and Output

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

Notes/Hints

[Data Range]

For 40% of the data, \( n, e \leq 1000 \).

For all data, \( 2 \leq n \leq 10^5 \), \( 1 \leq e \leq 10^5 \), and the following conditions are satisfied:
- When \( op = 1 \), \( 1 \leq k \leq n \), \( 0 \leq l \leq 32 \).
- When \( op = 2 \), \( 1 \leq k, l \leq n \).

[Problem Source]

This problem is from COCI 2012-2013 CONTEST 3 T6 PROCESOR, configured with the original problem data, with a full score of 160 points.

Provided by Eason_AC for translation and整理.

见题面 Input 部分

见题面 Output 部分