Background

You are a little frog.

You are locked into the “Saila Feiwuzhi Prison”.

Life feels a bit depressing, so the little frog imagines that he has walked out of the Saila Feiwuzhi Prison.

Life becomes too depressing, so the little frog starts to resist the Saila Feiwuzhi Prison.

The little frog is helpless and isolated, and gets locked into the Saila Feiwuzhi Prison again.

...

The loop is not infinite. Repeating like this, one day he will break through the dark cage called Saila Feiwuzhi!

Problem Description

The little frog is temporarily trapped in a loop. This loop can be seen as a cycle with $n$ vertices ($n$ is odd). Each vertex $i$ has a vertex weight $a_i$.

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

The edge weights and vertex weights have a special relationship: for any edge $i$, its edge weight $w_i$ must satisfy $w_i=\dfrac12(a_i+a_{i+1})$, where $w_n=\dfrac12(a_1+a_{n})$. When the edge weight of any edge in the cycle changes, all vertex weights will change accordingly, until all vertex weights and edge weights satisfy the relationship above.

Now the frog knows the values of $w_1 \sim w_n$, and he can swap the weights of any two edges any number of times (i.e., he may permute the edge weights arbitrarily). The frog now needs to give two arrangements of $w_1 \sim w_n$, such that the weight of vertex $1$ is maximized among all permutations / minimized among all permutations, respectively.

However, because the frog is stuck in an infinite loop, his mind is very confused. So he asks you for help: you need to construct these two arrangements.

It is guaranteed that $\boldsymbol n$ is odd.

Input Format

The first line contains an integer $n$.

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

Output Format

Output two lines. Each line contains $n$ integers representing an answer.

The first line contains $n$ integers $w_1' \sim w_n'$, representing an arrangement that makes the weight of vertex $1$ as large as possible.

The second line contains $n$ integers $w_1'' \sim w_n''$, representing an arrangement that makes the weight of vertex $1$ as small as possible.

This problem uses special judge. That is, if there are multiple valid answers, you may output any one of them.

3
0 0 0

0 0 0 
0 0 0

5
1 1 1 1 -1

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

3
1 2 3

3 1 2
2 3 1

Hint

[Sample #1 Explanation]

Here, red numbers are vertex weights, black numbers are edge weights, and blue numbers are vertex indices.

It can be proved that in this arrangement, the weight of vertex $1$ is both the minimum and the maximum.

[Sample #2 Explanation]

Here, red indicates vertex weights, black indicates edge weights, and blue indicates vertex indices.

It can be proved that in these two arrangements, the weight of vertex $1$ reaches the maximum and the minimum respectively. Note that this is not necessarily the unique solution.

[Constraints and Notes]

This problem uses bundled testdata.

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

Translated by ChatGPT 5