소각로

종영이는 종류가 $1$부터 $K$까지 번호가 붙은 쓰레기 $N$개를 순서대로 태우려고 한다. 쓰레기의 종류를 순서대로 나열한 수열을 $A_1, A_2, \dots, A_N$이라 하자. 태워야 할 쓰레기가 나중에 대기열의 뒤에 추가될 수도 있다.

소각로에는 $1$번부터 $M$번까지 번호가 붙은 칸 $M$개가 일렬로 있다. 처음에는 대기열 앞에서부터 $\min(N, M)$개를 꺼내어 $1$번 칸부터 순서대로 놓는다. $N < M$이면 오른쪽 칸은 비어 있다.

소각 작업은 연속된 구간 $[L, R]$ ($L \le R$)에 있는 쓰레기를 한 번에 태우는 것이다. 태운 뒤 빈 칸 $[L, R]$을 대기열 앞에서부터 순서대로 꺼내어 $L$번 칸부터 순서대로 채운다. 대기열이 먼저 바닥나면 남은 칸은 비워 둔다.

다음 네 가지 명령을 모두 $Q$번 수행하는 프로그램을 작성하라.

• 소각로의 구간 $[L, R]$에 소각 작업을 진행한다.
• 소각로 $i$번 칸에 놓인 쓰레기의 종류를 출력한다.
• 종류가 $p$인 쓰레기 $q$개를 현재 대기열의 뒤에 넣는다.
• 재활용을 위해 현재 대기열 맨 앞의 쓰레기 $t$개를 제거한다.

모든 명령을 수행한 뒤에는 현재 소각로의 상태도 출력해야 한다.

첫째 줄에 $N, M, K, Q$가 순서대로 주어진다. ($1 \le N, M, K, Q \le 5 \times 10^5$)

둘째 줄에 $N$개의 정수 $A_1, A_2, \dots, A_N$이 주어진다. ($1 \le A_i \le K$)

이어지는 $Q$개의 줄에는 명령이 하나씩 주어진다. 각 줄은 명령의 종류를 나타내는 정수 $o$로 시작한다. ($1 \le o \le 4$)

• $o = 1$이면 첫째 명령이며, $L$과 $R$이 뒤따른다. ($1 \le L \le R \le M$)
• $o = 2$이면 둘째 명령이며, $i$가 뒤따른다. ($1 \le i \le M$)
• $o = 3$이면 셋째 명령이며, $p$와 $q$가 뒤따른다. ($1 \le p \le K$, $1 \le q \le 10^6$)
• $o = 4$이면 넷째 명령이며, $t$가 뒤따른다. ($1 \le t \le$ 현재 대기열에 있는 쓰레기의 개수)

둘째 명령은 한 번 이상 주어짐이 보장된다.

첫째 줄에 둘째 명령에 대한 답을 모두 순서대로 공백으로 구분하여 출력한다. 둘째 줄에 모든 명령을 수행한 뒤 소각로에 남은 쓰레기의 종류를 $1$번 칸부터 $M$번 칸까지 순서대로 공백으로 구분하여 출력한다. 빈 칸은 $0$으로 출력한다.