Upper bound

Given an array of sorted n integers, you are asked to answer q queries. Each query is of the form β€œWhat is the first number 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: 5 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in