Задача №114114. Вложенные коробки с конфетами
В качестве новогоднего подарка Андрей получил коробку с конфетами. Или не совсем коробку. На самом деле он быстро обнаружил, что внутри коробки находятся ещё несколько одинаковых коробок меньшего размера, внутри которых содержатся ещё меньшие коробки и так далее... Формально, скажем что конфета является коробкой уровня 0 , а коробка уровня i содержит в себе a i коробок уровня i - 1 . Коробка, подаренная Андрею, имеет уровень n .
Сегодня к Андрею в гости придут друзья и он хочет поделиться с ними некоторым количеством конфет, для чего ему придётся открыть некоторое количество коробок. Разумеется, Андрей не может открыть коробку, если она находится внутри ещё не открытой коробки. Ему хотелось бы знать, какое минимальное количество коробок ему потребуется открыть, чтобы достать x конфет. Поскольку Андрей ещё не уверен, сколько друзей к нему сегодня придут, он просит вас решить задачу для нескольких значений x .
В первой строке входных данных записаны числа n и m ( 1 ≤ n , m ≤ 300 000 ) — количество коробок и количество вопросов Андрея соответственно.
Во второй строке записаны n целых чисел a 1 , a 2 , ..., a n ( 1 ≤ a i ≤ 10 9 ).
В третьей строке записаны m чисел x 1 , x 2 ..., x m ( 1 ≤ x i ≤ 10 12 ) — значения количества конфет, для которых Андрей хочет знать ответ. Гарантируется, что каждое значение x i не превосходит общего число конфет в коробке уровня n .
Выведите m целых чисел, i -е из них должно равняться минимальному количеству коробок, которое потребуется открыть Андрею, чтобы получить хотя бы x i конфет.
Тесты к этой задаче состоят из четырёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых предыдущих групп, указанных в таблице ниже.
В первом примере единственная конфета спрятана в пяти уровнях коробок.
Во втором примере, чтобы получить 13 конфет, Андрей должен открыть самую большую коробку, затем две коробки уровня 2 , и, наконец, пять из шести имеющихся коробок уровня 1 .
5 1 1 1 1 1 1 1
5
3 3 3 3 3 2 8 13
3 5 8