Description

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

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

It is guaranteed for each i = 1, ..., Q - 1, L_i - 3 ≤ L_i+1 and R_i - 3 ≤ 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 three integers L_i, R_i, and K_i, the range and the order of the mode to report for the i-th query.

Constraints

There are five subtasks. For each subtask,

1. N ≤ 2000, Q ≤ 1000.
2. N ≤ 200000, Q ≤ 100000, K_i = 1 for every query, and L_i ≤ L_i+1 and R_i ≤ R_i+1 for each i = 1, ..., Q - 1.
3. N ≤ 200000, Q ≤ 100000, and L_i ≤ L_i+1 and R_i ≤ R_i+1 for each i = 1, ..., Q - 1.
4. N ≤ 200000, Q ≤ 100000, and K_i = 1 for every query.
5. N ≤ 200000, Q ≤ 100000.

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

Output

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

If such value does not exist, print -1 instead.

Sample Input  Download

Sample Output  Download

Tags

Discuss