题目描述

给定长度为 $n$ 的数列 $a$，如果 $a_i \& a_j\neq 0$（按位与），则在 $i,j$ 之间存在一条长度为 $a_i+a_j$ 的边，求 $1$ 至所有点的最短路。

输入格式

第一行一个正整数 $n$。

接下来一行 $n$ 个整数 $a_1\sim a_n$。

输出格式

输出一行 $n$ 个整数，第 $i$ 个为 $1$ 到 $i$ 的最短路长度。不能到达输出 -1。

样例输入

5
1 5 6 7 8

样例输出

0 6 17 8 -1

数据范围

对于 $20\%$ 的数据， $n\leq 10$。

对于 $40\%$ 的数据， $n\leq 10^3$。

对于另外 $20\%$ 的数据， 所有的 $a_i$ 均可表示为 $2^x+2^y$ 的形式。

对于 $100\%$ 的数据， $1\leq n\leq 10^5,0\leq a_i\leq 2^{31}-1$。