問題文

寿司取るな君は回転寿司店を営んでおり、寿司は環状のレーンによって客に届けられます。

レーンの長さは $L$ であり、$1$ 秒あたり長さ $1$ 動く速さで回っています。
初め、レーンは反時計回りに回っていますが、動く向きが反対になるタイミングが $N$ 回存在します。
$i \, (1 \leq i \leq N)$ 回目の切り替わりは時刻 $A_i$ に起こります。

また、レーンの周りには $L$ 個の椅子が等間隔に並んでおり、反時計回りに $0, 1, 2, \dots, L - 1$ と番号付けられています。

寿司取るな君は、客の注文に素早く対応するためのトレーニングとして、$Q$ 回からなる思考実験を行うことにしました。
$i \, (1 \leq i \leq Q)$ 回目の思考実験では、客が椅子 $x_i$ の前に、時刻 $t_i$ に訪れます。
寿司取るな君は、時刻 $t_i$ 以降（客が訪れた瞬間でも構いません）、注文された寿司を椅子 $0$ の前のレーン上に置くことができます。
客は、寿司が自分の目の前に来た瞬間に寿司を取ることができます。客が訪れた瞬間、あるいは寿司取るな君が寿司を置いた瞬間であってもよいです。
寿司取るな君は、彼が最適な時刻に寿司を置くとき、客が訪れてから寿司を取るまでの時間の最小値を求めたいです。

ただし、入力では直接的には $x_i, t_i$ の値は与えられません。これらの値を計算するための整数 $B_i, C_i$ が与えられるので、以下のように $x_i, t_i$ を定めてください。

入力

$L\, N\, Q$
$A_1 \, A_2 \, A_3 \, \dots \, A_N$
$B_1 \, C_1$
$B_2 \, C_2$
$\vdots$
$B_Q \, C_Q$

出力

合計 $Q$ 行出力してください。$i \,\, (1\leq i \leq Q)$ 行目には $i$ 回目の思考実験に対する答えを出力してください。 最後に改行してください。

サンプル

10 3 3
1 5 16
8 0
2 5
3 9

3
5
4

20 2 1
5 6
7 0

9