题目描述

你有一个长为 $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$ 的值。

样例

input

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

output

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$。