B. Отрезок и разбиение
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a$$$, состоящий из $$$n$$$ целых чисел. Найдите отрезок значений $$$[x, y]$$$ ($$$x \le y$$$) и разбейте $$$a$$$ на ровно $$$k$$$ ($$$1 \le k \le n$$$) подмассивов таких, что:

  • Каждый подмассив состоит из нескольких последовательных элементов $$$a$$$, то есть он равен $$$a_l, a_{l+1}, \ldots, a_r$$$ для некоторых $$$l$$$ и $$$r$$$ ($$$1 \leq l \leq r \leq n$$$).
  • Каждый элемент $$$a$$$ принадлежит ровно одному подмассиву.
  • Для каждого подмассива количество элементов внутри отрезка $$$[x, y]$$$ (включительно) строго больше, чем количество элементов вне этого отрезка. Элемент с индексом $$$i$$$ находится внутри отрезка $$$[x, y]$$$, если и только если $$$x \le a_i \le y$$$.

Напечатайте любое решение, минимизирующее $$$y - x$$$.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка ввода содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 3 \cdot 10^4$$$) — количество наборов входных данных. Далее следует их описание.

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

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$), где $$$a_i$$$ равен $$$i$$$-му элементу массива.

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

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

Для каждого набора входных данных выведите $$$k+1$$$ строк.

В первой строке выведите $$$x$$$ и $$$y$$$ — границы найденного отрезка.

Затем выведите $$$k$$$ строк: $$$i$$$-я строка должна содержать $$$l_i$$$ и $$$r_i$$$ ($$$1\leq l_i \leq r_i \leq n$$$) — границы $$$i$$$-го подмассива.

Вы можете выводить подмассивы в любом порядке.

Пример
Входные данные
3
2 1
1 2
4 2
1 2 2 2
11 3
5 5 5 1 5 5 1 5 5 5 1
Выходные данные
1 2
1 2
2 2
1 3
4 4
5 5
1 1
2 2
3 11
Примечание

В первом наборе входных данных должен быть только один подмассив, который обязан совпадать со всем массивом. Внутри отрезка $$$[1, 2]$$$ содержится $$$2$$$ элемента, а вне его – $$$0$$$. Если выбрать отрезок $$$[1, 1]$$$, то внутри него будет содержаться $$$1$$$ элемент ($$$a_1$$$), вне его будет содержаться $$$1$$$ элемент ($$$a_2$$$), и ответ будет некорректным.

Во втором наборе можно выбрать отрезок $$$[2, 2]$$$ и разбить массив на подмассивы $$$(1, 3)$$$ и $$$(4, 4)$$$. В подмассиве $$$(1, 3)$$$ $$$2$$$ элемента содержатся внутри отрезка ($$$a_2$$$ и $$$a_3$$$) и $$$1$$$ элемент вне его ($$$a_1$$$). В подмассиве $$$(4, 4)$$$ содержится $$$1$$$ элемент ($$$a_4$$$), лежащий внутри отрезка.

В третьем наборе можно выбрать отрезок $$$[5, 5]$$$ и разбить массив на подмассивы $$$(1, 4)$$$, $$$(5, 7)$$$ и $$$(8, 11)$$$. В подмассиве $$$(1, 4)$$$ содержится $$$3$$$ элемента, лежащих внутри отрезка, и $$$1$$$ элемент, лежащий вне его. В подмассиве $$$(5, 7)$$$ содержится $$$2$$$ элемента, лежащих внутри отрезка, и $$$1$$$ элемент, лежащий вне его. В подмассиве $$$(8, 11)$$$ содержится $$$3$$$ элемента, лежащих внутри отрезка, и $$$1$$$ элемент, лежащий вне его.