G. Buratsuta 3
time limit per test
4.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the ruthless world of Blue Lock, Buratsuta 3 is a trio selected to overthrow the reigning champions and lead the Japan U-20 team to glory. Sae Itoshi has already secured his place as the first participant; the remaining two spots will be contested in the tough Side-B selection.

To test the strategic abilities of the candidates, Buratsuta has posed the following challenge:

You are given an array of $$$n$$$ integers called "performance records" and $$$q$$$ queries. Each query specifies a subarray $$$[l, r]$$$. In this subarray, find all record values that occur strictly more than $$$\lfloor\tfrac{r - l + 1}{3}\rfloor$$$ times.

Input

Each test consists of several test cases.

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The following describes the test cases.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ $$$(1 \le n, q \le 2\cdot10^5)$$$ — the number of records and the number of queries.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — the performance records.

Each of the following $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ $$$(1 \le l \le r \le n)$$$ — the boundaries of the query.

It is guaranteed that the sum of $$$n$$$ and sum of $$$q$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each query, output in one line all record values (in sorted order) that occur strictly more than $$$\lfloor\tfrac{r - l + 1}{3}\rfloor$$$ times in the segment $$$[l, r]$$$. If there are no such values, output $$$-1$$$.

Example
Input
5
1 1
5
1 1
4 2
1 1 2 3
1 4
2 3
6 3
7 7 7 8 8 9
1 6
2 5
4 6
8 2
4 4 4 5 5 5 6 6
1 8
3 6
10 5
1 2 3 3 3 4 4 4 4 5
1 10
1 5
4 9
6 9
7 10
Output
5 
1 
1 2 
7 
7 8 
8 
4 5 
5 
4 
3 
4 
4 
4
Note

In the second test case, the array is $$$a=[1,1,2,3]$$$ and there are two queries:

  • Query $$$(l,r)=(1,4)$$$: The length of the segment $$$len=r-l+1=4$$$, the threshold $$$\bigl\lfloor \frac{len}{3}\bigr\rfloor+1 = 2$$$. Occurrences of numbers: $$$1\!\to\!2$$$, $$$2\!\to\!1$$$, $$$3\!\to\!1$$$. Only the number $$$1$$$ occurs at least $$$2$$$ times, so the answer is: $$$1$$$.
  • Query $$$(l,r)=(2,3)$$$: The length of the segment $$$len=2$$$, the threshold $$$\bigl\lfloor \frac{len}{3}\bigr\rfloor+1 = 1$$$. Numbers $$$1$$$ and $$$2$$$ occur once each, so the answer is: $$$1 \; 2$$$.

In the fourth test case, the array is $$$a=[4,4,4,5,5,5,6,6]$$$ and there are two queries:

  • Query $$$(l,r)=(1,8)$$$: The length of the segment $$$len = 8$$$, the threshold $$$\bigl\lfloor \dfrac{len}{3} \bigr\rfloor + 1 = 3$$$.

    Occurrences of numbers: $$$4 \!\to\! 3$$$, $$$5 \!\to\! 3$$$, $$$6 \!\to\! 2$$$. Only the numbers $$$4$$$ and $$$5$$$ occur at least $$$3$$$ times, so the answer is: $$$4 \; 5$$$.

  • Query $$$(l,r)=(3,6)$$$: The length of the segment $$$len = 4$$$, the threshold $$$\bigl\lfloor \dfrac{len}{3} \bigr\rfloor + 1 = 2$$$.

    Occurrences of numbers: $$$4 \!\to\! 1$$$, $$$5 \!\to\! 3$$$. Only the number $$$5$$$ occurs at least $$$2$$$ times, so the answer is: $$$5$$$.