問題文

Discord サーバー「あさかつ」では、多様な需要に合わせて難易度の異なる $N$ 個のバーチャルコンテストを開催しています。
各コンテストは $M$ 問からなり、$i$ 個目のコンテストの $j$ 問目の難易度は $D_{i,j}$ です。
ここで、$D_{i,j}$ について以下が成り立つことが保証されます。

• $D_{i,j}\le D_{i,j+1}$ $(1\le i\le N,\ 1\le j\lt M)$
• $D_{i,j}\le D_{i+1,j}$ $(1\le i\lt N,\ 1\le j\le M)$
• 各 $i$ $(1\le i\le N)$ について、$D_{i,1},D_{i,2},\dots,D_{i,M}$ はこの順に等差数列をなす

ただし、入力では $D_{i}$ の初項 $A_i$ と公差 $B_i$ のみが与えられ、$D_{i,j}$ の値は陽に与えられません。

hibit 君はこれらのコンテストに延べ $Q$ 回参加することにしました。
hibit 君の $1$ 回目のコンテスト参加前のレートは $X$ であり、$i$ 番目のコンテストに参加をする度にレートが $C_i$ 増加します。

入力

$N$ $M$
$A_{1}$ $B_{1}$
$A_{2}$ $B_{2}$
$\vdots$
$A_{N}$ $B_{N}$ 
$Q$ $X$
$C_1$ $C_2$ $\dots$ $C_N$

• 入力はすべて整数
• $2 \leq N\leq 10^5$
• $2 \leq M\leq 10^9$
• $1 \leq Q \leq 2\times 10^5$
• $0 \leq X \leq 10^9$
• $D_{i,j}=A_{i}+(j-1)B_{i}$ とした時以下が成立
• $0 \leq D_{i,j} \leq 10^9$ $(1\le i\le N,1\le j\le M)$
• $D_{i,j}\le D_{i,j+1}$ $(1\le i\le N,\ 1\le j\lt M)$
• $D_{i,j}\le D_{i+1,j}$ $(1\le i\lt N,\ 1\le j\le M)$
• $0 \leq C_i \leq 10^9$ $(1\le i\le N)$

出力

$q=1,2,\dots,Q$ に対して、答えを空白区切りで出力せよ。

サンプル

3 3
1 2
6 0
7 1
2 4
3 1 4

1 2

6 4
0 5
0 6
1 7
6 6
6 10
9 9
5 11
1 12 13 11 25 14

1 1 4 4 6

4 4
0 0
1 1
3 3
5 5
4 4229
1 10 100 1000

4 4 4 4