408228: GYM103059 I Prefix Prizes

I. Prefix Prizestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Mateo, the owner of Austin's most popular video game store, was in a generous mood one day. He decides to give a gift to each of the $$$n$$$ people currently in his store and he has $$$n$$$ distinct prizes labeled $$$0, 1, \dots, n - 1$$$ to give out. Since Mateo never does anything the simple way, he comes up with the following scheme to give the prizes out.

He gives each of the $$$n$$$ people in the store unique numbers from $$$1$$$ to $$$n$$$ (inclusive). He then asks everyone to form a line and so the resulting ordering of the people can be written as the sequence $$$[x_1, x_2, \dots, x_n]$$$ (where each $$$x_i$$$ is unique and $$$1 \leq x_i \leq n$$$). The prize which Mateo gives person $$$x_j$$$ is equal to $$$x_1 \cdot x_2 \cdot \ldots \cdot x_{j-1} \cdot x_{j} \pmod{n}$$$. Unfortunately, Mateo only has one of each prize so he asks you to come up with an ordering of the $$$n$$$ people so that each person will get a unique prize number.

Input

The first and only line of input will contain a single integer $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$), representing the number of people in the store.

Output

A space-separated permutation of the numbers from $$$1$$$ to $$$n$$$ (inclusive), representing the ordering of people such that each person can get a distinct prize. Output -1 if there is no such permutation.

ExamplesInput

7

Output

1 4 3 6 5 2 7

Input

8

Output

-1

Note

In the first example:

• The product after the first person is $$$1$$$ so the first person gets prize $$$1$$$.
• The product after the second person is $$$1 \cdot 4 = 4 \equiv 4 \pmod{7}$$$ so the second person gets prize $$$4$$$
• The product after the third person is $$$4 \cdot 3 = 12 \equiv 5 \pmod{7}$$$ so the third person gets prize $$$5$$$.
• The product after the fourth person is $$$5 \cdot 6 = 30 \equiv 2 \pmod{7}$$$ so the fourth person gets prize $$$2$$$.
• The product after the fifth person is $$$5 \cdot 2 = 10 \equiv 3 \pmod{7}$$$ so the fifth person gets prize $$$3$$$.
• The product after the sixth person is $$$3 \cdot 2 = 6 \equiv 6 \pmod{7}$$$ so the sixth person gets prize $$$6$$$.
• The product after the seventh person is $$$6 \cdot 7 = 42 \equiv 0 \pmod{7}$$$ so the seventh person gets prize $$$0$$$.

Thus, with this ordering of people, each person will get a unique one of the $$$7$$$ prizes.