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$$$.

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$$$.

Buratsuta 3

Examples