配点 : $700$ 点

問題文

長さ $2^N$ の整数列 $A = (A_0, A_1, \ldots, A_{2^N-1})$ が与えられます。

また、$Q$ 個のクエリが与えられます。 $i = 1, 2, \ldots, Q$ について、$i$ 番目のクエリでは $2$ つの整数 $X_i, Y_i$ が与えられ、下記の操作を行います。

$j = 0, 1, 2, \ldots, 2^N-1$ の順に下記の手順を行う。

1. まず、$j$ の $N$ 桁の $2$ 進数表現を $b_{N-1}b_{N-2}\ldots b_0$ とおく。また、$b_{N-1}b_{N-2}\ldots b_0$ から $b_{X_i}$ を反転（ $0$ ならば $1$ に、$1$ ならば $0$ に変更）させて得られる $2$ 進数表現によって表される整数を $j'$ とおく。
2. そして、$b_{X_i} = Y_i$ ならば、$A_{j'}$ に $A_j$ の値を加算する。

すべてのクエリを入力で与えられる順番に実行した後の $A$ の各要素を $998244353$ で割ったあまりを出力してください。

制約

• $1 \leq N \leq 18$
• $1 \leq Q \leq 2 \times 10^5$
• $0 \leq A_i \lt 998244353$
• $0 \leq X_i \leq N-1$
• $Y_i \in \lbrace 0, 1\rbrace$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$N$ $Q$

$A_0$ $A_1$ $\ldots$ $A_{2^N-1}$

$X_1$ $Y_1$

$X_2$ $Y_2$

$\vdots$

$X_Q$ $Y_Q$

出力

$i = 0, 1, \ldots, 2^N-1$ について、すべてのクエリを実行した後の $A_i$ を $998244353$ で割ったあまり $A'_i$ を、下記の形式にしたがって空白区切りで出力せよ。

$A'_0$ $A'_1$ $\ldots$ $A'_{2^N-1}$

2 2
0 1 2 3
1 1
0 0

2 6 2 5

$1$ 番目のクエリに対する操作は次の通りです。

• $j = 0$ のとき、$b_1b_0 = 00, j' = 2$ です。$b_1 \neq 1$ であるので、加算の手順は行いません。
• $j = 1$ のとき、$b_1b_0 = 01, j' = 3$ です。$b_1 \neq 1$ であるので、加算の手順は行いません。
• $j = 2$ のとき、$b_1b_0 = 10, j' = 0$ です。$b_1 = 1$ であるので、$A_0$ に $A_2$ の値を加算します。その結果、$A = (2, 1, 2, 3)$ となります。
• $j = 3$ のとき、$b_1b_0 = 11, j' = 1$ です。$b_1 = 1$ であるので、$A_1$ に $A_3$ の値を加算します。その結果、$A = (2, 4, 2, 3)$ となります。

$2$ 番目のクエリに対する操作は次の通りです。

• $j = 0$ のとき、$b_1b_0 = 00, j' = 1$ です。$b_0 = 0$ であるので、$A_1$ に $A_0$ の値を加算します。その結果、$A = (2, 6, 2, 3)$ となります。
• $j = 1$ のとき、$b_1b_0 = 01, j' = 0$ です。$b_0 \neq 0$ であるので、加算の手順は行いません。
• $j = 2$ のとき、$b_1b_0 = 10, j' = 3$ です。$b_0 = 0$ であるので、$A_3$ に $A_2$ の値を加算します。その結果、$A = (2, 6, 2, 5)$ となります。
• $j = 3$ のとき、$b_1b_0 = 11, j' = 2$ です。$b_0 \neq 0$ であるので、加算の手順は行いません。

以上より、すべてのクエリを実行した後の $A$ は $(2, 6, 2, 5)$ です。

3 10
606248357 338306877 919152167 981537317 808873985 845549408 680941783 921035119
1 1
0 0
0 0
0 0
0 1
0 1
0 1
2 0
2 0
2 0

246895115 904824001 157201385 744260759 973709546 964549010 61683812 205420980