I. Prefix Prizes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard 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.

Examples
Input
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.