cho.shProcessor Design
Time limit1sMemory limit128 MBProblem
Boseop designed a small processor for a computer architecture and logic assignment. The processor has N registers numbered from 1 to N. Each register stores an unsigned 32-bit integer in the usual binary representation, from 0 to 2^32 - 1. The processor supports the following two commands.
| Command | Description | Illustration |
|---|---|---|
1 K M | Rotate the bits stored in register K to the right by M positions, then store the result back in register K. | 00000000000000000010001111111011 -> (M = 10) -> 11111110110000000000000000001000 (decimal: 9211 -> 4273995784) |
2 K L | XOR the values stored in registers K and L, then output the result to the system bus. | 00000000000000000000001111000111 XOR 00000000000001111100000000000111 = 00000000000001111100001111000000 (decimal: 967 XOR 507911 = 508864) |
The processor has already been built, but it has no command for directly reading the value stored in a register. Therefore, the only way to determine a register value is by using commands 1 and 2. Given the order of commands that were executed and every output produced by command 2, reconstruct the values initially stored in all registers.
If multiple initial register sequences are possible, output the lexicographically smallest one.
Input
The first line contains the number of registers N and the number of commands E executed by the processor. (2 <= N <= 100,000, 1 <= E <= 100,000)
Each command is then given in order. Every command is valid and satisfies 1 <= K, L <= N and 0 <= M < 32. Whenever a command of type 2 is given, the next line contains the decimal value output on the system bus.
Output
Print the initial values of the N registers from register 1 to register N, separated by spaces.
If no initial register sequence can produce the given outputs, print -1.