В саду Bessie есть $N$ растений, пронумерованных от $1$ до $N$ ($2\leq N\leq 5\cdot 10^5$) слева направо. Bessie знает, что растению $i$ требуется не менее $w_i$ ($0\leq w_i \leq 10^6$) единиц воды. У Bessie очень необычная система полива с $N-1$ каналами, пронумерованными от $1$ до $N-1$. С каждым каналом $i$ связана стоимость за единицу $c_i$ ($1\le c_i\le 10^6$): Bessie может заплатить $c_i k$, чтобы предоставить каждому из растений $i$ и $i+1$ по $k$ единиц воды, где $k$ — неотрицательное целое число. Bessie занята и, возможно, не успеет использовать все каналы. Для каждого $2\leq i \leq N$ вычислите минимальную стоимость, необходимую для полива растений от $1$ до $i$ с использованием только первых $i-1$ каналов.

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

Вторая строка содержит $N$ целых чисел $w_1, \ldots, w_N$, разделённых пробелами. Третья строка содержит $N-1$ целых чисел $c_1, \ldots, c_{N-1}$, разделённых пробелами.

Третья строка содержит $N-1$ целых чисел $c_1, \ldots, c_{N-1}$, разделённых пробелами.

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

Выведите $N-1$ целых чисел, каждое в отдельной строке. $(i-1)$-е число должно содержать минимальную стоимость полива первых $i$ растений с использованием первых $i-1$ каналов.

Примеры

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

3
39 69 33
30 29

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

2070
2127

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

3
33 82 36
19 1

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

1558
676

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

8
35 89 44 1 35 3 62 50
7 86 94 62 63 9 49

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

623
4099
4114
6269
6272
6827
8827

Ограничения

• Входные данные 4: $N \leq 200$, и все $w_i \leq 200$.
• Входные данные 5–6: все $w_i \leq 200$.
• Входные данные 7–10: $N \leq 5000$.
• Входные данные 11–14: все $w_i$ и $c_i$ генерируются независимо и равномерно случайным образом.
• Входные данные 15–19: нет дополнительных ограничений.