Processor Design

Time limit1sMemory limit128 MB

Summary
Reconstruct lexicographically smallest initial 32-bit register values consistent with a sequence of bit-rotation and XOR-output commands, using union-find over bits with XOR relations.
Level

Medium6 of 10

Topics
Union-find, Bit manipulation, Greedy
Solved
No attempts yet

Problem

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.

CommandDescriptionIllustration
1 K MRotate 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 LXOR 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.

Examples3

  1. Example 1

    Input
    3 3
2 1 2
1
2 1 3
2
2 2 3
3
    Expected output
    0 1 2

  2. Example 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
    Expected output
    5 0 14 3

  3. Example 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
    Expected output
    15 6 7 12 5