Тождественная перестановка длины \(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\) в возрастающем порядке.
Примечание
Рассмотрим примеры из условия.
- В первом наборе входных данных единственное возможное значение для циклического сдвига это \(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]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|