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

Tokitsukaze играет в «побег из комнаты», разработанный SkywalkerT. В этой игре она должна найти скрытые подсказки в комнате, чтобы раскрыть способ побега.

Через некоторое время она поняла, что единственный способ убежать — открыть цифровой дверной замок. Она случайно зашла в тайный отсек и нашла некоторые зацепки, которые могут быть интерпретированы следующим образом:

  • Дверь можно будет открыть только после того, как будут введены $$$n$$$ возможных различных паролей.
  • Пароли должны быть целыми числами от $$$0$$$ до $$$(m - 1)$$$;
  • Пароль не может быть равен $$$x$$$ ($$$0 \leq x < m$$$), если $$$x$$$ и $$$m$$$ не являются взаимно простыми числами (т.е. $$$x$$$ и $$$m$$$ имеют некоторый общий делитель больший одного);
  • Пароль не может быть равен $$$x$$$ ($$$0 \leq x < m$$$), если существуют неотрицательные целые числа $$$e$$$ и $$$k$$$ такие, что $$$p^e = k m + x$$$, где $$$p$$$ — секретное число;
  • Любое целое число, не нарушающее описанных выше правил, может являться паролем.
  • Несколько целых чисел спрятаны в комнате, однако только одно из них может являться числом $$$p$$$.

К счастью, она узнала, что $$$n$$$ и $$$m$$$ записаны в замке. Тем не менее, Tokitsukaze расстроена тем, что она не очень хороша в математике. Теперь, когда она нашла число, которое может являться числом $$$p$$$, она хочет, чтобы Вы помогли ей найти $$$n$$$ возможных паролей или определить, что данное число не может быть числом $$$p$$$.

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

В единственной строке записаны три целых числа $$$n$$$, $$$m$$$ и $$$p$$$ ($$$1 \leq n \leq 5 \times 10^5$$$, $$$1 \leq p < m \leq 10^{18}$$$).

Гарантируется, что $$$m$$$ является простым числом, возведенным в натуральную степень.

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

Если существует строго меньше чем $$$n$$$ различных возможных паролей, выведите единственное число $$$-1$$$.

Иначе, выведите $$$n$$$ различных целых чисел от $$$0$$$ до $$$(m - 1)$$$, являющихся возможными паролями. Вы можете выводить эти числа в любом порядке. Кроме того, если существует несколько возможных решений, выведите любое.

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

В первом примере, не существует возможных паролей.

В каждом из следующих трех примеров, данное число $$$n$$$ равняется количеству возможных паролей для данных $$$m$$$ и $$$p$$$, поэтому если игнорировать порядок выведенных чисел, решение уникально, как показано выше.