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

Определим перестановкой длины $$$n$$$ массив $$$p$$$ длины $$$n$$$, в котором каждое число от $$$1$$$ до $$$n$$$ встречается единожды.

Вам дана перестановка $$$p_1, p_2, \dots, p_n$$$ и число $$$k$$$. Вам необходимо отсортировать перестановку в возрастающем порядке. Для этого вы можете выполнить следующую операцию любое количество раз (возможно, ни разу):

  • выбрать два элемента перестановки $$$p_i$$$ и $$$p_j$$$ такие, что $$$|i - j| = k$$$ и поменять их местами.

К сожалению, некоторые перестановки не могут быть отсортированы для некоторых $$$k$$$. Например, невозможно отсортировать $$$[2, 4, 3, 1]$$$ для $$$k = 2$$$.

Поэтому, перед началом сортировки, вы можете выполнить не более одного предварительного обмена:

  • выбрать любую пару $$$p_i$$$ и $$$p_j$$$ и поменять их местами.

Ваша задача проверить:

  1. возможно ли отсортировать перестановку без предварительных обменов,
  2. если нет, проверить, возможно ли отсортировать перестановку с использованием ровно одного предварительного обмена.

Например, если $$$k = 2$$$ и дана перестановка $$$[2, 4, 3, 1]$$$, то вы можете выполнить предварительный обмен $$$p_1$$$ и $$$p_4$$$, что даст перестановку $$$[1, 4, 3, 2]$$$, которую уже можно отсортировать для данного $$$k$$$.

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

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

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

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

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

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

Для каждого набора входных данных выведите

  • 0, если можно отсортировать перестановку без предварительного обмена;
  • 1, если можно отсортировать перестановку с одним предварительны обменом, но нельзя без предварительных обменов;
  • -1, если нельзя отсортировать перестановку с не более чем одним предварительным обменом.
Пример
Входные данные
6
4 1
3 1 2 4
4 2
3 4 1 2
4 2
3 1 4 2
10 3
4 5 9 1 8 6 10 2 3 7
10 3
4 6 9 1 8 5 10 2 3 7
10 3
4 6 9 1 8 5 10 3 2 7
Выходные данные
0
0
1
0
1
-1
Примечание

В первом наборе предварительный обмен не нужен, так как можно обменять местами $$$(p_1, p_2)$$$ и затем $$$(p_2, p_3)$$$.

Во втором наборе предварительный обмен не нужен, так как можно обменять местами $$$(p_1, p_3)$$$ и затем $$$(p_2, p_4)$$$.

В третьем наборе необходимо применить предварительный обмен к $$$(p_2, p_3)$$$, после чего перестановка становится $$$[3, 4, 1, 2]$$$, которую уже возможно отсортировать для $$$k = 2$$$.