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\) различных возможных паролей, выведите единственное число \(-1\).
Иначе, выведите \(n\) различных целых чисел от \(0\) до \((m - 1)\), являющихся возможными паролями. Вы можете выводить эти числа в любом порядке. Кроме того, если существует несколько возможных решений, выведите любое.
Примечание
В первом примере, не существует возможных паролей.
В каждом из следующих трех примеров, данное число \(n\) равняется количеству возможных паролей для данных \(m\) и \(p\), поэтому если игнорировать порядок выведенных чисел, решение уникально, как показано выше.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 2 1
|
-1
|
|
2
|
3 5 1
|
2 4 3
|
|
3
|
2 5 4
|
2 3
|
|
4
|
4 9 8
|
2 4 7 5
|