問題文

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

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

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

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

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

入力

$LNQ$
$A_1{A}_2{A}_3\dots A_N$
$B_1{C}_1$
$B_2{C}_2$
$⋮$
$B_Q{C}_Q$

出力

合計 $Q$ 行出力してください。$i(1\le i\le 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