問題文

高橋君は目$grep$が得意である。しかしこの世には目$grep$が得意な人が大勢いて特技にならないため、高橋君は新たな技を習得すべく$grep$コマンドのマニュアルを目$grep$していた。

検索コマンド $grep$ には $\-B$ と $\-A$ というオプションがある。これは、
$grep$ $\-B$ $x$ $\-A$ $y$ $"needle"$ $kakikomi.txt$ とすると ファイル$kakikomi.txt$ でパターン $"needle"$ にヒットした行だけでなく、その行の直前 $x$ 行, 直後 $y$ 行をあわせて表示するというものである。直前直後にある行数が$x,y$に満たない場合、あるだけ表示する。

同じ行番号の行が複数回表示されることになった場合、これらはマージされ、全体で1回ずつしか現れないようになる。この挙動については出力例の説明が詳しい。

今、ファイル$kakikomi.txt$ に対してあるパターンで$grep$を実行し、ヒットする行番号のリスト $L_1,L_2,...,L_n$ がわかっているものとする。ここに $m$ 個のクエリが与えられ、それぞれx,yが指定される。各クエリについて、$\-B$ $x$ $\-A$ $y$のオプションをつけて同様に$grep$を実行した場合、表示される行数を答えよ。

入力

入力は以下の形式で標準入力から与えられる。$all$ $N$ $M$ $L_{1}$ $L_{2}$ : $L_{N}$ $x_{1}$ $y_{1}$ $x_{2}$ $y_{2}$ : $x_{M}$ $y_{M}$

1. $1$ 行目には $kakikomi.txt$ の行数を表す整数 $all(1≦all≦10^9)$、ヒットした行数を表す整数 $N(1≦N≦min(all,10^5))$ 、クエリ$x, y$ の個数を表す整数 $M(1≦M≦10^5)$ が与えられる。
2. $2$ 行目から $N+1$ 行までの $N$ 行では、$i$ 番目にヒットした行の行番号を表す整数 $L_{i}(1≦L_{i}≦all)$ が与えられる。

• $L_i$ は $L_i < L_{i+1}$を満たす。

4. $N+2$ 行目から $N+M+1$ 行までの $M$ 行では、$L_i$ に対する各クエリを表す整数 $x_i, y_i(0≦x_i, y_i≦10^9)$ が与えられる。

出力

各クエリ$x, y$ に対して表示される行数をそれぞれ$1$ 行で出力すること。
また、出力の最後には改行をいれること。

入力例 1

7 2 3
2
4
1 1
3 0
3 4

出力例 1

5
4
7

• ヒットした行は、 $2$ 行目と $4$ 行目である。
• $x = 1, y = 1$ のとき、それぞれのヒット範囲は、 $1$ ～ $3$ 行目、$3$ ～ $5$ 行目なので、合わせて $5$行が答えとなる。
• $x = 3, y = 0$ のとき、それぞれのヒット範囲は、 $1$ ～ $2$ 行目、$1$ ～ $4$ 行目なので、合わせて $4$行が答えとなる。
• $x = 3, y = 4$ のとき、それぞれのヒット範囲は、 $1$ ～ $6$ 行目、$1$ ～ $7$ 行目なので、合わせて $7$行が答えとなる。

入力例 2

100 5 5
3
18
24
57
90
1 8
27 0
15 16
22 3
2 2

出力例 2

46
80
98
79
25