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.