Implement an approximate binary search algorithm.
Input:
- the first line of the input contains numbers N and K (\(0< N,\ K < 100001\));
- the second line contains N numbers of the first array, sorted in non-decreasing order;
- the third line contains K numbers of the second array.
Each number in both arrays does not exceed \(2 \cdot 10^9\).
Output: For each of the K numbers, print the number from the first array that is closest to the given number on a separate line. If there are several of them, print the smallest one.
Examples
| # |
Input |
Output |
| 1 |
5 5
1 3 5 7 9
2 4 8 1 6
|
1
3
7
1
5 |