#3073. 「2019 集训队互测 Day 2」序列

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: cz_xuyixuan

题目描述

小 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_{{\array{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 分):无特殊限制。