#561. 「LibreOJ Round #9」CommonAnts 的调和数

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

题目描述

你有一个长为 n 的序列 \{a_i\}(1\le i\le n) ,初始时 a_i=0

现在某人对这个序列做了 m 次修改,每次选择两个正整数 p,x ,对于每个 1\le j\le \lfloor \frac{n}{p} \rfloor a_{pj} 加上 x\cdot j \cdot 表示乘积)。

接着某人有 q 次询问,每次询问给出一个正整数 k ,要求出 \sum_{j=1}^{\lfloor \frac{n}{k} \rfloor} j\cdot a_{kj} \bmod 998244353

为了降低难度,某人会使 p k 有较多的公因子。具体而言,保证修改和询问中所有 p k 的最小公倍数的质因子种类数不超过 10

输入格式

第一行三个正整数 n,m,q 表示序列长度,修改个数和询问个数。

接下来 m 行每行两个正整数 p_i,x_i 表示一次修改;

接下来 q 行每行一个正整数 k_i 表示一组询问。

输出格式

输出共 q 行,每行一个整数 \mathrm{ans}_i 表示答案模 998244353 的值。

样例

样例输入

12 5 12
2 9
3 3
4 1
5 2
6 4
1
2
3
4
5
6
7
8
9
10
11
12

样例输出

2134
1017
412
326
100
191
0
38
9
49
0
77

数据范围与提示

对于所有数据, 1\le p_i,k_i \le n\le 10^9,1\le m,q\le 2\times 10^5,0\le x_i\le 10^9

子任务编号 分值 n \leq m,q\leq
1 15 10^3 10^3
2 10^9
3 10^6 2\times 10^5
4 20 10^7
5 35 10^9