Description

Secret Number is a number guessing game where the questioner thinks of a number between 1 and 100. We can ask about a number, and the questioner will tell us if it is higher or lower than his number.

We know that the fastest way to guess the number is by asking about the middle value each time, reducing the options by half. This idea is called Binary Search.

 

Now there is a questioner who also cannot answer you, and this game will be played T times. Each time you will receive a number M, and you need to find its position P in a sorted array A of length N.

However, since the questioner is careless, the given number M might not exist in the array. In this case, you need to find the position P of number K in array A that has the smallest difference with M.
If two numbers have the same minimum difference from K, output the position of the smaller one.

 

Hint:
If you get a TLE, try to think about how to use the number guessing game strategy to quickly find M.

Input

The first line contains two integers N and T. N represents the length of the array, and T represents the number of games to be played.

The second line contains N numbers, representing the numbers A_i in the array, guaranteed to be sorted in increasing order. Each number appears only once.

The following T lines each contain a number M_j , representing the number to find in the jth round.

Constraints

• 1 ≤ T ≤ 10⁵
• 1 ≤ N ≤ 10⁶
• 0 ≤ A_i ≤ 10⁹
• 1 ≤ P ≤ N

​Subtasks

• Testcases 1 ~ 2: 1 ≤ N, T ≤ 1000
• Testcases 3 ~ 6: 1 ≤ T ≤ 10⁵, 1 ≤ N ≤ 10⁶, M is guaranteed to be in array A.
• Testcases 7 ~ 10: No additional restrictions.

 

Output

Output T lines, each containing a number P_j, representing the position of K_j in the array for the jth round.

 

Please remember to print "\n" at the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss