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

Антону стало скучно в походе, и он захотел что-нибудь порешать. Он спросил у Кирилла, нет ли у него какой-то новой задачи, и у Кирилла она естественно нашлась.

Дана перестановка $$$p$$$ размера $$$n$$$, а также число $$$x$$$, которое необходимо найти. Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

Вы решили, что вы крутой программист, поэтому будете использовать для поиска продвинутый алгоритм — бинарный поиск. Однако, вы забыли, что для бинарного поиска массив должен быть отсортирован.

Вы не отчаялись и решили все равно применить этот алгоритм, а чтобы получить правильный ответ, вы перед запуском алгоритма можете не более $$$2$$$ раз выполнить следующую операцию: выбрать индексы $$$i$$$, $$$j$$$ ($$$1\le i, j \le n$$$) и поменять местами элементы на позициях $$$i$$$ и $$$j$$$.

После этого выполняется бинарный поиск. В начале алгоритма объявляются две переменные $$$l = 1$$$ и $$$r = n + 1$$$. Далее выполняется цикл:

  1. Если $$$r - l = 1$$$, закончить цикл
  2. $$$m = \lfloor \frac{r + l}{2} \rfloor$$$
  3. Если $$$p_m \le x$$$, присвоить $$$l = m$$$, иначе $$$r = m$$$.

Цель — до алгоритма переставить числа в перестановке так, чтобы после выполнения алгоритма $$$p_l$$$ было равно $$$x$$$. Можно показать, что $$$2$$$ операции всегда достаточно.

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

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

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

Во второй строке через пробел вводится перестановка $$$p$$$ ($$$1 \le p_i \le n$$$).

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

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

Для каждого набора входных данных выведите в первой строке целое число $$$k$$$ ($$$0 \le k \le 2$$$) — количество совершенных вами операций. В следующих $$$k$$$ строках через пробел выведите по $$$2$$$ целых числа $$$i$$$, $$$j$$$ ($$$1 \le i, j \le n$$$) означающих, что вы меняете местами элементы на позициях $$$i$$$ и $$$j$$$.

Обратите внимание, что вам не нужно минимизировать количество операций.

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