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

Тождественная перестановка длины $$$n$$$ — это массив $$$[1, 2, 3, \dots, n]$$$.

Мы применили следующие операции к тождественной перестановке длины $$$n$$$:

  • Вначале мы циклически сдвинули ее вправо на $$$k$$$ позиций, где $$$k$$$ вам неизвестно (вы знаете только то, что $$$0 \le k \le n - 1$$$). При циклическом сдвиге массива вправо на $$$k$$$ позиций необходимо взять $$$k$$$ последних элементов исходного массива (не меняя их относительный порядок) и дописать $$$n - k$$$ первых элементов исходного массива справа от них (также не меняя относительный порядок этих $$$n - k$$$ элементов). Например, если бы мы циклически сдвинули тождественную перестановку длины $$$6$$$ на $$$2$$$ позиции вправо, мы бы получили массив $$$[5, 6, 1, 2, 3, 4]$$$;
  • Далее мы выполнили следующую операцию не более $$$m$$$ раз: выбрали два элемента массива и поменяли их местами.

Вам даны $$$n$$$ и $$$m$$$, а также полученный массив. Ваша задача — найти все возможные значения $$$k$$$ в операции циклического сдвига.

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

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

Каждый набор входных данных описывается двумя строками. Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$m$$$ ($$$3 \le n \le 3 \cdot 10^5$$$; $$$0 \le m \le \frac{n}{3}$$$).

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

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

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

Для каждого набора входных данных выведите ответ следующим образом:

  • Вначале выведите одно целое число $$$r$$$ ($$$0 \le r \le n$$$) — количество возможных значений $$$k$$$ в операции циклического сдвига;
  • Далее выведите $$$r$$$ целых чисел $$$k_1, k_2, \dots, k_r$$$ ($$$0 \le k_i \le n - 1$$$) — все возможные значения $$$k$$$ в возрастающем порядке.
Пример
Входные данные
4
4 1
2 3 1 4
3 1
1 2 3
3 1
3 2 1
6 0
1 2 3 4 6 5
Выходные данные
1 3
1 0
3 0 1 2
0
Примечание

Рассмотрим примеры из условия.

  • В первом наборе входных данных единственное возможное значение для циклического сдвига это $$$3$$$. Если мы сдвинем $$$[1, 2, 3, 4]$$$ на $$$3$$$ позиции, мы получим $$$[2, 3, 4, 1]$$$. Далее мы можем поменять $$$3$$$-й и $$$4$$$-й элементы местами, чтобы получить массив $$$[2, 3, 1, 4]$$$;
  • Во втором наборе единственное возможное значение для циклического сдвига это $$$0$$$. Если мы сдвинем $$$[1, 2, 3]$$$ на $$$0$$$ позиций, мы получим $$$[1, 2, 3]$$$. Далее мы не производим операций обмена (так как нам разрешено совершить не более $$$1$$$-го обмена), таким образом, полученный массив остается равным $$$[1, 2, 3]$$$;
  • В третьем наборе все значения от $$$0$$$ до $$$2$$$ допустимы для циклического сдвига:
    • если мы сдвинем $$$[1, 2, 3]$$$ на $$$0$$$ позиций, мы получим $$$[1, 2, 3]$$$. Далее мы можем поменять $$$1$$$-й и $$$3$$$-й элементы, чтобы получить $$$[3, 2, 1]$$$;
    • если мы сдвинем $$$[1, 2, 3]$$$ на $$$1$$$ позицию, мы получим $$$[3, 1, 2]$$$. Далее мы можем поменять $$$2$$$-й и $$$3$$$-й элементы, чтобы получить $$$[3, 2, 1]$$$;
    • если мы сдвинем $$$[1, 2, 3]$$$ на $$$2$$$ позиции, мы получим $$$[2, 3, 1]$$$. Далее мы можем поменять $$$1$$$-й и $$$2$$$-й элементы, чтобы получить $$$[3, 2, 1]$$$;
  • В четвертом наборе входных данных операции обмена запрещены, однако ни один циклический сдвиг не равен массиву $$$[1, 2, 3, 4, 6, 5]$$$.