Số dương bị thiếu thứ k (Kth Excluded)

Nguồn: AtCoder

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho dãy tăng nghiêm ngặt gồm $N$ số nguyên dương:

Có $Q$ truy vấn. Với truy vấn thứ $i$, cho số nguyên dương $K_i$. Hãy tìm số nguyên dương nhỏ thứ $K_i$ không bằng bất kỳ phần tử nào của $A$.

Input

Dòng đầu chứa $N$ và $Q$.

Dòng thứ hai chứa $A_1,\ldots,A_N$.

$Q$ dòng tiếp theo, dòng thứ $i$ chứa $K_i$.

Output

Với mỗi truy vấn, in đáp án trên một dòng.

Subtask

• 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}$.

Ví dụ

Input

4 3
3 5 6 7
2
5
3

Output

2
9
4

Giải thích

Các số dương không thuộc $A$ là $1,2,4,8,9,10,\ldots$. Vì vậy số thiếu thứ $2$, $5$, $3$ lần lượt là $2$, $9$, $4$.