C. Возмутительный Контраст
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано целое число m, а также список из n различных целых чисел от 0 до m - 1.

Вы хотите построить последовательность, удовлетворяющую следующим требованиям:

  • Каждый элемент последовательности — целое число от 0 до m - 1, включительно.
  • Все префиксные произведения (то есть, произведения положительного числа первых элементов последовательности) различны по модулю m.
  • Никакое префиксное произведение по модулю m не является элементом заданного списка.
  • Длина последовательности максимально возможна.

Постройте любую последовательность, удовлетворяющую описанным свойствам.

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

Первая строка содержит два целых числа n и m (0 ≤ n < m ≤ 200 000) — число элементов в заданном списке и модуль, соответственно.

Если n ненулевое, то следующая строка содержит n различных целых чисел от 0 до m - 1 — запрещенные префиксные произведения. Если n равно нулю, то второй строки нет.

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

В первой строке выведите число k — длину построенной последовательности.

Во второй строке выведите k целых чисел — вашу последовательность.

Примеры
Входные данные
0 5
Выходные данные
5
1 2 4 3 0
Входные данные
3 10
2 9 1
Выходные данные
6
3 9 2 9 8 0
Примечание

В первом примере префиксные произведения построенной последовательности по модулю m равны [1, 2, 3, 4, 0].

Во втором примере префиксные произведения построенной последовательности по модулю m равны [3, 7, 4, 6, 8, 0].