AT_arc151_d [ARC151D] Binary Representations and Queries

给定一个长度为 $2^N$ 的整数序列 $A = (A_0, A_1, \ldots, A_{2^N-1})$。 同时给出 $Q$ 个查询。对于第 $i$ 个查询（$i = 1, 2, \ldots, Q$），给定两个整数 $X_i$ 和 $Y_i$，执行以下操作： > 按顺序对 $j = 0, 1, 2, \ldots, 2^N-1$ 执行以下步骤： > > 1. 首先，将 $j$ 的 $N$ 位二进制表示记为 $b_{N-1}b_{N-2}\ldots b_0$。然后，通过反转 $b_{X_i}$（$0$ 变为 $1$，$1$ 变为 $0$）得到一个新的二进制表示，并将其对应的整数记为 $j'$。 > 2. 如果 $b_{X_i} = Y_i$，则将 $A_j$ 的值加到 $A_{j'}$ 上。 请输出所有查询按给定顺序执行后，$A$ 中每个元素对 $998244353$ 取模的结果。 关于 $N$ 位二进制表示的定义：非负整数 $X$（$0 \leq X < 2^N$）的 $N$ 位二进制表示是唯一满足以下条件的长度为 $N$ 的 $0$ 和 $1$ 组成的序列 $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}$

### 约束条件 - $1 \leq N \leq 18$ - $1 \leq Q \leq 2 \times 10^5$ - $0 \leq A_i < 998244353$ - $0 \leq X_i \leq N-1$ - $Y_i \in \{0, 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_2$ 加到 $A_0$ 上，$A$ 变为 $(2,1,2,3)$。 - 当 $j=3$ 时，$b_1b_0=11$，$j'=1$。由于 $b_1=1$，将 $A_3$ 加到 $A_1$ 上，$A$ 变为 $(2,4,2,3)$。 第二个查询的操作如下： - 当 $j=0$ 时，$b_1b_0=00$，$j'=1$。由于 $b_0=0$，将 $A_0$ 加到 $A_1$ 上，$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_2$ 加到 $A_3$ 上，$A$ 变为 $(2,6,2,5)$。 - 当 $j=3$ 时，$b_1b_0=11$，$j'=2$。由于 $b_0 \neq 0$，不执行加法。 最终 $A$ 的结果为 $(2,6,2,5)$