ストーリー

ここは, サクラタウン. 住民はたくさんいるのだが, 真夜中になると, この街は静寂に包まれる.

問題文

サクラタウンは東西方向に一直線に伸びる街であり, その長さは $A$ である. サクラタウンでは, 最西端から $x$ の地点のことを座標 $x$ と呼ぶ.

サクラタウンには $N$ 人の人がいて, $i~(1 \leq i \leq N)$ 番目の人は街の座標 $X_i$ にいる.

サクラタウンにおいて, 全部で $T$ 個の音が発生した. $t~(1 \leq t \leq T)$ 番目の音について, 以下の特徴があった.

• この音が発生した時刻は $t$ である.
• 座標 $L_t$ 以上 $R_t$ 以下の地点にいる人全員に, そしてその座標にいた人に限り, この音を聞いた

サクラタウンにいる $N$ 人について, $i=1,2, \dots, N$ それぞれに対して, 以下の質問 $i$ に答えよ.

• 質問 $i$: $i$ 番目の人は発生した $T$ 個の音のうち, $1$ 個以上の音を聞いたか? もし聞いたのであるならば, 最後に聞いた音が発生した時刻を求めよ.

ただし, この問題では以下を仮定する.

• $1$ 以上 $T$ 以下の整数 $t$ に対して, 時刻 $t$ にはそれ以前に発生した $(t-1)$ 個の音は全て全員聞こえなくなっている.

制約

• $1 \leq N \leq 10^5$.
• $1 \leq A \leq 10^9$.
• $0 \leq X_i \leq A \quad (i=1,2, \dots, N)$.
• $1 \leq T \leq 10^5$.
• $0 \leq L_t \leq R_t \leq A \quad (t=1,2, \dots, T)$.
• 入力はすべて整数

入力

$N$ $A$
$X_1$ $X_2$ $\cdots$ $X_N$
$T$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_T$ $R_T$

出力

出力は $N$ 行からなる. 第 $i~(1 \leq i \leq N)$ 行目に質問 $i$ に対する解答について, $1$ 個以上の音を聞いた場合は最後に聞いた音が発生した時刻を整数で出力せよ. もし, $1$ 個も音を聞いていない場合は -1 を出力せよ.

サンプル

4 15
3 8 11 14
4
1 6
12 14
7 10
5 9

1
4
-1
2

1 1000000000
500000000
1
499999999 500000001

1