反向传播

一共有 $2^m-1$ 个函数 $f_i(x_1...x_{2^{m-1}})~~~~~(1\leq i\leq 2^m-1)$，其中对于 $2^{m-1}\leq i\leq 2^m-1$，有$f_i(x)=x_{i-2^{m-1}+1}$

对于 $1\leq i\leq 2^{m-1}-1$，有 $f_i(x)=f_{2i}(x)~op_i~f_{2i+1}(x)$，其中 $op_i\in \{+,\times\}$

一开始有 $x_i=i$，接下来一共有 $Q$ 次操作，每次操作是其中以下两个中的一种：

- $1~i~y$：表示令 $x_i=y$
- $2~i$： 表示你需要求出：$\lim_{d\rightarrow 0}\frac{f_1(add(x,i,d))-f_1(x)}{d}$，其中 $add(x,i,d)$ 表示：将 $x_1...x_{2^{m-1}}$ 中的 $x_i$ 变成 $x_i+d$，其他的保持不变，可以发现该操作其实就是需要你求出 $\frac{\partial f_1(x)}{\partial x_i}$

由于答案可能很大，你只需要输出答案对 $998244353$ 取模后的值

第一行两个正整数 $m(2\leq m\leq 20)$，$Q(1\leq Q\leq 10^5)$

第二行一个长度为 $2^{m-1}-1$ 的 01 字符串 ，第 $i$ 个字符为 $0$ 表示 $op_i=+$，否则 $op_i=\times$

接下来 $Q$ 行，每行两个数或者三个数表示一次操作，保证 $0\leq y< 998244353$

对于每次操作 2，输出答案

2 6
1
2 1
2 2
1 1 6
1 2 7
2 1
2 2

2
1
7
6

2019 年百度之星·程序设计大赛 - 初赛三