Problem Statement

There are $N$ integers $A_1, A_2, \dots, A_N$.

Solve the following $N$ mutually independent problems $1\text{-gathering}, 2\text{-gathering}, \dots, N\text{-gathering}$:

$k\text{-gathering}$

There is an integer sequence $B = (B_1, B_2, \dots, B_k)$ of length $k$, and initially $B = (A_1, A_2, \dots, A_k)$ holds.

You may perform the following operation any number of times, possibly $0$ or more:

• Freely choose $2$ integers $i, j$ such that $1 \leq i, j \leq k$, and replace $\large B_i$ with the value of $\large 2B_j - B_i$.

Find the minimum value $V'_k$ of $V_k \coloneqq \displaystyle \max B - \min B$ that can be obtained by performing the operations appropriately.
Note that this value always exists.

Input

The input is given from standard input in the following format:

$N$
$A_1 \enspace A_2 \enspace \dots \enspace A_N$

Output

Output the values of $V'_1, V'_2, \dots, V'_N$ to standard output in the following format:

$V'_1$
$V'_2$
$\vdots$
$V'_N$

Constraints

• $1 \leq N \leq 3 \times 10^5$
• $\left| A_i \right| < 2^{60} \scriptsize \; (1 \leq i \leq N)$
• All input values are integers

Sample

4
2 6 5 -4

0
4
1
1