問題文

長さ$N$の数列$A$が与えられます。$k = 1,2,\cdots,N$について次の問題を解いて答えを出力してください。

｜$A$の要素から添え字の異なる$k$個の要素を取り出す方法すべてについて、取り出した要素のbitwise xorを計算し、それらの和を$mod998244353$で求めてください。

制約

• $1 \leq N \leq 10^5$
• $0 \leq A_{i} \lt2^{30}$

入力

入力はすべて整数である。

N
A_1 A_2 ... A_N

出力

$k = 1,2,\cdots,N$に対する答えを$X_k$として下のように空白区切りで出力してください。

X_1 X_2 ... X_N

サンプル

3
1 2 3

6 6 0

$A$の要素から添え字の異なる$1$個の要素を取り出す方法は$\{1\}$,$\{2\}$,$\{3\}$の$3$通りで、取り出した要素のbitwise xorはそれぞれ$1,2,3$です。したがって$k = 1$に対する答えは$1 + 2 + 3 = 6$です。

$A$の要素から添え字の異なる$２$個の要素を取り出す方法は$\{1,2\}$,$\{1,3\}$,$\{2,3\}$の$3$通りで、取り出した要素のbitwise xorはそれぞれ$3,2,1$です。したがって$k = 2$に対する答えは$3 + 2 + 1 = 6$です。

$A$の要素から添え字の異なる$３$個の要素を取り出す方法は$\{1,2,3\}$の$1$通りで、取り出した要素のbitwise xorは$0$です。したがって$k = 3$に対する答えは$0$です。

5
3 1 4 1 5

14 36 40 20 2

15
216772463 773059972 511530910 457632683 1007506860 936312247 447222115 723492740 564986817 9051227 703939751 882747237 567501421 586217631 660927401

64702298 451229420 580632965 220233611 157072596 351203809 294969646 655771502 526786041 628046144 26367998 127946910 811551646 124077043 96425249