二进制表示与查询

时间限制：2s
空间限制：512MB

题目描述

给定长度为 $2^N$ 的整数序列 $A=(A_0,A_1,\ldots,A_{2^N-1})$，以及 $Q$ 次查询。第 $i$ 次查询给出 $X_i,Y_i$，并按照 $j=0,1,\ldots,2^N-1$ 的顺序执行下列操作：把 $j$ 写成 $N$ 位二进制数 $b_{N-1}b_{N-2}\ldots b_0$，令 $j'$ 为翻转其中第 $X_i$ 位后表示的整数；如果 $b_{X_i}=Y_i$，就把当前的 $A_j$ 加到 $A_{j'}$ 中。

所有查询依次完成后，输出序列中每个元素对 $998244353$ 取模的结果。这里二进制位从最低位开始编号为 $0$。

输入格式

第一行两个整数 $N,Q$。第二行给出 $2^N$ 个整数 $A_0,A_1,\ldots,A_{2^N-1}$。接下来 $Q$ 行，每行两个整数 $X_i,Y_i$。

输出格式

输出一行 $2^N$ 个整数，依次表示所有查询结束后的 $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

样例输入 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

数据范围

• $1\le N\le 18$，$1\le Q\le 2\times 10^5$；
• $0\le A_i<998244353$；
• $0\le X_i<N$，$Y_i\in\{0,1\}$；
• 输入均为整数。