EduBrick

Какая это глава

5000 мс · 256 МБ · всё или ничего

В книге nn глав, в ii-й главе cic_i страниц. Главы идут подряд: первая начинается со страницы 1.

Для каждого из qq запросов — номера страницы — выведите номер главы, на которой открыта книга.

Формат ввода

В первой строке число nn от 11 до 21052 \cdot 10^5. Во второй — nn чисел от 11 до 10910^9. В третьей — число qq от 11 до 10510^5. В четвёртой — qq номеров страниц, каждый от 1 до общего числа страниц.

Формат вывода

qq чисел через пробел.

Примеры

ввод
3
3 1 4
6
3 3 7 7 3 5
вывод
1 1 3 3 1 3

Примечание

Постройте накопленные суммы длин глав. Тогда номер главы — это первое место, где накопленная сумма достигла номера страницы.

Войдите, чтобы отправлять решения.