F. Самый длинный страйк
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a$$$ длины $$$n$$$ и целое число $$$k$$$, вам нужно найти два любых числа $$$l$$$ и $$$r$$$ ($$$l \leq r$$$) таких, что:

  • Для каждого $$$x$$$ $$$(l \leq x \leq r)$$$, $$$x$$$ содержится в $$$a$$$ хотя бы $$$k$$$ раз (т.е. $$$k$$$ или более элементов массива равны $$$x$$$).
  • Значение $$$r-l$$$ максимально среди возможных.

Если не существует подходящих чисел, выведите -1.

Например, если $$$a=[11, 11, 12, 13, 13, 14, 14]$$$ и $$$k=2$$$, то:

  • для $$$l=12$$$, $$$r=14$$$ первое условие не выполнено, так как $$$12$$$ содержится менее $$$k=2$$$ раз.
  • для $$$l=13$$$, $$$r=14$$$ первое условие выполнено, так как $$$13$$$ содержится хотя бы $$$k=2$$$ раз в $$$a$$$ и $$$14$$$ содержится хотя бы $$$k=2$$$ раз в $$$a$$$.
  • для $$$l=11$$$, $$$r=11$$$ первое условие выполнено, так как $$$11$$$ содержится хотя бы $$$k=2$$$ раз в $$$a$$$.

Пара $$$l$$$ и $$$r$$$ для которой выполнено первое условие и $$$r-l$$$ максимально — это пара $$$l = 13$$$, $$$r = 14$$$.

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

Первая строка содержит единственное целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Затем следуют описания наборов.

Первая строка каждого набора содержит целые числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \leq k \leq n$$$) — длина массива $$$a$$$ и минимальное количество раз, которое должно встретиться каждое число в диапазоне $$$[l, r]$$$, соответственно.

Затем следует единственная строка, состоящая из $$$n$$$ целых чисел — элементов массива $$$a$$$ ($$$1 \leq a_i \leq 10^9$$$).

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

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

Для каждого набора входных данных выведите $$$2$$$ числа, $$$l$$$ и $$$r$$$ которые удовлетворяют условиям, или «-1» если таких не существует.

Если ответов может быть несколько, выведите любой.

Пример
Входные данные
4
7 2
11 11 12 13 13 14 14
5 1
6 3 5 2 1
6 4
4 3 4 3 3 4
14 2
1 1 2 2 2 3 3 3 3 4 4 4 4 4
Выходные данные
13 14
1 3
-1
1 4