Тождественная перестановка длины $$$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$$$ в операции циклического сдвига.
Выходные данные
Для каждого набора входных данных выведите ответ следующим образом:
- Вначале выведите одно целое число $$$r$$$ ($$$0 \le r \le n$$$) — количество возможных значений $$$k$$$ в операции циклического сдвига;
- Далее выведите $$$r$$$ целых чисел $$$k_1, k_2, \dots, k_r$$$ ($$$0 \le k_i \le n - 1$$$) — все возможные значения $$$k$$$ в возрастающем порядке.
Пример
Выходные данные
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]$$$.