题目描述

小 J 用计算机生成了 $n$ 个长为 $m$ 的序列（每个序列的元素从 $0$ 到 $m - 1$ 标号），具体生成方式如下：

对于每个序列，小 J 先将所有元素置为 $0$，再指定两个生成参数 $x$ 和 $v$，对序列进行如下操作：

for (i = x; i > 0; i -= lowbit(i))
    for (j = i - lowbit(i); j < i; j++)
        A[j] += i * (i ^ v);

其中 $A$ 表示该序列，$\mathrm{lowbit}(i)$ 表示 $i$ 在二进制下最低非零位的值，如 $\mathrm{lowbit}(20) = \mathrm{lowbit}\left(\left(10100\right)_2\right) = \left(100\right)_2 = 4$。

接下来小 M 会进行 $q$ 次询问，每次询问有两个参数 $c$ 和 $d$，请你回答前 $c$ 个序列 $\mathrm{xor}$ 卷积的第 $d$ 项，即设前 $c$ 个序列为 $S_1, S_2 \dots, S_c$，求（$\oplus$ 表示二进制按位异或运算）：

$$\sum_{\substack{p_1 \oplus p_2 \oplus \dots \oplus p_c = d \\ 0 \le p_1, p_2, \dots, p_c < m}} \prod_{i=1}^{c} S_{i,p_i} $$

答案对 $998244353$ 取模。

输入格式

输入第一行包含三个整数 $n$、$m$ 和 $q$。

接下来 $n$ 行，每行包含两个整数 $x$ 和 $v$，依次表示每个序列的生成参数。

接下来 $q$ 行，每行包含两个整数 $c$ 和 $d$，依次表示每次询问的参数。

输出格式

对于每次询问，输出一行一个整数，表示所求的答案。

样例

输入：
5 4 4
1 2
2 3
4 3
4 5
2 1000000000
3 2
3 1
1 0
5 2

输出：
336
336
3
818435035

对于第一次询问，前 $3$ 个序列分别为 $[3, 0, 0, 0]$、$[2, 2, 0, 0]$ 和 $[28, 28, 28, 28]$。

当 $p = [0, 0, 2]$ 或 $p = [0, 1, 3]$ 时，符合条件，总权值为 $3 \times 2 \times 28 + 3 \times 2 \times 28 = 336$。

数据范围与提示

对于全部数据：

• $1 \le n \le 7 \times 10^5$，$1 \le m \le 10^6$，$1 \le q \le 10^5$；
• 所有序列满足 $1 \le x \le m$，$1 \le v \le 10^9$；
• 每次询问满足 $1 \le c \le n$，$0 \le d < m$。

各子任务限制如下：

子任务 1（10 分）：$n \le 5$，$m \le 5$，$q \le 5$；
子任务 2（10 分）：$n \le 100$，$m \le 100$，$q \le 100$；
子任务 3（20 分）：$n \le 2000$，$m \le 2000$；
子任务 4（30 分）：$n \le 30000$；
子任务 5（30 分）：无特殊限制