Background

Nahida really likes permutations.

Artist pid: 72405030

Problem Description

Nahida has a permutation $c$ of $0 \sim n-1$. She wants you to construct two permutations $a, b$, also of $0 \sim n-1$, such that $\forall i \in [1,n]$, $c_i = (a_i + b_i) \bmod n$. If Nahida's requirement cannot be satisfied, output $-1$.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers, representing the permutation $c$.

Output Format

If there is no construction that meets the requirements, output one line with $-1$.

Otherwise, output two lines, each with $n$ integers. The first line is $a_i$, and the second line is $b_i$.

3
2 1 0

2 0 1
0 1 2

4
1 3 0 2

-1

Hint

Constraints

• $\text{Subtask 1(30 pts)}$: $n \le 10$.
• $\text{Subtask 2(20 pts)}$: A solution is guaranteed to exist.
• $\text{Subtask 3(50 pts)}$: No special properties.

For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 10^5$, and $c$ is a permutation.

Translated by ChatGPT 5