17507번 - 시간여행자의 실험기록

시간 여행 능력을 가진 화학자 Lawali는 전설의 마법 포션, 엘릭서를 만드는 실험을 설계했다. 긴 시간의 연구 끝에 Lawali는 특정한 마법 포션들을 정확한 순서로 섞었을 때 엘릭서를 만들 수 있음을 알아냈으나, 필요한 포션의 종류와 그 순서는 알아내지 못했다. 엘릭서를 만드는데 필요한 N가지 포션은 아주 희귀해서, Lawali는 포션을 각 종류별로 한 병밖에 구하지 못했다. Lawali는 엘릭서 제조법을 알아내기 위해 연구를 진행하려 하였으나, 한번 섞인 포션은 다시 분리할 수 없기 때문에 Lawali는 그의 시간 여행 능력을 실험을 위해 사용하기로 결심했다. Lawali가 사용할 수 있는 시간 여행 능력은 다음과 같다.

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

이 연구 과정을 기록하기 위해 Lawali는 두 가지 도구를 사용하기로 결정했다. 하나는 실험실에 그대로 놔둘 공책과 가지고 다니는 수첩이다. 실험실에 놔두는 공책은 JUMP와 LOAD 능력의 영향을 받고, 수첩은 영향을 받지 않는다.

실험은 서로 다른 두 포션을 선택하여 섞는 것으로 이루어진다. 실험에 대한 세부 사항은 다음과 같다.

• 포션을 한 번 섞을 때는 반드시 두 병의 포션만을 섞으며, 섞고 나면 양이 반으로 줄어들어 한병 분량의 새로운 포션이 나온다.
• 정확한 결과가 나오기 위해서 사용해야 하는 최소 양은 포션 한 병 분량이다. 다시 말해 포션두 병을 섞을 때는 남김 없이 모두 투입해야 한다.
• 같은 과정을 거쳐 만든 결과물은 유일하다. 즉 같은 과정을 거쳐 만든 포션은 항상 같으며, 다른 과정을 거쳐 만든 어떤 포션과도 일치하지 않는다. Lawali는 이 포션에 새로운 번호를 붙여 관리한다.

연구는 총 Q번의 과정으로 진행되며, 한번의 연구 과정은 다음과 같다.

1. SAVE 능력을 사용한다. 이 능력을 사용하는 데에는 시간이 소요되지 않는다.
2. 아래 4가지 행동 중 하나를 수행한다.

행동 내용은 다음과 같으며, 각 행동을 수행하고 나서는 하루 동안의 휴식이 필요하다.

• 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 ≤ N, Q ≤ 10⁵)

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

i+1번째 줄의 첫 번째는 행동의 종류를 의미하는 정수 t가 주어진다, (1 ≤ t ≤ 4)

t가 1일 경우 세 정수 a, b, c가 공백으로 구분하여 주어진다. (a ≠ b, b ≠ c, c ≠ a, 1 ≤ a, b, c ≤ 2 × 10⁵)

t가 2인 경우에는 정수 q가 주어진다. (1 ≤ q ≤ 2 × 10⁵)

t가 3인 경우에는 정수 k가 주어진다. (1 ≤ k ≤ Q)

t가 4인 경우에는 정수 j가 주어진다. (1 ≤ j < i)

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

다음 T개의 줄에 걸쳐 해당하는 포션의 번호를 순서대로 출력한다.

다음 P개의 줄에 걸쳐 해당하는 실험의 내용 x y z를 공백으로 구분하여 순서대로 출력한다.