Background

Inversion pairs are really fun.

Problem Description

You need to maintain a sequence and support the following $4$ operations:

1. Swap two intervals.
2. Move an interval backward to between the $k$-th number and the $(k+1)$-th number.
3. Insert a number $x$ at the end.
4. Insert a number $x$ at the beginning.

After each operation, the indices of the numbers are re-numbered in the new sequence from the first number to the $k$-th number as $1$ to $k$.

Now, after every operation, please output the parity of the number of inversion pairs in the entire sequence.

Input Format

The first line contains two positive integers $n,m$, representing the length of the initial sequence and the number of operations.

The next line contains $n$ positive integers $a_1,a_2,\dots,a_n$, representing the initial sequence.

The next $m$ lines each start with an integer $t$ indicating the operation type, followed by:

• If $t=1$, input four positive integers $l_1,r_1,l_2,r_2$, meaning to swap the whole interval $[l_1,r_1]$ with the whole interval $[l_2,r_2]$. It is guaranteed that $l_1\le r_1< l_2\le r_2$.
• If $t=2$, input three positive integers $l,r,k$, meaning to move the interval $[l,r]$ to between the $k$-th number and the $(k+1)$-th number of the sequence. It is guaranteed that $r<k$.
• If $t=3$, input one positive integer $x$, meaning to insert $x$ at the end of the sequence.
• If $t=4$, input one positive integer $x$, meaning to insert $x$ at the beginning of the sequence.

Output Format

After each operation, if the number of inversion pairs is even, output even; otherwise output odd.

6 4
4 3 5 7 2 6
1 1 1 2 2
2 1 1 3
3 11
4 1

odd
odd
odd
odd

Hint

[Sample Explanation]

In the first operation, swap interval $[1,1]$ and interval $[2,2]$. The sequence becomes 3 4 5 7 2 6.

In the second operation, move interval $[1,1]$ to between the $3$-rd and the $4$-th numbers. The sequence becomes 4 5 3 7 2 6.

In the third operation, insert $11$ at the end of the sequence. The sequence becomes 4 5 3 7 2 6 11.

In the fourth operation, insert $1$ at the beginning of the sequence. The sequence becomes 1 4 5 3 7 2 6 11.

[Constraints]

"This problem uses bundled testdata."

• $\texttt{Subtask 1(10 pts): }n,m\le 10^2$.
• $\texttt{Subtask 2(15 pts): }n,m\le 10^3$.
• $\texttt{Subtask 3(20 pts): }$Operations 1 and 2 do not appear.
• $\texttt{Subtask 4(20 pts): }$Operations 3 and 4 do not appear.
• $\texttt{Subtask 5(35 pts): }$No special restrictions.

For $100\%$ of the testdata, $1\le n,m \le 2\times 10^5$, $a_i\le 2\times10^6$, and it is guaranteed that all numbers in $a$ are distinct at any time.

Translated by ChatGPT 5