# C. CommonAnts 的调和数

#### 样例输入

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 $15$ $10^3$ $10^3$
2 $15$ $10^9$ $10^3$
3 $15$ $10^6$ $2\times 10^5$
4 $20$ $10^7$ $2\times 10^5$
5 $35$ $10^9$ $2\times 10^5$