マルチテストについての説明はこちら (サンプル問題を確認されていない方のみお読みください。)

配点：$400$ 点

問題文

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

また，任意の非負整数列 $X = (X_1, X_2, \ldots, X_{|X|})$ に対して次の操作を $0$ 回以上好きなだけ行えます：

• $1 \leq i \leq |X|$ かつ $0 \leq p$ なる $2$ 整数 $i, p$ を自由に選び，$X_i$ を $X_i \,|\, p$ で置き換える．
  • なお，$2$ 非負整数 $a, b$ に対して $a \,|\, b$ は $a, b$ の bitwise OR を表す．
• このときちょうど $p$ だけコストがかかる．

$1 \leq k \leq N$ なる整数 $k$ それぞれについて，以下の互いに独立した問題を解いてください：

• $B \coloneqq (A_1, A_2, \ldots, A_k)$．
• 数列 $B$ を回文にするために必要なコストの総和の最小値を求めよ．
  • なお，列 $X = (X_1, X_2, \ldots, X_{|X|})$ が回文であるとは，$1 \leq i \leq |X|$ なる任意の $i$ に対して $X_i = X_{|X|-i+1}$ が満たされることを指す．

制約

• $1 \leq \Phi \leq 10^4$
• $1 \leq N$
• $\sum_{\phi} \Phi_{\phi}(N) \leq 5 \times 10^5$
• $0 \leq A_i < \bold{2^{10}} \scriptsize \; (1 \leq i \leq N)$
• 入力はすべて整数

入力

各テストケースの入力は，それぞれ以下の形式で与えられる：

出力

$N$ 個の整数を空白もしくは改行区切りで出力せよ．
$i \; \scriptsize (1 \leq i \leq n)$ 番目には $k = i$ に対する問題の答えを出力せよ．

サンプル

1
5
0 1 2 3 4

0 1 2 6 6

たとえば $k = 4$ のとき， $B = (0, 1, 2, 3)$ であり $(i, p) = (1, 3), (2, 2), (3, 1)$ として順に $3$ 回の操作を行うことで $B = (3, 3, 3, 3)$ となり条件を満します．
このとき $3$ 回の操作でかかるコストの総和は $3 + 2 + 1 = 6$ で，これ未満のコストで目標は達成できないため，$6$ が答えです．

2
10
0 0 0 0 0 0 0 0 0 0
9
9 9 8 2 4 4 3 5 3

0 0 0 0 0 0 0 0 0 0
0 0 1 12 24 36 35 40 39