Bob breezed through the Missing Number 1 challenge, but that was too boring for him. So, he cranked up the difficulty: more numbers, more queries, and an even bigger challenge!

Now, he is on a new quest to find the ~K-th~ missing number, and he dared you to solve it faster than ever before.

Again, The list will contains distinct positive integers in increasing order. Some numbers are missing from the natural counting sequence, and Bob wants to find the one that comes ~K-th~ among those missing numbers.

Your task is to find the ~K-th~ missing number from a sorted list with new challenge!.

Input

• The first line contains two integers ~N~ and ~Q~ ~(1 ≤ N, Q ≤ 10^5)~. — ~N~ is the number of integers in the sorted list and ~Q~ is the number of queries Bob has.
• The second line contains ~N~ distinct positive integers: ~a_1, a_2, ..., a_n~ ~(1 ≤ a_1 < a_2 < ... < a_n ≤ 10^{18})~, sorted in ascending order.
• The next ~Q~ lines each contain a single integer ~K_i (1 ≤ K_i ≤ 10^{18})~ - For each Query, Bob wants to find the ~K-th~ missing positive integer that is not in the list.

Output

• Print ~Q~ lines, where the ~i-th~ line is the answer to the ~i-th~ query — the ~K_i-th~ missing number not in Bob list.

📌 Example

Input

4 3  
3 5 6 7  
2  
9  
4

Output

2
13
8