题目描述

長さ $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$ で割ったあまりを出力してください。

$N$ 桁の $2$ 進数表現とは？非負整数 $X$ ($0\ \leq\ X\ )\ の\ N$ 桁の $2$ 進数表現とは、$0$ と $1$ のみからなり下記の条件を満たす唯一の、長さ $N$ の列 $b_{N-1}b_{N-2}\ldots\ b_0$です。

• $\sum_{i\ =\ 0}^{N-1}\ b_i\ \cdot\ 2^i\ =\ X$

输入格式

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

$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}$

题目大意

给定一个整数 $n$ 和一个长度为 $2^n-1$ 的序列 $A$（下标从 0 开始）。你需要按顺序执行 $Q$ 次操作，每次操作内容如下：

• 给定两个整数 $X,Y$，若整数 $i\in [0,2^n)$ 满足它的二进制第 $X$ 位（位数从 0 开始）为 $Y$，设 $i$ 翻转第 $X$ 位后的值为 $i'$，则让 $A_{i'}$ 的值加上 $A_i$。

所有操作执行完后，请输出整个序列 $A$。

$1\le N\le 18,\ 1\le Q\le 2\times 10^5,\ 0\le X\le N-1,\ Y\in \{0,1\}$。

2 2
0 1 2 3
1 1
0 0

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

提示

制約

• $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$
• 入力はすべて整数

Sample Explanation 1

$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)$ です。