题目描述

给定一个长度为 $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

输入

2 2
0 1 2 3
1 1
0 0

输出

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

输出

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