시간여행자의 실험기록

시간 여행 능력을 가진 화학자 Lawali는 전설의 마법 포션인 엘릭서를 만드는 실험을 설계했다. 오랜 연구 끝에 Lawali는 특정한 마법 포션들을 정확한 순서로 섞으면 엘릭서가 만들어진다는 사실을 알아냈다. 하지만 필요한 포션의 종류와 순서는 알아내지 못했다.

엘릭서를 만드는 데 필요한 $N$가지 포션은 아주 희귀해서, 각 종류를 한 병씩만 구할 수 있다. Lawali는 엘릭서의 제조법을 알아내려 연구를 진행하고 싶지만, 한번 섞인 포션은 다시 분리할 수 없다. 그래서 그는 실험에 시간 여행 능력을 쓰기로 했다. 그가 쓸 수 있는 능력은 다음과 같다.

1. JUMP: 시간을 $k$일만큼 되돌린다.
2. SAVE: 현재 시간선을 저장한다.
3. LOAD: SAVE로 저장된 시간선 중 하나로 이동한다. 이때 실험실의 상태는 저장했던 당시의 상태와 정확히 같아진다.

Lawali는 이 연구를 기록하기 위해 두 가지 도구를 쓴다. 하나는 실험실에 그대로 두는 공책이고, 다른 하나는 가지고 다니는 수첩이다. 실험실의 공책은 JUMP와 LOAD의 영향을 받지만, 수첩은 영향을 받지 않는다.

실험은 서로 다른 두 포션을 골라 섞는 것으로 이루어진다. 세부 사항은 다음과 같다.

• 포션은 반드시 두 병씩 섞는다. 섞고 나면 양이 반으로 줄어 새 포션 한 병이 나온다.
• 정확한 결과를 얻으려면 최소한 한 병 분량을 써야 한다. 즉 두 병을 섞을 때는 남김없이 모두 넣어야 한다.
• 같은 과정을 거쳐 만든 포션은 항상 같으며, 다른 과정으로 만든 어떤 포션과도 일치하지 않는다. Lawali는 포션마다 새 번호를 붙여 관리한다.

연구는 총 $Q$번의 과정으로 진행된다. 한 번의 연구 과정은 다음과 같다.

1. SAVE 능력을 쓴다. 이 능력을 쓰는 데는 시간이 걸리지 않는다.
2. 아래 네 가지 행동 중 하나를 수행한다.

각 행동을 수행한 뒤에는 하루 동안 쉬어야 한다.

• 1 a b c: 포션 $a$와 포션 $b$를 섞어 만든 새 포션에 번호 $c$를 붙이고, 이 과정을 a b c 형태로 공책에 기록한다.
• 2 q: 현재 존재하는 포션 중 포션 $q$ 또는 포션 $q$를 포함한 포션의 번호를 수첩에 기록한다.
• 3 k: JUMP 능력으로 $k$일 전으로 돌아간다.
• 4 j: LOAD 능력으로 SAVE를 $j$번째로 사용한 시점으로 이동한다.

Lawali를 도와, 실험이 끝난 뒤 수첩과 공책에 기록된 내용을 출력하는 프로그램을 작성하라.

첫째 줄에 $N$과 $Q$가 공백으로 구분되어 주어진다. ($1 \le N, Q \le 10^5$)

둘째 줄부터 $Q$개의 줄에 걸쳐 Lawali가 수행할 행동이 주어진다.

$i+1$번째 줄의 첫 번째 정수 $t$는 행동의 종류이다. ($1 \le t \le 4$)

• $t=1$이면 세 정수 $a$, $b$, $c$가 공백으로 구분되어 주어진다. ($a \ne b$, $b \ne c$, $c \ne a$, $1 \le a, b, c \le 2 \times 10^5$)
• $t=2$이면 정수 $q$가 주어진다. ($1 \le q \le 2 \times 10^5$)
• $t=3$이면 정수 $k$가 주어진다. ($1 \le k \le Q$)
• $t=4$이면 정수 $j$가 주어진다. ($1 \le j < i$)

첫째 줄에 수첩에 기록된 내용의 개수 $T$와 공책에 기록된 내용의 개수 $P$를 공백으로 구분하여 출력한다.

다음 $T$개의 줄에 수첩에 기록된 포션의 번호를 순서대로 출력한다.

다음 $P$개의 줄에 공책에 기록된 실험 내용 x y z를 공백으로 구분하여 순서대로 출력한다.