423. Ближайшая остановка

В Берляндии есть проспект Берленина, по которому ходит автобус. Проспект можно считать прямой, вдоль которой введена система координат. Всего на проспекте есть $n$ остановок, $i$-я из которых находится в точке с координатой $a_i$.

Паша пишет новое приложение для отслеживания автобусов и хочет рисовать иконку автобуса около ближайшей остановки. Формально, если автобус имеет координату $x$, то выбирается номер остановки $i$, минимизирующий $|a_i – x|$. Если таких $i$ несколько, то Паша выбирает номер нужной остановки по очень странным правилам:

0. Если есть остановки, совпадающие с координатой автобуса, то стоит вывести минимальную по номеру среди них.
1. Если есть остановки справа и слева, то стоит вывести максимальную по номеру среди левых.
2. Если есть остановки только слева, то стоит вывести максимальную по номеру среди левых.
3. Если есть остановки только справа, то стоит вывести минимальную по номеру среди правых.

Пашино приложение ещё не готово до конца, поэтому он просит вас помочь разработать эту функциональность. Для теста он выдал вам $k$ запросов, каждый из которых задаётся числом $x$ — координатой автобуса.

В первой строке входных данных содержатся числа $n$ и $k$ $(1 \leq n,k \leq 10^5)$ — количество остановок и запросов соответственно. Во второй строке задаётся $n$ целых чисел, отсортированных по неубыванию, — $a_i$, а в третьей строке — $k$ запросов, каждый из которых составляет координату автобуса. Каждое число находится в промежутке $[–2 \cdot 10^9; 2 \cdot 10^9]$.

Для каждого запроса выведите номер нужной остановки $i$ ($1 \le i \le n$).

В примере даны остановки с координатами $1, 3, 5$.

Для первого запроса автобус находится в точке $4$ и расстояния до остановок от него равны $3$, $1$ и $1$ соответственно. Это значит, что существуют оптимальные остановки слева (остановка с номером 2) и справа (остановка с номером 3), а значит нужно выбрать максимальную по номеру среди левых - 2.

Во время второго запроса автобус находится в точке 1, а значит существует всего одна остановка, минимизирующая заданное расстояние.