Description

Mirko received an interesting assignment: to design his own small processor. This processor has $n$ registers numbered from $1$ to $n$. Each register stores an unsigned $32$-bit integer in binary form (possible values are in $[0,2^{32}-1]$).

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

• 1 k m: Move the last $m$ bits of the binary representation of the number in register $k$ to the very front as a whole, and then write the resulting new number back into register $k$. For example:

$$\begin{aligned}&00000000000000000010001111111011\\\xrightarrow{m=10}&11111110110000000000000000001000\end{aligned}$$

• 2 k l: Compute the XOR of the number in register $k$ and the number in register $l$, and output the result to the system. For example:

$$\begin{aligned}&00000000000000000000001111000111\\ \underline{\text{XOR }} & \underline{00000000000001111100000000000111}\\ \text{= }&00000000000001111100001111000000\end{aligned}$$

Only after building the processor model did Mirko realize that he forgot to implement an operation to read the contents of a register. Therefore, the only thing he can do now is to execute operations $1$ and $2$ many times, and infer the register contents from the results. After executing a sequence of commands, he asks you to help him derive a set of initial register contents that is consistent with the obtained results.

If there are multiple possible sets of initial register states, you need to find the lexicographically smallest set (if two sets have equal values in the first $k-1$ registers but different values in register $k$, then the lexicographically smaller set is the one with the smaller value in register $k$).

Input Format

The input consists of multiple lines.

The first line contains two integers $n,e$, representing the total number of registers and the number of operations.
The next lines describe each operation. For an operation, first read a line with three integers $\textit{op},k,l$, representing the operation type and its two parameters. If $op=2$, then read one more line containing one integer, which is the result produced by the operation $2$ on the previous line, and then proceed to the next operation on the following line. Otherwise, proceed directly to the next operation on the next line.

If you cannot understand the input format well, please refer to the sample to better understand this part.

Output Format

If there is no set of initial register contents consistent with the input, output a single line with the integer $-1$. Otherwise, output one line with $n$ integers, where the $i$-th integer is the number initially stored in register $i$.

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

0 1 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

5 0 14 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

15 6 7 12 5

Hint

Constraints

For $40\%$ of the testdata, $n,e\leqslant 1000$.
For all testdata, $2\leqslant n\leqslant 10^5$, $1\leqslant e\leqslant 10^5$. Also:

• When $op=1$, $1\leqslant k\leqslant n$, $0\leqslant l\leqslant 32$.
• When $op=2$, $1\leqslant k,l\leqslant n$.

Source

This problem is from COCI 2012-2013 CONTEST 3 T6 PROCESOR. Using the original testdata configuration, the full score is $160$.

Translated and organized by Eason_AC.

Translated by ChatGPT 5