题目描述
小 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 表示该序列,lowbit(i) 表示 i 在二进制下最低非零位的值,如 lowbit(20)=lowbit((10100)2)=(100)2=4。
接下来小 M 会进行 q 次询问,每次询问有两个参数 c 和 d,请你回答前 c 个序列 xor 卷积的第 d 项,即设前 c 个序列为 S1,S2…,Sc,求(⊕ 表示二进制按位异或运算):
\arrayp1⊕p2⊕⋯⊕pc=d0≤p1,p2,…,pc<m∑i=1∏cSi,pi
答案对 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×2×28+3×2×28=336。
数据范围与提示
对于全部数据:
- 1≤n≤7×105,1≤m≤106,1≤q≤105;
- 所有序列满足 1≤x≤m,1≤v≤109;
- 每次询问满足 1≤c≤n,0≤d<m。
各子任务限制如下:
- 子任务 1(10 分):n≤5,m≤5,q≤5;
- 子任务 2(10 分):n≤100,m≤100,q≤100;
- 子任务 3(20 分):n≤2000,m≤2000;
- 子任务 4(30 分):n≤30000;
- 子任务 5(30 分):无特殊限制。