Kth Excluded

Source: AtCoder

Version: Phuoc Hung OJ Extended

Problem Statement

You are given a strictly increasing sequence of $N$ positive integers. For query $i$, you are given a positive integer $K_i$. Find the $K_i$-th smallest positive integer that is different from every element of the sequence.

Input

The first line contains $N$ and $Q$.

The second line contains $A_1,\ldots,A_N$.

The next $Q$ lines contain $K_1,K_2,\ldots,K_Q$, one value per line.

Output

Print one answer per query.

Subtasks

• Subtask 1 — 20%: $N,Q\le1000$, $A_i,K_i\le10^6$.
• Subtask 2 — 30%: $N,Q\le30000$, $A_i,K_i\le10^{18}$.
• Subtask 3 — 50%: $1\le N,Q\le10^5$, $1\le A_1<\cdots<A_N\le10^{18}$, $1\le K_i\le10^{18}$.

Examples

Input

4 3
3 5 6 7
2
5
3

Output

2
9
4

Explanation

The missing positive integers are $1,2,4,8,9,10,\ldots$.