Problem Statement

You are given a length-$N$ sequence of non-negative integers $A=(A_1,A_2,\ldots,A_N)$.

For $k=1,2,\ldots,N$, solve the following problem.

• Find the product, modulo $998244353$, of $A_i$ for all integers $i$ between $1$ and $k$, inclusive, such that the bitwise $\mathrm{OR}$ operation of $A_i$ and $A_k$ equals $A_k$.

What is bitwise $\mathrm{OR}$ operation? The bitwise $\mathrm{OR}$ of non-negative integers $X$ and $Y$, denoted $X\ \mathrm{OR}\ Y$, is defined as follows. When $X\ \mathrm{OR}\ Y$ is written in binary, the digit at the $2^k$ $(k \geq 0)$ place is $1$ if at least one of the digits at the $2^k$ place when $X$ and $Y$ are written in binary is $1$, and $0$ otherwise. For example, $3\ \mathrm{OR}\ 5 = 7$ (in binary: $011\ \mathrm{OR}\ 101 = 111$).

Constraints

• $1\le N\le 4\times 10^5$
• $0\le A_i < 2^{20}$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_N

Output

Output $N$ lines.

The $i$-th line $(1\le i\le N)$ should contain the answer for the case $k=i$.