Echoing Permutation#13045
Sign in

Echoing Permutation

3 seconds
512 megabytes
Very hard

You are given an integer and an array of length .

Let

m=n+1.

Find a permutation of the integers from to such that for every (1 \le i \le n),

p_1 \cdot p_2 \cdot \ldots \cdot p_i \equiv b_i \pmod{m}.

If no such permutation exists, print -1.

Input

The first line contains one integer (1 \le n \le 2 \cdot 10^5).

The second line contains integers b_1,b_2,\ldots,b_n (0 \le b_i \le n).

Output

If a valid permutation exists, print integers p_1,p_2,\ldots,p_n.

Otherwise, print -1.

If there are several valid permutations, print any of them.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

In the first example, no valid permutation exists.

In the second example, the permutation

p=[1,2,3]

is valid, since its prefix products modulo are

1,\ 2,\ 2.

Scoring

  1. Subtask ( points): n \le 8.

  2. Subtask ( points): n \le 100.

  3. Subtask ( points): n+1 is prime.

  4. Subtask ( points): n \le 5000.

  5. Subtask ( points): b_i>0 for every .

  6. Subtask ( points): No additional constraints.