Математик Миша мечтает о том, как он станет министром образования России и опробует свою оригинальную экспериментальную образовательную программу по математике в начальных классах школы. Суть этой программы состоит в том, что вместо изучения арифметических операций в поле вещественных чисел, первоклассники будут изучать эти операции в конечных полях по модулю простых целых чисел. Под впечатлением от своей идеи Миша решил написать новейший учебник арифметики для первых классов и уже составляет задачи и упражнения на тему дискретного извлечения квадратного корня по модулю.
Входными данными в каждой такой задаче является целое число x, из которого требуется извлечь квадратный корень, и простое число p, по модулю которого это требуется сделать. Правильным ответом на такую задачу является квадратный корень из x по модулю p, то есть такое целое число s, что s·s и x дают один и тот же остаток от деления на p. Иными словами, число 
должно нацело делиться на p. Нужно заметить, что иногда для заданного x подходящего квадратного корня s не существует.
Чтобы автоматизировать процесс составления задач на эту тему, Миша решил написать программу, которая для заданного простого числа p находит квадратные корни по модулю p из всех целых чисел x от 0 до 
включительно, либо сообщает, что соответствующего квадратного корня не существует.
Первая строка содержит единственное простое целое число p (2 ≤ p ≤ 106). Простое число имеет ровно два различных делителя.
Выведите p неотрицательных целых чисел через пробел, i-ое из которых должно быть равно квадратному корню из 
по модулю p. Ни одно из чисел не должно превышать . Если некоторого квадратного корня не существует, выведите - 1 вместо него, а если существует несколько подходящих целых чисел от 0 до включительно, каждое из которых является квадратным корнем из соответствующего числа, то выведите любое из них.
5
0 4 -1 -1 3
7
0 1 3 -1 5 -1 -1
В первом примере: 
, 
.
