Algorithms and Data Structures

# Upper bound

Given an array of `n` integers, you are asked to answer `q` queries. Each query is of the form “What is the smallest number that is larger than `x` in the given list?”.

#### Input

The first line of the input contains two integers `n` (2 ≤ n ≤ ) and `q` (1 ≤ q ≤ ).
The next line contains `n` space-separated integers () in an increasing order.
The final line contains `q` space-separated queries ( < ).

#### Output

The program should print `q` lines. Each line should contain the answer for the corresponding query.

#### Examples

 Input Output 6 3 2 7 9 10 20 30 8 20 1 9 30 2
Hint
In the classical implementation of the binary search, we consider the range `[l; r)` where `l` is inclusive and `r` is not. In some cases, you might want to have `(l; r]` instead - exclude `l` and include `r`. This will require some changes in calculating the `l`, `r`, and `mid` points.

#### Constraints

Time limit: 0.5 seconds

Memory limit: 512 MB

Output limit: 1 MB