AT_arc205_e [ARC205E] Subset Product Problem

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 $ ).

The input is given from Standard Input in the following format: > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

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

### Sample Explanation 1 - When $ k=1 $ : For $ i=1 $ , the bitwise $ \mathrm{OR} $ operation of $ A_i $ and $ A_k $ is $ 1 $ . Therefore, the answer for the case $ k=1 $ is $ A_1=1 $ . - When $ k=2 $ : For $ i=1,2 $ , the bitwise $ \mathrm{OR} $ operation of $ A_i $ and $ A_k $ is $ 3,2 $ , respectively. Therefore, the answer for the case $ k=2 $ is $ A_2=2 $ . - When $ k=3 $ : For $ i=1,2,3 $ , the bitwise $ \mathrm{OR} $ operation of $ A_i $ and $ A_k $ is all $ 3 $ . Therefore, the answer for the case $ k=3 $ is $ A_1\times A_2\times A_3=6 $ . - When $ k=4 $ : For $ i=1,2,3,4 $ , the bitwise $ \mathrm{OR} $ operation of $ A_i $ and $ A_k $ is $ 5,7,7,5 $ , respectively. Therefore, the answer for the case $ k=4 $ is $ A_1\times A_4=5 $ . ### Constraints - $ 1\le N\le 4\times 10^5 $ - $ 0\le A_i < 2^{20} $ - All input values are integers.