시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (언어별 추가 시간 없음) 512 MB 151 32 29 27.358%

문제

종영이는 여러 가지 쓰레기들을 소각하려고 한다. 쓰레기들은 그 안에서도 여러 종류가 있다. 그 종류는 총 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

10 3 100 7
1 2 3 4 5 7 7 8 9 10
1 1 3
4 4
3 100 1000000
4 999999
2 2
1 1 3
2 2

예제 출력 1

5 0
100 0 0

예제 입력 2

1 1 1 1
1
2 1

예제 출력 2

1
1

예제 입력 3

10 10 500000 8
1 2 3 4 5 6 7 8 9 10
1 1 10
3 314159 10
1 1 10
1 2 4
1 7 9
2 5
3 500000 6
1 2 8

예제 출력 3

314159
314159 500000 500000 500000 500000 500000 500000 0 0 314159