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.