Byang is learning about War Tactics from Raat, a famous martial arts master, who has successfully trained a few Ninja Turtles. Byang is hoping to gain some wisdom from Raat for the upcoming war.

Raat said to Byang, “Only fools attack enemy where they are strong; and those who are careless attack enemy where they are weak and fall in trap. Follow the middle path and middle path only”.

After stating his philosophy, Raat suggested playing a game to help Byang understand things better. Raat asked some of his Turtle Disciples to stand in a line.

There are N turtles in total. They are enemies in this game. Each turtle Ti has strength Si. Now Raat is going to do two things.

Reverse X Y: Raat selects the sub-array of turtles from position $X$ and $Y$ (inclusive) and reverses them.

Query X Y: Raat asks Byang which Turtle he should attack between position $X$ and $Y$ (inclusive)? Byang needs to tell Raat the strength of the Turtle which he should attack.

Byang is pretty smart. So he quickly realized that for each query he should find the median of turtles' strengths between position $X$ and $Y$. But it’s not so easy. Can you please help him?

Input

The first line will contain a positive integer $T$ ($T ≤ 100$) denoting the number of the test cases. For each test case, the first line will contain two positive integers $N$ ($N ≤ 1000$) and $Q$ ($Q ≤ 1000$).

The next line contains $N$ integers indicating the strength $S$ of $N$ turtles. The absolute value of $S$ will not exceed $10^{12}$.

After that $Q$ lines follow which are the operations Raat performs. Each operation is made of 3 positive integers: A X Y. $A$ is either 1 or 2:

If $A$ is 1 then it is an operation of type 1.

If $A$ is 2 then it is an operation of type 2. $X$ and $Y$ will follow these constraints: $X ≤ Y$, $1 ≤ X$, $Y ≤ N$ and $Y - X + 1$ will be odd for type two operation.

Output

For each test case print a line with the case number. Then for each operation of type 2 print a single integer which is the median strength of turtles between $X$ and $Y$. See the sample input/output for more details.