G. Lines
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given an array A with N numbers. There are Q queries which give you a number x. Print the index of A where (A[i] - x) * (A[i + 1] - x) is maximized.

Input

First line has N and Q, length of the array and number of queries. $$$1 \le N, Q \le 2 \cdot 10^5$$$

Second line has N space separated integers representing the array A. $$$1 \le A[i] \le 2 \cdot 10^5$$$

Next Q lines have one integer: X. $$$1 \le X \le 2 \cdot 10^5$$$

Output

Print Q lines, the answer for each query.

Example
Input
10 10
102392 37104 59879 14348 157814 183664 -60462 60677 -13277 -179147
-196790
194340
126649
121980
-141990
-18502
111378
51412
59177
75080
Output
5
9
9
9
5
5
9
9
9
9