Byang and War Tactics

Limits 500ms, 512 MB

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.

  1. Reverse X Y: Raat selects the sub-array​ of turtles from position XX and YY (inclusive) and reverses them.
  2. Query X Y: Raat asks Byang which Turtle he should attack between position XX and YY (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 XX and YY. But it’s not so easy. Can you please help him?

Input

The first line will contain a positive integer TT (T100T ≤ 100) denoting the number of the test cases. For each test case, the first line will contain two positive integers NN (N1000N ≤ 1000) and QQ (Q1000Q ≤ 1000).

The next line contains NN integers indicating the strength SS of NN turtles. The absolute value of SS will not exceed 101210^{12}.

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

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 XX and YY. See the sample input/output for more details.

Sample

InputOutput
1
5 4
10 3 -10 4 5
2 1 5
2 2 4
1 1 3
2 2 4
Case 1:
4
3
4