Background

You are a little frog.

You are trapped in the Seraphim Prison.

Life is a bit depressing, and the little frog fantasizes about escaping the Seraphim Prison.

Life is too oppressive, and the little frog starts to rebel against the Seraphim Prison.

The little frog is isolated and trapped again in the Seraphim Prison.

...

The cycle is not infinite. Repeating this process, one day, he will break through the dark cage of Seraphim!

Problem Description

The little frog is temporarily trapped in a loop, which can be seen as a ring with $n$ points (where $n$ is an odd number), and each point $i$ has a point weight $a_i$.

For all $1 \leq i < n$, there is an edge between point $i$ and point $i+1$ with an edge weight $w_i$; there is also an edge between point $1$ and point $n$ with an edge weight $w_n$.

The edge weights and point weights of this ring have a peculiar relationship: for any edge $i$, its edge weight $w_i$ must satisfy the relationship $w_i = \frac{1}{2}(a_i + a_{i+1})$, where $w_n = \frac{1}{2}(a_1 + a_n)$. When the edge weight of any edge in the ring changes, the weights of all points will change accordingly until all point weights can satisfy the above relationship with the edge weights.

Now the frog has the values of $w_1$ to $w_n$, and he can swap the weights of any two edges any number of times (i.e., arbitrarily shuffle the edge weights). Now the frog needs to provide two arrangements of $w_1$ to $w_n$, each to make the point weight of point $1$ the largest / the smallest among all possible permutations.

However, due to the infinite loop, the frog's mind is very confused, so he seeks your help. You need to help him construct these two arrangements.

The problem guarantees that $\boldsymbol{n}$ is an odd number.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers, where the $i$-th number $w_i$ represents the weight of the $i$-th edge.

Output Format

Two lines, each containing $n$ integers, represent the answer.

The first line contains $n$ integers from $w_1'$ to $w_n'$ representing a scheme that makes the point weight of point $1$ the largest.

The second line contains $n$ integers from $w_1''$ to $w_n''$ representing a scheme that makes the point weight of point $1$ the smallest.

This problem uses a special judge, which means that if there are multiple possible answers, you can output any one of them.

Sample Input and Output

Sample Input #1

3
0 0 0

Sample Output #1

0 0 0
0 0 0

Sample Input #2

5
1 1 1 1 -1

Sample Output #2

1 1 1 -1 1
1 1 -1 1 1

Sample Input #3

3
1 2 3

Sample Output #3

3 1 2
2 3 1

Notes

[Explanation of Sample #1]

The red numbers represent point weights, the black numbers represent edge weights, and the blue numbers represent point numbers.

It can be proven that under this scheme, the point weight of point $1$ is both the smallest and the largest.

[Explanation of Sample #2]

The red numbers represent point weights, the black numbers represent edge weights, and the blue numbers represent point numbers.

It can be proven that under these two schemes, the point weight of point $1$ is the largest and the smallest, respectively. Note that this is not necessarily the only solution.

[Data Range and Constraints]

This problem is bundled with tests.

• Special Property $\rm A$: The sequence $\{w\}$ is obtained by arbitrarily shuffling the set $\{-1, 0, 1\}$.
• Special Property $\rm B$: It is guaranteed that $n \ge 3$ and for all $i \in [2, n]$, $w_i$ is the same.
• Special Property $\rm C$: It is guaranteed that $n \ge 3$ and for all $i \in [3, n]$, $w_i$ is the same.
• For $100\%$ of the data, $1 \leq n \leq 10^6$ and $n$ is an odd number, $|w_i| \leq 10^9$.

见题面 Input 部分

见题面 Output 部分