410653: GYM104069 E El Classificador

Lucas El Classificador Harada is a member of the MaratonUSP group and creator of a famous algorithm known as Classificador. Given a list a with size $$$m$$$ and an integer $$$x$$$ the algorithm finds the first integer of this list that is greater than or equal to $$$x$$$ and removes it.

The MaratonUSP ordered $$$n$$$ sneakers of the same model but in different sizes. In total $$$q$$$ clients will buy the product. Each client has a minimum size of sneakers that would like to get and Lucas must use his Classificador criterion to manage the inventory. As the inventory may be very large, you must help Lucas to make an efficient program that says which size of sneakers each client must buy.

The first line has two integers $$$n, q (1\leq n,q \leq 2 \cdot 10^5)$$$ - the number of sneakers bought and the number of clients, respectively.

The next line has n integers $$$l_1,l_2,\dots, l_n (1\leq l_i \leq 10^9$$$) - the size of sneakers initially in inventory.

The next line has q will be a number integer x integers ($$$1\leq x \leq 10^9$$$) representing the minimum size of sneakers that the client wants.

Print $$$q$$$ lines, $$$i$$$-th line should contain the size of the sneakers that the $$$i$$$-th client will buy. In case there aren't any sneakers in the inventory for this client, print $$$-1$$$.

2 3
4 4
3
4
4

4
4
-1

3 5
1 2 3
2
1
3
5
1

2
1
3
-1
-1

5 6
10 5 7 1 7
6
2
15
8
1
1

7
5
-1
10
1
7

On testcase 1, initially there are two sneakers of size 4. The first client wants a sneaker of size at least 3, then takes one of size 4. The second client takes the last one of size 4. Since MaratonUSP is out of sneakers, the third client takes nothing.