E. kex
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим множество неотрицательных целых чисел $$$A$$$. Минимальное неотрицательное целое число, которое не встречается в этом множестве, часто возникает, например, в теории игр, и обозначается как $$$\mathrm{mex}(A)$$$. Например, $$$\mathrm{mex}(\{0, 1, 2, 4, 5, 9\})=3$$$.

Аня решила обобщить понятие mex. Рассмотрим целое положительное число $$$k$$$ и множество целых неотрицательных чисел $$$A$$$. Обозначим как $$$\mathrm{kex}(A, k)$$$ неотрицательное целое число, которое является $$$k$$$-м по возрастанию среди всех чисел, не входящих в $$$A$$$. Например, $$$\mathrm{kex}(\{0, 1, 2, 4, 5, 9\}, 2)=6$$$.

Требуется найти $$$\mathrm{kex}(A, k_i)$$$ для заданного множества $$$A$$$ и $$$q$$$ значений $$$k_i$$$.

Входные данные

В первой строке входных данных дано два числа $$$n$$$ и $$$q$$$ ($$$1 \leqslant n, q \leqslant 10^5$$$) — количество элементов во множестве $$$A$$$ и количество значений $$$\mathrm{kex}$$$, которое надо найти.

Во второй строке в порядке возрастания даны $$$n$$$ различных чисел, не превышающих $$$10^9$$$, — элементы множества $$$A$$$.

В третьей строке даны $$$q$$$ чисел $$$k_i$$$ ($$$1\leqslant k_i \leqslant 10^9$$$).

Выходные данные

Выведите $$$q$$$ значений: $$$\mathrm{kex}(A, k_1), \mathrm{kex}(A, k_2),\ldots, \mathrm{kex}(A, k_q)$$$.

Пример
Входные данные
4 10
1 2 6 7
1 2 3 4 5 6 7 8 10 11
Выходные данные
0 3 4 5 8 9 10 11 13 14