Description

 

Given a sequence A = a₁, ..., a_N, answer Q queries.

In the i-th query, you are given two integers L_i and R_i, and have to find the maximum mode of A[L_i...R_i].

It is guaranteed for each i = 1, ..., Q - 1, L_i ≤ L_i+1 and R_i ≤ R_i+1.

 

scanf and printf are recommended over cin and cout to speed up input and output.

 

Input

The first line of the input contains an integer T, the number of testcases.

The first line of each testcase contains two integers N and Q, the length of A and the number of queries.

The second line of each testcase contains N integers, a₁, ..., a_N, the sequence A.

Each of the next Q lines contains two integers L_i and R_i, the range of the subsequence in the i-th query.

 

Constraints

There are six subtasks. For each subtask,

1. N ≤ 20, Q ≤ 10
2. N ≤ 20, Q ≤ 10
3. N ≤ 2000, Q ≤ 1000
4. N ≤ 2000, Q ≤ 1000
5. N ≤ 200000, Q ≤ 100000
6. N ≤ 200000, Q ≤ 100000

In every subtask, 1 ≤ T ≤ 10, 1 ≤ a_i ≤ 10⁹, 1 ≤ L_i ≤ R_i ≤ N.

 

Output

For each query in each testcase, please print the maximum mode of A[L_i...R_i] followed by a newline.

 

Sample Input  Download

Sample Output  Download

Discuss