P11897 「LAOI-9」多维空间中的游戏

小 $\mathbf A$ 和小 $\mathbf B$ 正在玩一个有趣的游戏。 游戏将在一个 $\underbrace{2\times2\times2\times\cdots\times2}_{k 个 2}$ 的 $k$ 维空间中进行。最小的节点的坐标为 $(\underbrace{0,0,0,\cdots,0}_{k个0})$，最大的节点的坐标为 $(\underbrace{1,1,1,\cdots,1}_{k个1})$。 下面是 $k=3$ 时的情况：  小 $\mathbf A$ 和小 $\mathbf B$ 各执一枚 $k$ 维空间中的点。 小 $\mathbf A$ 和小 $\mathbf B$ 轮流操作，小 $\mathbf A$ 先手。 定义一个维度为可操作的，当且仅当两个点中存在至少一个点在这个维度上的坐标不为 $0$。然后，操作方可以将两个点的某个可操作的维度的坐标置为 $0$。 如图，这是一个合法的操作：  这也是一个合法的操作：  但是这不是一个合法的操作，因为两个点在这个维度上的坐标均为 $0$：  无法操作者输。 相信大家一定发现了，我们可以将任意一个坐标编码为一个二进制数。例如对于坐标 $(0,1,1,1,0,0,1,0)$，可以编码为 $\tt 01110010$，对应十进制数 $114$。 小 $\mathbf A$ 和 $\mathbf B$ 将进行 $q$ 轮游戏。两人绝顶聪明，都想要自己赢。每一轮双方点的位置将会随机生成，进一步地，生成到编码为 $x$ 的坐标的概率为 $p_x$。 由于小 $\mathbf A$ 先手，所以每轮她们将会划定一个可落子区域 $[l,r]$，其他区域则为不可落子区域。如果小 $\mathbf A$ **初始**的点坐标编码后的值在区间 $[l,r]$ 外，则将会判为小 $\mathbf B$ 胜。（此规则对小 $\mathbf B$ 不生效，也就是即使小 $\mathbf B$ 初始的点坐标编码后的值在区间 $[l,r]$ 外，也不会直接判为小 $\mathbf A$ 胜） 现在对于第 $i$ 轮，可落子区域为 $[l_i,r_i]$，小 $\mathbf B$ 会有 $a_i$ 个询问，每个询问为当她的点被随机到编号为 $x$ 的坐标，且小 $\mathbf A$ 的点按照 $p$ 的概率随机生成时，她的胜率为多少。答案对 $998244353$ 取模。

第一行一个正整数 $c$ 表示子任务编号，特殊地，样例的编号为 $0$。 接下来一行一个正整数 $t$ 表示数据读入输出方法。当 $t=1$ 时，你需要在下一行接着读入一个整数 $seed$ 表示随机种子。 接下来一行一个正整数 $k$ 表示维度数。 接下来一行 $2^k$ 个非负整数 $p_0,p_1,\cdots,p_{2^{k}-1}$ 表示生成到编码为 $x$ 的坐标的概率为 $p_x$。 接下来一行一个正整数 $q$ 表示游戏轮数。 接下来 $q$ 组询问，对于第 $i$ 组询问（下标从 $1$ 开始）： 每组询问第一行三个整数，表示 $a_i,l_i,r_i$。 当 $t=0$ 时，接下来一行 $a_i$ 个整数 $x_{i,1},x_{i,2},\cdots,x_{i,a_i}$，表示每次小 $\mathbf B$ 的询问。 当 $t=1$ 时，接下来小 $\mathbf B$ 的第 $j$ 个询问（下标从 $1$ 开始）$x_{i,j}$ 为 $seed\times i\times j\times 50007\bmod (2^k)$。 对于 C++ 选手，我们下发了一份数据读入模板 `down.cpp`，您只需要完善其中的代码部分即可。

当 $t=0$ 时，对于第 $i$ 组询问输出一行 $a_i$ 个整数，表示这组询问所有答案模 $998244353$ 后的值。 当 $t=1$ 时，对于每组询问输出一行一个整数，表示这组询问所有答案模 $998244353$ 后的异或和。

### 样例 1 解释 对于第一组询问，当小 $\mathbf A$ 的点在编号为 $1$ 的坐标时，由于超出了可落子区域，小 $\mathbf B$ 胜；当小 $\mathbf A$ 的点在编号为 $2$ 的坐标时，小 $\mathbf A$ 胜；当小 $\mathbf A$ 的点在编号为 $3$ 的坐标时，小 $\mathbf B$ 胜。 故在模意义下，小 $\mathbf B$ 的胜率：$1+2=3$。 ### 样例 2 解释 解码后，$x_{1,1}=1,x_{1,2}=2$，答案分别为 $18,18$，异或和为 $0$。 **本题目采用捆绑测试**。 | 子任务编号 | $k\le$ | $q\le$ | $a_i\le$ | 时间限制 | 特殊性质 | 分值 | | :--------: | :----: | :----: | :------: | :------: | :------: | :--: | | $0$ | $5$ | $30$ | $30$ | 1 秒 | 样例 | $0$ | | $1$ | $1$ | $30$ | $30$ | 1 秒 | | $5$ | | $2$ | $2$ | $30$ | $30$ | 1 秒 | | $5$ | | $3$ | $10$ | $300$ | $100$ | 1 秒 | | $20$ | | $4$ | $15$ | $100$ | $2^{15}$ | 1 秒 | $t=1$ | $20$ | | $5$ | $16$ | $1000$ | $100$ | 1 秒 | | $10$ | | $6$ | $16$ | $2000$ | $3000$ | 1 秒 | $t=1$ | $10$ | | $7$ | $16$ | $3000$ | $2^{15}$ | 2 秒 | $t=1$ | $30$ | 对于 $100\%$ 数据，满足 $1\le k\le 16,1\le q\le 3000,0\le p_i