问题描述

给定一个长度为$2^N$的整数序列$A = (A_0, A_1, \ldots, A_{2^N-1})$。

另外，我们给出$Q$个查询。对于每个$i = 1, 2, \ldots, Q$，第$i$个查询由两个整数$X_i$和$Y_i$表示，并要求你执行以下操作。

按照顺序对于每个$j = 0, 1, 2, \ldots, 2^N-1$，执行以下操作：

1.首先，令$b_{N-1}b_{N-2}\ldots b_0$为$j$的二进制表示形式，其中有$N$个数字。此外，令$j'$为将第$b_{X_i}$位取反后（将$0$变为$1$，将$1$变为$0$）的二进制表示形式$b_{N-1}b_{N-2}\ldots b_0$所代表的整数。 2.然后，如果$b_{X_i} = Y_i$，将$A_j$的值加到$A_{j'}$上。

在按照给定的输入顺序处理完所有的查询后，以模$998244353$的余数形式打印$A$的每个元素。

什么是$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$。

约束条件

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

样例输入1

2 2
0 1 2 3
1 1
0 0

样例输出1

2 6 2 5

第一个查询要求你执行以下操作。

• 对于$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)$。

样例输入2

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

样例输出2

246895115 904824001 157201385 744260759 973709546 964549010 61683812 205420980