Вам дано целое число m, а также список из n различных целых чисел от 0 до m - 1.
Вы хотите построить последовательность, удовлетворяющую следующим требованиям:
- Каждый элемент последовательности — целое число от 0 до m - 1, включительно.
- Все префиксные произведения (то есть, произведения положительного числа первых элементов последовательности) различны по модулю m.
- Никакое префиксное произведение по модулю m не является элементом заданного списка.
- Длина последовательности максимально возможна.
Постройте любую последовательность, удовлетворяющую описанным свойствам.
Выходные данные
В первой строке выведите число k — длину построенной последовательности.
Во второй строке выведите k целых чисел — вашу последовательность.
Примечание
В первом примере префиксные произведения построенной последовательности по модулю m равны [1, 2, 3, 4, 0].
Во втором примере префиксные произведения построенной последовательности по модулю m равны [3, 7, 4, 6, 8, 0].
Примеры
| № | Входные данные | Выходные данные |
|
1
|
0 5
|
5
1 2 4 3 0
|
|
2
|
3 10
2 9 1
|
6
3 9 2 9 8 0
|