题目描述

钟荣准备焚烧多种垃圾。垃圾共有 $K$ 种，依次用整数 $1,2,\ldots,K$ 表示。

最初，队列中有 $N$ 件等待焚烧的垃圾，它们从队首到队尾的种类依次为

之后还可能有新的垃圾加入队尾。

焚烧炉由横向排列的 $M$ 个格子组成，从左到右编号为 $1,2,\ldots,M$。

开始时，从队首依次取出 $\min(N,M)$ 件垃圾，按顺序放入焚烧炉的第 $1$ 到第 $\min(N,M)$ 个格子。若 $N<M$，右侧的一些格子为空。

一次焚烧操作会同时烧掉区间 $[L,R]$ 内所有格子中的垃圾。焚烧完成后，这些格子变空；随后从当前队首开始依次取垃圾，按 $L,L+1,\ldots,R$ 的顺序填入这些格子。若队列在填满区间之前已经为空，剩余格子保持为空。

你需要依次执行 $Q$ 条命令。命令共有四种：

1. 1 L R：对焚烧炉的格子区间 $[L,R]$ 执行一次焚烧操作；
2. 2 i：询问焚烧炉第 $i$ 个格子中垃圾的种类；若该格为空，答案为 $0$；
3. 3 p q：向当前队尾加入 $q$ 件种类为 $p$ 的垃圾；
4. 4 t：为了回收利用，从当前队首删除 $t$ 件垃圾。

执行完全部命令后，还需要输出焚烧炉的最终状态。

输入格式

第一行包含四个整数 $N,M,K,Q$。

第二行包含 $N$ 个整数

接下来 $Q$ 行，每行给出一条命令。命令首先给出类型 $o$：

• 若 $o=1$，随后给出 $L,R$；
• 若 $o=2$，随后给出 $i$；
• 若 $o=3$，随后给出 $p,q$；
• 若 $o=4$，随后给出 $t$。

输出格式

第一行按照命令出现的顺序，输出所有类型 $2$ 询问的答案，答案之间用空格分隔。

第二行输出执行完全部命令后焚烧炉从左到右的状态，共 $M$ 个整数。若某个格子为空，则输出 $0$。

数据范围

对于各种命令：

类型 $4$ 命令满足

保证至少出现一次类型 $2$ 命令。

输入

7 4 3 7
1 1 2 3 3 2 1
2 3
1 2 4
3 2 3
2 2
4 1
1 1 2
2 4

输出

2 3 1
2 2 2 1

说明

初始时焚烧炉为 $[1,1,2,3]$，队列中剩余 $[3,2,1]$。

• 第一次询问第 $3$ 格，得到 $2$；
• 焚烧区间 $[2,4]$ 后，使用队列中的垃圾补入，焚烧炉变为 $[1,3,2,1]$；
• 向队尾加入三个种类为 $2$ 的垃圾，随后询问第 $2$ 格，得到 $3$；
• 从队首删除一个垃圾后，焚烧区间 $[1,2]$，最终焚烧炉为 $[2,2,2,1]$；
• 最后询问第 $4$ 格，得到 $1$。