Incinerator

Jongyeong wants to burn $N$ pieces of waste in order. There are $K$ kinds, numbered $1$ through $K$. The kinds in queue order form the sequence $A_1, A_2, \dots, A_N$. More waste to burn can be added to the back of the queue later.

The incinerator has $M$ cells in a row, numbered $1$ to $M$ from the left. At the start, take $\min(N, M)$ pieces from the front of the queue and place them in order into cells $1$ through $\min(N, M)$. If $N < M$, the cells on the right stay empty.

One burning operation burns everything in a consecutive interval $[L, R]$ ($L \le R$) at once. After burning, cells $[L, R]$ are empty, so refill them in order from cell $L$ with pieces taken in order from the front of the queue. If the queue runs out while refilling, leave the remaining cells empty.

Write a program that performs the following four kinds of commands $Q$ times in total.

• Burn the interval $[L, R]$ of the incinerator.
• Print the kind in cell $i$ of the incinerator.
• Append $q$ pieces of kind $p$ to the back of the current queue.
• Remove $t$ pieces from the front of the current queue for recycling.

After all commands, also print the current state of the incinerator.

The first line holds $N, M, K, Q$ in order. ($1 \le N, M, K, Q \le 5 \times 10^5$)

The second line holds $N$ integers $A_1, A_2, \dots, A_N$. ($1 \le A_i \le K$)

Each of the next $Q$ lines holds one command. Every line starts with an integer $o$ giving the command kind. ($1 \le o \le 4$)

• If $o = 1$, it is the first command, followed by $L$ and $R$. ($1 \le L \le R \le M$)
• If $o = 2$, it is the second command, followed by $i$. ($1 \le i \le M$)
• If $o = 3$, it is the third command, followed by $p$ and $q$. ($1 \le p \le K$, $1 \le q \le 10^6$)
• If $o = 4$, it is the fourth command, followed by $t$. ($1 \le t \le$ the number of pieces currently in the queue)

The second command appears at least once.

On the first line, print the answers to all second commands in order, separated by spaces. On the second line, print the kinds left in the incinerator from cell $1$ to cell $M$ in order, separated by spaces, after all commands. Print $0$ for an empty cell.