F. Permutation
time limit per test
6 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given $$$\{a_i\}$$$, a permutation of $$$1...n$$$, you need to perform the following operations:

  • Reverse a subarray indexed by $$$[L,R](1\le L\le R \le |a|)$$$, that is, $$$\forall i\in [L,\frac{L + R}{2}]$$$, swap(a[i],a[R+L-i]).
  • Complement the elements $$$a_i$$$ such that $$$L\le a_i\le R(1\le L\le R \le |a|)$$$, that is, $$$\forall L\le a_i\le R$$$, assign R+L-a[i] to a[i].
  • Increase all the elements that is no less than $$$v(1\le v\le |a|+1)$$$ by $$$1$$$, and then insert $$$v$$$ before the $$$i(1\le i\le |a|)$$$th element. It's clear that the array becomes a permutation of $$$1...|a|+1$$$ after that.
  • Given $$$i(1\le i\le |a|)$$$, print the value of $$$a_i$$$.
  • Given $$$v(1\le v\le |a|)$$$, print the position of $$$v$$$.
Input

This problem contains multiple test cases.

The first line contains a single integer $$$T$$$($$$1 \leq T \leq 10$$$), the number of test cases.

Each test case starts with a line of two integers $$$n,m(1\le n,m\le 10^5)$$$, the initial length of the permutation and the number of operations.

Then follows a line of $$$n$$$ numbers, representing a permutation of $$$1...n$$$.

For the following $$$m$$$ lines, each line is of the following format:

  • 1 L R, asking you to reverse a subarray.
  • 2 L R, asking you to complement certain elements.
  • 3 i v, asking you to insert an element.
  • 4 i, asking you to print the value of the $$$i$$$th element.
  • 5 v, asking you to print the position of $$$v$$$.
Output

For each print operation, print a single integer in a line denoting the answer.

Example
Input
1
5 5
1 2 3 4 5
1 1 3
2 1 5
3 1 2
4 6
5 2
Output
1
1