403388: GYM101149 C Mathematical Field of Experiments

Mathematician Michael is dreaming how he becomes a Minister of Education in Russia and tries his innovative experimental educational program in Maths in an elementary school. The main feature of this program is learning arithmetical operations in fields of integers modulo prime numbers instead of fields of real numbers. Impressed by his idea, Michael has started to write a Maths textbook for the 1st grade kids and is already preparing exercises to find a square root in modular arithmetic.

In each such exercise an integer x is given, and it's needed to find its square root modulo prime number p, which is also given. The correct answer for such task is an integer s, such that s·s and x have the same remainder after division by p. In other words, the number has to leave no remainder after division by p. It must be said that the square root s doesn't exist for some numbers x.

To speedup the process of preparing tasks in this topic, Michael decided to write a program that finds square roots modulo given prime number p for all numbers x from 0 to , or tells that the corresponding square root doesn't exist.

The first line contains a prime number p (2 ≤ p ≤ 10⁶). A prime number has exactly two different divisors.

Output p space-separated integers, the i-th of which must be equal to the square root of modulo p. All numbers must be between 0 and . If some square root doesn't exist, output  - 1 instead of it, and if there are multiple square roots for some i, output any of them.

5

0 4 -1 -1 3

7

0 1 3 -1 5 -1 -1

In the first sample: , .