Дан непустой массив из n целых чисел, отсортированный по неубыванию, и k запросов. Числа в массиве могут повторяться.
Для каждого числа-запроса x найдите значение элемента массива, расстояние от которого до x наименьшее. Расстояние между числами v и x равно модулю их разности: |v − x|.
Если одинаково близки два разных значения, выберите меньшее. Например, для массива [1, 5] и запроса x = 3 ответ равен 1.
Все запросы относятся к исходному массиву. Массив во время обработки запросов не меняется.
Входные данные
В первой строке содержатся два целых числа n и k (1 ≤ n ≤ 105, 1 ≤ k ≤ 105) — длина массива и количество запросов.
Во второй строке содержатся n целых чисел — элементы массива, отсортированного по неубыванию.
В третьей строке содержатся k целых чисел — запросы. Все элементы массива и запросы по модулю не превосходят 2 · 109.
Выходные данные
Для каждого запроса выведите в отдельной строке значение ближайшего элемента. Выводить номер элемента не нужно.
| № | Входные данные | Выходные данные |
|
1
|
7 6
2 4 7 7 7 9 12
7 8 2 12 1 20
|
7
7
2
12
2
12
|
|
2
|
2 6
1 5
-2 1 3 4 5 9
|
1
1
1
5
5
5
|