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 and (inclusive) and reverses them.
Query X Y: Raat asks Byang which Turtle he should attack between position and (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 and . But it’s not so easy. Can you please help him?
The first line will contain a positive integer () denoting the number of the test cases. For each test case, the first line will contain two positive integers () and ().
The next line contains integers indicating the strength of turtles. The absolute value of will not exceed .
After that lines follow which are the operations Raat performs. Each operation is made of 3 positive integers:
A X Y. is either 1 or 2:
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 and . See the sample input/output for more details.
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