AT_past202209_o.２個のボール

有两个盒子 $A$ 和 $B$，其中包含写有 $0$ 到 $2^N-1$ 之间整数的球。盒子 $A$ 中有 $A_i$ 个编号为 $i$ 的球（$0 \leq i < 2^N$），盒子 $B$ 中有 $B_i$ 个编号为 $i$ 的球（$0 \leq i < 2^N$）。所有球均可区分。

考虑从盒子 $A$ 和盒子 $B$ 各取一个球。在 $(A$ 盒中球的总数 $) \times ($ B 盒中球的总数 $)$ 种可能的取法中，令 $f(x, y)$ 表示满足下列条件的对数：

• 这里 $\mathrm{popcount}(x)$ 表示 $x$ 的二进制表达中 $1$ 的个数。
• 设 $a$、$b$ 分别为从 $A$、$B$ 中取出的球上的整数。则 $a$ 和 $b$ 的按位或为 $x$，且 $\mathrm{popcount}(a) + \mathrm{popcount}(b) = y$。

现给定长度为 $Q$ 的序列 $X$ 和 $Y$。对于每一个 $i$（$1 \leq i \leq Q$），请计算 $f(X_i, Y_i)$ 对 $998244353$ 取模的结果。

输入从标准输入给出，格式如下：

$N$ $Q$
$A_0$ $A_1$ $\dots$ $A_{2^N-1}$
$B_0$ $B_1$ $\dots$ $B_{2^N-1}$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_Q$ $Y_Q$

输出共 $Q$ 行。第 $i$ 行输出 $f(X_i, Y_i) \bmod 998244353$。

样例解释 1

• 对于 $x = 1, y = 1$，满足条件的配对 $(a,b)$ 为 $(0, 1), (1, 0)$。因此答案为 $A_0 \times B_1 + A_1 \times B_0 = 32$。
• 对于 $x = 3, y = 2$，满足条件的配对 $(a,b)$ 为 $(0,3),(1,2),(2,1),(3,0)$。因此答案为 $A_0 \times B_3 + A_1 \times B_2 + A_2 \times B_1 + A_3 \times B_0 = 61$。
• 对于 $x = 2, y = 0$，没有满足条件的配对 $(a,b)$。因此答案为 $0$。

样例解释 2

盒子中可能没有球。

数据范围

• $1 \leq N \leq 17$
• $1 \leq Q \leq 10^5$
• $0 \leq A_i < 998244353$ （$0 \leq i < 2^N$）
• $0 \leq B_i < 998244353$ （$0 \leq i < 2^N$）
• $0 \leq X_i < 2^N$ （$1 \leq i \leq Q$）
• $0 \leq Y_i \leq 2N$ （$1 \leq i \leq Q$）
• 所有输入值均为整数。

由 ChatGPT 5 翻译