G. Buratsuta 3
ограничение по времени на тест
4.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В безжалостном мире Blue Lock, Buratsuta 3 — это трио, отобранное для того, чтобы свергнуть действующих чемпионов и привести команду Японии U-20 к славе. Сае Итоши уже занял свое место в качестве первого участника; оставшиеся два места будут разыграны в жестком отборе Side-B.

Чтобы проверить стратегические способности кандидатов, Buratsuta поставил следующую задачу:

Вам дан массив из $$$n$$$ целых чисел «рекордов производительности» и $$$q$$$ запросов. Каждый запрос указывает подмассив $$$[l, r]$$$. В этом подмассиве найдите все значения рекордов, которые встречаются строго больше чем $$$\lfloor\tfrac{r - l + 1}{3}\rfloor$$$ раз.

Входные данные

Каждый тест состоит из нескольких наборов входных данных.

В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$q$$$ $$$(1 \le n, q \le 2\cdot10^5)$$$ — количество записей и количество запросов.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — записи производительности.

Каждая из следующих $$$q$$$ строк содержит два целых числа $$$l$$$ и $$$r$$$ $$$(1 \le l \le r \le n)$$$ — границы запроса.

Гарантируется, что сумма значений $$$n$$$ и сумма значений $$$q$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого запроса выведите в одной строке все значения рекордов (в отсортированном порядке), которые встречаются строго больше чем $$$\lfloor\tfrac{r - l + 1}{3}\rfloor$$$ раз на отрезке $$$[l, r]$$$. Если таких значений нет, выведите $$$-1$$$.

Пример
Входные данные
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
Выходные данные
5 
1 
1 2 
7 
7 8 
8 
4 5 
5 
4 
3 
4 
4 
4
Примечание

Во втором наборе входных данных дан массив $$$a=[1,1,2,3]$$$ и два запроса:

  • Запрос $$$(l,r)=(1,4)$$$: длина отрезка $$$len=r-l+1=4$$$, порог $$$\bigl\lfloor \frac{len}{3}\bigr\rfloor+1 = 2$$$.

    Вхождения чисел: $$$1\!\to\!2$$$, $$$2\!\to\!1$$$, $$$3\!\to\!1$$$. Только число $$$1$$$ встречается не менее $$$2$$$ раз, поэтому ответ: $$$1$$$.

  • Запрос $$$(l,r)=(2,3)$$$: длина отрезка $$$len=2$$$, порог $$$\bigl\lfloor \frac{len}{3}\bigr\rfloor+1 = 1$$$.

    Числа $$$1$$$ и $$$2$$$ встречаются по одному разу, поэтому ответ: $$$1 \; 2$$$.

В четвертом наборе входных данных дан массив $$$a=[4,4,4,5,5,5,6,6]$$$ и два запроса:

  • Запрос $$$(l,r)=(1,8)$$$: длина отрезка $$$len = 8$$$, порог $$$\bigl\lfloor \dfrac{len}{3} \bigr\rfloor + 1 = 3$$$.

    Вхождения чисел: $$$4 \!\to\! 3$$$, $$$5 \!\to\! 3$$$, $$$6 \!\to\! 2$$$. Только числа $$$4$$$ и $$$5$$$ встречаются не менее $$$3$$$ раз, поэтому ответ: $$$4 \; 5$$$.

  • Запрос $$$(l,r)=(3,6)$$$: длина отрезка $$$len = 4$$$, порог $$$\bigl\lfloor \dfrac{len}{3} \bigr\rfloor + 1 = 2$$$.

    Вхождения чисел: $$$4 \!\to\! 1$$$, $$$5 \!\to\! 3$$$. Лишь число $$$5$$$ встречается не менее $$$2$$$ раз, поэтому ответ: $$$5$$$.