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 in the samples.

Samples

A large sample for this problem is provided. Please download it from the "Attachments" section.

10 5
1 2 3 4 5 6 7 8 9 10
1 3 8
2 9 10
3 4 7
4 5 114
1 4 6

3 4 5 6 7 8
8 114 9
Final sequence: 1 2 3 8 114 9 7 6 5 4

10 10
9 6 8 6 7 2 4 6 7 10 
3 2 5
3 6 10
3 9 10
4 8 328728721
4 7 -662061217
4 3 -247898505
3 3 9
3 7 8
1 8 8
2 5 10

-247898505
Final sequence: 9 2 7 10 -662061217 6 -247898505 7 6 328728721

Attachments

Download the attached files from 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$.