문제
종영이는 여러 가지 쓰레기들을 소각하려고 한다. 쓰레기들은 그 안에서도 여러 종류가 있다. 그 종류는 총 K개가 있는데 이를 순서대로 1, 2, ..., K의 자연수로 표현하자.
대기열에 순서대로 있는 총 N개의 쓰레기를 순서대로 소각해야 하는데, 그 쓰레기의 종류를 순서대로 수열 A1, A2, ..., AN 으로 나타낼 수 있다. 이후에 소각해야 하는 쓰레기들이 대기열 뒤에 더 추가될 수도 있다.
소각로는 M개의 칸이 일렬로 나열되어있는 구조이며 각 칸은 맨 왼쪽부터 오른쪽으로 1번부터 M번까지 번호가 붙어있다. 맨 처음에는 대기열의 앞에서부터 순서대로 min(N, M)개의 쓰레기를 가져와 소각로의 1번 칸부터 min(N, M)번 칸까지 순서대로 놓아둔다. N < M 이면 오른쪽에 빈 칸들이 있을 수 있음에 유의하자.
소각 작업은 L번 칸부터 R번 칸까지(L ≤ R) 연속된 칸에 있는 쓰레기 모두를 한 번에 태우는 식으로 이루어진다. 이렇게 한 번 태우고 나면 L번 칸부터 R번 칸까지는 비게 되는데, 그때 대기열의 앞에서부터 순서대로 쓰레기를 가져와 L번 칸부터 R번 칸까지 채운다. 쓰레기를 가져와 채우다가 더 이상 대기열 상에 쓰레기가 남지 않았으면 그 뒤로는 아무것도 놓지 않는다.
이러한 소각 시스템을 자동화하자. 다음과 같은 4가지 명령을 총 Q번 수행하는 코드를 작성하여라.
소각로 상의 [L, R] 구간에 소각 작업을 진행한다.
i번째 소각로 칸에 놓여있는 쓰레기의 종류를 출력한다.
p번 종류의 쓰레기 q개를 현재 대기열 뒤에 넣는다.
재활용을 위해 현재 대기열 맨 앞의 쓰레기 t개를 제거한다.
또한, 명령을 모두 수행한 뒤 마지막에는 현재 소각로의 상태를 출력해야 한다.
입력
첫 번째 줄에 N, M, K, Q의 값들이 순서대로 입력된다. (1 ≤ N, M, K, Q ≤ 5×105)
두 번째 줄에 N개의 Ai 값들이 주어진다. (1 ≤ Ai ≤ K)
Q개 줄에 명령들이 주어진다. 명령의 의미를 나타내는 수 o가 먼저 주어진다. (1 ≤ o ≤ 4)
o=1 이면 첫 번째 명령을 뜻하며, L과 R이 주어진다. (1 ≤ L ≤ R ≤ M)
o=2 이면 두 번째 명령을 뜻하며, i가 주어진다. (1 ≤ i ≤ M)
o=3 이면 세 번째 명령을 뜻하며, p와 q가 주어진다. (1 ≤ p ≤ K, 1 ≤ q ≤ 106)
o=4 이면 네 번째 명령을 뜻하며, t가 주어진다. (1 ≤ t ≤ 현재 대기열 상 쓰레기의 개수)
두 번째 명령은 한 번 이상 주어짐이 보장된다.
출력
첫 번째 줄에 모든 두 번째 명령에 대한 출력값을 공백으로 구분해 출력한다.
두 번째 줄에 모든 명령을 수행한 후 소각로 상에 남은 쓰레기들의 종류를 왼쪽부터 순서대로 M개의 수로 구분해 출력한다. 소각로 칸이 비어있는 경우에는 그 칸을 나타내는 수로 0을 출력한다.
예제1
1031007
12345778910
113
44
31001000000
4999999
22
113
22
50
10000
예제2
1111
1
21
1
1
예제3
10105000008
12345678910
1110
331415910
1110
124
179
25
35000006
314159
31415950000050000050000050000050000050000000314159