G. Buratsuta 3time limit per test4.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputIn 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.InputEach 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$$$.OutputFor 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$$$.ExampleInput51 151 14 21 1 2 31 42 36 37 7 7 8 8 91 62 54 68 24 4 4 5 5 5 6 61 83 610 51 2 3 3 3 4 4 4 4 51 101 54 96 97 10Output5 1 1 2 7 7 8 8 4 5 5 4 3 4 4 4 NoteIn 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$$$.