Задача A3. Гражданская оборона

Автор:Восьмая всероссийская командная олимпиада школьников по программированию   Ограничение времени:2 сек
Входной файл:shelter.in   Ограничение памяти:256 Мб
Выходной файл:shelter.out  

Условие

Штаб гражданской обороны Тридесятой области решил обновить план спасения на случай ядерной атаки. Известно, что все n селений Тридесятой области находятся вдоль одной прямой дороги. Вдоль дороги также расположены m бомбоубежищ, в которых жители селений могут укрыться на случай ядерной атаки.

Чтобы спасение в случае ядерной тревоги проходило как можно эффективнее, необходимо для каждого селения определить ближайшее к нему бомбоубежище.

Формат входного файла

Первая строка входного файла содержит число n — количество селений. Вторая строка содержит n различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до i-го селения.

Третья строка входного файла содержит число m — количество бомбоубежищ. Четвертая строка содержит m различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до i-го бомбоубежища.

Формат выходного файла

Выведите в выходной файл n чисел — для каждого селения выведите номер ближайшего к нему бомбоубежища. Бомбоубежища пронумерованы от 1 до m в том порядке, в котором они заданы во входном файле.

Ограничения

1 ≤ n, m ≤ 100 000

Все расстояния положительны и не превышают 109. Селение и убежище могут располагаться в одной точке.

Примеры тестов

Входной файл (shelter.in) Выходной файл (shelter.out)
1
4
1 2 6 10
2
7 3
2 2 1 1

0.094s 0.023s 15