220_normalization_of_indicators

Нормализация показателей

Description

Разработчики сервиса сбора данных решили уменьшить количество возможных вариантов ответов. Для этого выбрали $n$ различных целых чисел — канонические варианты.

Но в системе уже имеется $m$ старых ответов. Для каждого их этих $m$ чисел необходимо найти ближайший из $n$ канонических вариантов, т.е. с минимальным модулем разности.

Input Format:

В первой строке записано целое число $n$ ($1 \le n \le 50,000$).

Во второй строке записаны $n$ целых чисел $a_1$ $a_2$ … $a_n$ — канонические ответы.

В третьей строке записано одно целое число $m$ ($1 \le m \le 50,000$).

В $j$-й из следующих $m$ строк записано одно целое число $b_{j}$.

Гарантируется, что все входные числа не превосходят $10^{6}$ по абсолютной величине.

Output Format:

Для каждого значения $b_j$ найдите каноническое значение (ближайшее). Если оптимальных значений несколько, выведите любое из них.

Example Test Cases

Example 1

Input:

6
-7 3 8 12 -3 -10
7
-12
13
-5
-3
5
-2
0

Output:

-10
12
-3
-3
3
-3
3

Example 2

Input:

5
20 -27 12 21 -7
12
-18
19
-27
-9
-26
-6
-2
-20
0
-3
16
-12

Output:

-27
20
-27
-7
-27
-7
-7
-27
-7
-7
20
-7

Example 3

Input:

16
-1 -20 -17 25 24 18 -12 -11 14 9 7 -2 -29 -13 29 6
7
-25
-14
20
-23
24
26
18

Output:

-29
-13
18
-20
24
25
18