410729: GYM104094 E kex

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

E. kextime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

Consider the set of non-negative integers $$$A$$$. The minimum non-negative integer that does not occur in this set is considered, for example, in game theory, and is denoted as $$$\mathrm{mex}(A)$$$. For example, $$$\mathrm{mex}(\{0, 1, 2, 4, 5, 9\})=3$$$.

Ann has decided to generalize the concept of mex. Consider a positive integer $$$k$$$ and a set of non-negative integer $$$A$$$. Denote as $$$\mathrm{kex}(A,k)$$$ a non-negative integer that is $$$k$$$-th in ascending order among all integers that are not in $$$A$$$. For example, $$$\mathrm{kex}(\{0, 1, 2, 4, 5, 9\}, 2)=6$$$.

You must find $$$\mathrm{kex}(A, k_i)$$$ for the given set of integers $$$A$$$ and $$$q$$$ values of $$$k_i$$$.

Input

The first line of input contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 10^5$$$) — number of elements in $$$A$$$ and number of $$$\mathrm{kex}$$$ numbers, that you have to find.

In second line of input contains $$$n$$$ different not negative integers, each of which is at most $$$10^9$$$, — elements of $$$A$$$.

In third line of input contains $$$q$$$ integers $$$k_i$$$ ($$$1\leq k_i \leq 10^9$$$).

Output

Print values: $$$\mathrm{kex}(A, k_1), \mathrm{kex}(A, k_2),\ldots, \mathrm{kex}(A,k_q)$$$.

ExampleInput
4 10
1 2 6 7
1 2 3 4 5 6 7 8 10 11
Output
0 3 4 5 8 9 10 11 13 14 

加入题单

上一题 下一题 算法标签: