Задача
На планете Шелезяка поднялась буря из алмазной пыли. Как известно, алмазная пыль вызывает у роботов паралич. В момент начала бури все роботы были заняты работой вдоль одной прямой дороги. Вдоль этой же дороги расположены m ремонтных мастерских. Поэтому было решено направить каждого робота в ближайшую ремонтную мастерскую, чтобы обновить свою смазку.
Необходимо для каждого робота определить ближайшую к нему ремонтную мастерскую.
Входные данные
В первой строке вводится число
n - количество роботов(
\(1 <= n <= 100000\)). Вторая строка содержит
n различных целых чисел,
i-е из этих чисел задает расстояние от начала дороги до места работы
i-го робота. В третьей строке входных данных задается число
m - количество ремонтных мастерских (
1 <= m <= 100000). Четвертая строка содержит
m различных целых чисел,
i-е из этих чисел задает расстояние от начала дороги до
i-й ремонтной мастерской. Все расстояния положительны и не превышают
109. Робот и мастерская могут располагаться в одной точке.
Выходные данные
Выведите
n чисел - для каждого робота выведите номер ближайшей к нему ремонтной мастерской. Ремонтные мастерские пронумерованы от
1 до
m в том порядке, в котором они заданы во входных данных.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4
1 2 6 10
2
7 3 |
2 2 1 1 |