Statement is not available in English language
D. Перетировка сорстановки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана перестановка $$$p$$$ всех чисел от $$$1$$$ до $$$n$$$, а также целое число $$$k$$$. С перестановкой разрешается выполнять следующую операцию неограниченное число раз:

  1. Выбрать любой подотрезок длины $$$k$$$.
  2. Найти на этом подотрезке минимальный и максимальный элементы.
  3. Поменять их местами.
Ваша задача с помощью этих операций отсортировать перестановку или же сообщить, что это невозможно.
Входные данные

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

Первая строка каждого набора входных данных содержит два целых числа $$$n, k$$$ ($$$5 \le n \le 100, 2 \le k \le 4$$$) — длина перестановки, а также размер отрезка, над которым проводим операцию.

Вторая строка каждого набора входных данных содержит числа $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — изначальная перестановка.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$100$$$, а также, что $$$p$$$ является корректной перестановкой.

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

Для каждого набора входных данных выведите «YES», если возможно отсортировать перестановку с помощью таких операций, в ином случае «NO».

Если можно отсортировать, то затем нужно вывести сами операции.

В первой строке выведите число $$$m$$$ — количество действий для сортировки. В следующих $$$m$$$ ($$$1 \le m \le 10^5$$$) строках сами операции в порядке выполнения.

Для каждой операции выведите два числа $$$l, r$$$ ($$$1 \le l \le r \le n, r - l + 1 = k$$$) — означающие отрезки, над которыми проводятся операции.

Гарантируется, что для всех входных данных, где ответ существует, существует набор операций, состоящий не более чем из $$$10^5$$$ операций, который позволяет отсортировать массив.

Пример
Входные данные
4
8 2
1 4 8 3 2 5 7 6
5 3
1 3 5 2 4
5 4
1 3 2 5 4
6 3
4 3 5 1 6 2
Выходные данные
YES
9
3 4
2 3
4 5
3 4
2 3
5 6
6 7
7 8
6 7
YES
7
1 3
3 5
1 3
2 4
3 5
2 4
1 3
NO
YES
6
1 3
2 4
1 3
4 6
3 5
2 4