The happy time is always short. The party comes to an end, and the security guard GYQ can finally rest for a while. He was so miserable in the beginning that he didn't have the energy to complete the final task seriously.

Everyone at the party has a strength value expressed as . They will leave in a specific order. GYQ's original task is to count the maximum strength of the remaining people in all the different intervals, but he does not have the energy to calculate it carefully, so he can only submit a report to the senior management ZX to represent the departure of a particular group of people. As for the maximum value, ZX can only calculate by himself in order to provide different levels of service, which is going to drive him crazy. Please Help him!

Given a report submitted by GYQ, there are two integers N and M, representing that there were N people at the beginning and M leaving records. After that, given an nb array of N numbers, representing each person's strength value. Then followed M lines, each line has two numbers l and r, representing all the people whose number i is in this range (l ≤ i ≤ r) had left. Of course, each person will leave only once and will not return, but due to GYQ's carelessness, the record may be overlap. You need to tell ZX the maximum strength of all the remaining people after each recording. If nobody is here, the answer is 0.

There are multiple test cases. The first line of input contains an integer T (1 ≤ T ≤ 10), indicating the number of test cases. For each test case:

The first line contains two integers N, M (1 ≤ N, M ≤ ), indicating the number of plates.

The second line contains N integers,  ,  ,……,  (1 ≤  ≤ ), indicating the strength value of person numbered i.

Then, in the following next M lines, each line contains two integers ,  (1 ≤  ≤  ≤ N), indicating the j-th range.

Note: This problem has huge input data; it's recommended to use scanf instead of cin to read data in order to avoid time limit exceed.

For each test case, print M lines, each line contains an integer, indicating the maximum strength value of people who still stay here.

1
5 3
2 1 5 3 5
3 4
2 5
2 3

5
2
2