프로세서 디자인

시간 제한

1초

메모리 제한

128 MB

문제

보섭이는 컴퓨터 구조와 논리 과제로 작은 프로세서를 설계했다. 이 프로세서에는 1번부터 N번까지 번호가 붙은 N개의 레지스터가 있다. 각 레지스터는 일반적인 이진수 형태의 unsigned 32비트 정수를 저장하며, 값의 범위는 0부터 2^32 - 1까지이다. 프로세서는 다음 두 가지 명령을 수행할 수 있다.

명령	설명	동작 예시
`1 K M`	레지스터 K에 저장된 비트를 오른쪽으로 M칸 회전한 뒤, 그 결과를 다시 레지스터 K에 저장한다.	`00000000000000000010001111111011` -> (M = 10) -> `11111110110000000000000000001000` (10진수: `9211` -> `4273995784`)
`2 K L`	레지스터 K와 L에 저장된 값을 XOR한 뒤, 그 결과를 시스템 버스로 출력한다.	`00000000000000000000001111000111` XOR `00000000000001111100000000000111` = `00000000000001111100001111000000` (10진수: `967` XOR `507911` = `508864`)

보섭이는 프로세서를 이미 만들었지만, 레지스터에 저장된 값을 직접 읽는 명령을 만들지 않았다는 사실을 알게 되었다. 따라서 특정 레지스터의 값을 알아내려면 1번 명령과 2번 명령을 적절히 이용해야 한다. 프로세서가 명령을 수행한 순서와 2번 명령이 출력한 값들이 주어질 때, 처음에 각 레지스터에 저장되어 있던 값을 구하시오.

가능한 초기값의 배열이 여러 가지라면, 사전순으로 가장 작은 배열을 출력한다.

입력

첫째 줄에 레지스터의 수 N과 프로세서가 수행한 명령의 수 E가 주어진다. (2 <= N <= 100,000, 1 <= E <= 100,000)

이후 프로세서가 수행한 명령이 순서대로 하나씩 주어진다. 모든 명령은 올바르며 1 <= K, L <= N, 0 <= M < 32를 만족한다. 2번 명령이 주어진 경우에는 그 다음 줄에 시스템 버스가 출력한 결과가 10진수로 주어진다.

출력

첫째 줄에 N개 레지스터의 초기값을 1번 레지스터부터 차례대로 공백으로 구분하여 출력한다.

주어진 출력값들을 만들 수 있는 초기값의 배열이 없다면 -1을 출력한다.