C. CommonAnts 的调和数

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

题目描述

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

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

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

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

输入格式

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

接下来 mm 行每行两个正整数 pi,xip_i,x_i 表示一次修改;

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

输出格式

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

样例

样例输入

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

数据范围与提示

对于所有数据,1pi,kin109,1m,q2×105,0xi1091\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

子任务编号 分值 nn \leq m,qm,q\leq
1 1515 10310^3 10310^3
2 1515 10910^9 10310^3
3 1515 10610^6 2×1052\times 10^5
4 2020 10710^7 2×1052\times 10^5
5 3535 10910^9 2×1052\times 10^5