Source

This problem is adapted from Long Long OJ. All rights reserved.

Attention

The time limit for this problem is 10 seconds.

Problem Description

Given a sequence $a_1,a_2,\ldots,a_n$ containing $n$ elements, perform $q$ operations:

• Query (Type 1): Formatted as $\texttt{1 x y}$, which means output $a_x,a_{x+1},\cdots,a_y$ in sequence. It is guaranteed that $1\le y-x+1\le 20$.
• Move (Type 2): Formatted as $\texttt{2 x y}$, which means move $a_x$ to the position right after $a_y$. It is guaranteed that $1\le x < y \le n$.
• Cut and Reverse (Type 3): Formatted as $\texttt{3 x y}$, which means cut the subsequence $a_x,a_{x+1},\cdots,a_y$, reverse it, and append it to the end of the original sequence. It is guaranteed that $1\le x < y \le n$.
• Modify (Type 4): Formatted as $\texttt{4 x y}$, which means update $a_x$ to $y$ (i.e., $a_x \leftarrow y$). It is guaranteed that $1\le x \le n$ and $-10^9\le y\le 10^9$.

Input Format

• The first line contains two integers $n$ and $q$, representing the length of the sequence and the number of queries respectively;
• The second line contains $n$ integers $a_1,a_2,\cdots,a_n$;
• Lines $3$ to $q+2$ each contain one query.

Output Format

For each Query (Type 1) operation, output a line containing $y-x+1$ integers separated by spaces.

In particular, after all operations on the sequence are completed, output a line containing $n$ integers, with the specific format shown below:

Final sequence: a[1] a[2] ... a[n]

Samples

Download the sample files from the link below.

Attachments

Download the files here.

Data Range

The information for each test case is shown in the table below (this problem does not use bundled testing):

• Special Property $\mathcal A$: The data is random.
• Special Property $\mathcal B$: Only Query (Type 1) and Modify (Type 4) operations are present.
• Special Property $\mathcal C$: Only Move (Type 2) operations are present.
• Special Property $\mathcal D$: Only Cut and Reverse (Type 3) operations are present.
• Special Property $\mathcal /$: No special properties.

For $100\%$ of the data, $1\le n,q\le 2 \times 10^5$ and $-10^9\le a_i\le 10^9$.