시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 15 6 5 38.462%

문제

보섭이는 컴퓨터 구조와 논리 숙제로 작은 프로세서를 디자인했다. 이 프로세서는 총 N개의 레지스터를 가지고 있고, 1번부터 N번까지 번호가 매겨져 있다. 각 레지스터는 unsigned 32비트 정수를 일반적인 이진수 형태로 저장하고 있다. (0 ~ 232-1) 프로세서는 다음과 같은 두 가지 명령을 수행할 수 있다.

명령어 설명 예제
1 K M 레지스터 K에 저장되어 있는 비트를 M만큼 오른쪽으로 회전시킨다음 다시 K에 저장한다. 00000000000000000010001111111011 → (M = 1010) → 11111110110000000000000000001000
(10진법: 9211 → (M = 10) → 4273995784)
2 K L 레지스터 KL에 저장되어 있는 값을 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을 출력한다.

예제 입력

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

예제 출력

0 1 2

힌트