По итогам переписи населения статистическое управление хранит не список жителей, а сводную таблицу: для каждого возраста указано, сколько жителей имеют этот возраст. Возраст — целое число полных лет.
Представим, что все жители выстроены в одну шеренгу по неубыванию возраста и пронумерованы слева направо, начиная с 1; порядок жителей одного возраста не важен, поскольку их возраст одинаков. Демографов интересует возраст жителей, стоящих на определённых местах шеренги: например, возраст жителя, стоящего ровно посередине, называется медианным возрастом.
По сводной таблице ответьте на Q вопросов вида «какой возраст у жителя, стоящего в шеренге на месте p?».
Формат входных данных
В первой строке записано целое число M (0 ≤ M ≤ 120) — наибольший возраст, учтённый в таблице. Во второй строке через пробел записаны M + 1 целых чисел c0, c1, …, cM (0 ≤ ci ≤ 109), где ci — количество жителей в возрасте i лет; хотя бы одно из этих чисел положительно. В третьей строке записано целое число Q (1 ≤ Q ≤ 1000) — количество вопросов. В четвёртой строке через пробел записаны Q целых чисел p1, p2, …, pQ (1 ≤ pj ≤ S), где S = c0 + c1 + … + cM — общее число жителей.
Формат выходных данных
Выведите Q строк: в j-й строке — возраст жителя, стоящего в шеренге на месте pj.
Пояснение к первому примеру. Шеренга выглядит так: 0 0 2 2 2 3 4 4 4 4. На местах 1, 3, 5, 6 и 10 стоят жители в возрасте 0, 2, 2, 3 и 4 лет.
| № | Входные данные | Выходные данные |
|
1
|
4
2 0 3 1 4
5
1 3 5 6 10
|
0
2
2
3
4
|
|
2
|
2
1000000000 1000000000 1000000000
3
1000000000 1000000001 3000000000
|
0
1
2
|
|
3
|
0
7
2
7 1
|
0
0
|