给定一个包含 $n$ 个非负整数的数组 $a_1, a_2, \dots, a_n$。对于每个 $k$ 从 $1$ 到 $n$，求出大小为 $k$ 的子序列 $(a_{i_1}, a_{i_2}, \dots, a_{i_k}; 1 \le i_1 < \dots < i_k \le n)$ 的数量，使得它们的按位与（bitwise AND）等于零（$a_{i_1} \wedge a_{i_2} \wedge \dots \wedge a_{i_k} = 0$）。由于答案可能非常大，请将它们对 $998\,244\,353$ 取模。

如果两个子序列在某个下标 $i$ 处，元素 $a_i$ 在其中一个子序列中出现而不在另一个中出现，则认为这两个子序列是不同的。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 2^{19}$)。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i < 2^{19}$)。

输出格式

输出 $n$ 个空格分隔的整数 $b_1, b_2, \dots, b_n$，其中 $b_i$ 是 $k=i$ 时的答案对 $998\,244\,353$ 取模的结果。

样例

输入 1

3
0 1 2

输出 1

1 3 1

输入 2

6
1 2 2 7 6 7

输出 2

0 3 9 10 5 1