Производитель чая рашил организовать огромную церемонию дегустации чая. \(n\) дегустаторов будут пробовать \(n\) сортов чая. И сорта чая, и дегустаторы пронумерованы от \(1\) до \(n\). Производитель подготовил \(a_i\) миллилитров \(i\)-го сорта чая. \(j\)-й дегустатор способен выпить \(b_j\) миллилитров чая за раз.
Дегустация будет происходить по этапам. На первом этапе \(i\)-й дегустатор попробует \(i\)-й сорт чая. \(i\)-й дегустатор выпивает \(\min(a_i, b_i)\) чая (сколько доступно \(i\)-го сорта чая и сколько \(i\)-й дегустатор способен выпить). \(a_i\) также уменьшается на это количество.
Затем все дегустаторы переходят к предыдущему сорту чая. Тогда на втором этапе \(i\)-й дегустатор пробует \((i-1)\)-й сорт чая. \(i\)-й дегустатор выпивает \(\min(a_{i-1}, b_i)\) чая. \(1\)-й дегустатор заканчивает дегустацию.
На третьем этапе \(i\)-й дегустатор пробует \((i-2)\)-й сорт чая. \(2\)-й дегустатор заканчивает дегустацию. Это продолжается, пока все дегустаторы не закончат дегустацию.
Рассмотрим процесс дегустации для \(n = 3\), \(a = [10, 20, 15]\), \(b = [9, 8, 6]\). В левом столбце записаны текущие количества каждого сорта чая. В правом столбце записаны текущие выпитые количества чая для каждого дегустатора. Стрелка указывает, какой дегустатор пьет каждый чай на текущем шаге. Число на стрелке — это количество — минимум из того, сколько доступно сорта чая, и того, сколько может выпить дегустатор.
Для каждого дегустатора выведите, сколько миллилитров чая он/она суммарно выпьет.
Выходные данные
На каждый набор входных данных выведите \(n\) целых чисел — \(i\)-е значение должно быть равно суммарному количеству чая, выпитому \(i\)-м дегустатором.
Примечание
Первый набор входных данных описан в условии. Здесь предоставлены оставшиеся количества каждого сорта чая после каждого этапа и количество выпитого каждым дегустатором чая:
- \(a = [1, 12, 9]\), \(\mathit{ans} = [9, 8, 6]\)
- \(a = [0, 6, 9]\), \(\mathit{ans} = [9, 9, 12]\)
- \(a = [0, 6, 9]\), \(\mathit{ans} = [9, 9, 12]\)
Во втором наборе входных данных единственный дегустатор выпьет \(\min(5, 7)\) миллилитров чая единственного сорта.
Здесь предоставлены оставшиеся количества каждого сорта чая после каждого этапа и количество выпитого каждым дегустатором чая для третьего набора входных данных:
- \(a = [10, 4, 3, 3]\), \(\mathit{ans} = [3, 4, 2, 1]\);
- \(a = [6, 2, 2, 3]\), \(\mathit{ans} = [3, 8, 4, 2]\);
- \(a = [4, 1, 2, 3]\), \(\mathit{ans} = [3, 8, 6, 3]\);
- \(a = [3, 1, 2, 3]\), \(\mathit{ans} = [3, 8, 6, 4]\).
Здесь предоставлены оставшиеся количества каждого сорта чая после каждого этапа и количество выпитого каждым дегустатором чая для четвертого набора входных данных:
- \(a = [999999999, 999999999, 0]\), \(\mathit{ans} = [1, 1, 1000000000]\);
- \(a = [999999998, 0, 0]\), \(\mathit{ans} = [1, 2, 1999999999]\);
- \(a = [0, 0, 0]\), \(\mathit{ans} = [1, 2, 2999999997]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3
10 20 15
9 8 6
1
5
7
4
13 8 5 4
3 4 2 1
3
1000000000 1000000000 1000000000
1 1 1000000000
|
9 9 12
5
3 8 6 4
1 2 2999999997
|