Городские олимпиады/1-2 курсы/Предметная олимпиада по информатике 2019


6. Сборка ёлки (100 баллов)

Автор задачи: Соловьёв Виктор
Ограничение по времени: 1 с.
Ограничение по памяти: 256 МБ

Уже который год Виктор использует на Новый год искусственные ели. Искусственная ель, которую он собирает в этом году, состоит из ствола, являющегося цельной деталью, и множества ветвей, вставляемых в пазы на стволе.

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

У Виктора есть n веток, которые перемешались между собой. Зная, сколько веток должно быть на каждом ярусе, он хочет подобрать длины веток для каждого из них. Каждый ярус, при этом, должен быть полностью заполнен.

Среди веток могут оказаться лишние, оставшиеся от предыдущих пришедших в негодность ёлок.

Входные данные

Первая строка содержит одно целое число n — количество ярусов (1 \leqslant n \leqslant 10^{5}).

Вторая строка содержит n целых чисел k_{i}, разделённых пробелами — количество веток на i-м ярусе в порядке возрастания значения i (1 \leqslant k_{i} \leqslant 10^{5}).

Третья строка содержит одно целое число m — количество веток (1 \leqslant m \leqslant 10^{5}).

Четвёртая строка содержит m разделённых пробелами целых чисел l_{i} — длины веток (1 \leqslant l_{i} \leqslant 10^{9}).

Выходные данные

Необходимо вывести через пробел n целых чисел — длины веток на каждом ярусе в порядке от первого к последнему. Если возможно несколько вариантов ответа — разрешается вывести любой. Гарантируется существование хотя бы одного способа собрать ёлку из имеющихся ветвей.

Примеры
Стандартный вводСтандартный вывод
3
1 2 3
6
8 11 5 8 11 11
5 8 11
3
2 1 3
6
7 9 7 9 9 7
7 7 9
4
6 6 6 8
32
2 4 5 6 4 6 6 4 6 4 3 4 4 3 6 3 4 4 6 3 4 4 5 3 3 4 4 2 6 6 5 7
3 4 4 6
Примечания

Решения, правильно работающие в случаях, когда лишних ветвей нет, а на всех ярусах ели длины ветвей различны, будут оцениваться из 35 баллов.

Решения, правильно работающие во всех случаях, когда лишних ветвей нет, будут оцениваться из 75 баллов.

Решения, которые правильно работают во всех случаях, будут оцениваться из 100 баллов.