問題文

数直線上に 1,2, \ldots, N と番号がついた N 匹のヤギがいます。ヤギ i ははじめ座標 A_i にいます。ここで、ヤギははじめ相異なる座標にいることが保証されます。

以下の Q 個のクエリを i=1,2,\ldots,Q の順に処理してください。

座標 B_i に先生がエサを置き、エサからの距離が最も小さいヤギがエサを食べます。ただし、そのようなヤギが複数いる場合は、そのようなヤギの中で番号が最も小さいヤギがエサを食べます。また、座標 X と座標 Y の距離は \lvert X-Y \rvert であるとします。

それぞれのエサを食べるヤギの番号を求めてください。ただし、エサを食べたヤギはエサのある座標に移動し、そのままそこに残るものとします。

制約

• 1 \leq N,Q \leq 2 \times 10^5
• -10^{18} \leq A_i \leq 10^{18} (1 \leq i \leq N)
• A_i \neq A_j (1 \leq i < j \leq N)
• -10^{18} \leq B_i \leq 10^{18} (1 \leq i \leq Q)
• 入力は全て整数

入力例 1

5
10 7 21 2 13
4
11 9 17 16

出力例 1

1
1
3
3

1 つ目のクエリでは、エサが置かれる 11 に最も近い 10 にいるヤギ 1 がエサを食べ、 11 に移動します。

2 つめのクエリでは、エサが置かれる 9 に近いヤギは 7 にいるヤギ 2 と 11 にいるヤギ 1 がいます。そのため、より番号の小さいヤギ 1 がエサを食べ、 9 に移動します。