問題文

$N$ 個の整数 $A_1, A_2, \dots, A_N$ があります。

$N$ 個の互いに独立した問題 $1\text{-gathering}, 2\text{-gathering}, \dots, N\text{-gathering}$ を解いてください：

$k\text{-gathering}$

長さ $k$ の整数列 $B = (B_1, B_2, \dots, B_k)$ があり、はじめ $B = (A_1, A_2, \dots, A_k)$ が満たされています。

次の操作を $0$ 回以上何度でも行えます：

• $1 \leq i, j \leq k$ なる $2$ 整数 $i, j$ を自由に選び、$\large B_i$ を $\large 2B_j - B_i$ の値で置き換える。

操作を適切に行って得られる $V_k \coloneqq \displaystyle \max B - \min B$ の最小値 $V'_k$ を求めてください。
なお、これは必ず存在します。

入力

入力は、以下の形式で標準入力より与えられる：

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

出力

各 $V'_1, V'_2, \dots, V'_N$ の値を、以下の形式で標準出力へ出力せよ：

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

制約

• $1 \leq N \leq 3 \times 10^5$
• $\left| A_i \right| < 2^{60} \scriptsize \; (1 \leq i \leq N)$
• 入力はすべて整数

サンプル

4
2 6 5 -4

0
4
1
1