Le jardin de Bessie possède $N$ plantes numérotées de $1$ à $N$ ($2\leq N\leq 5\cdot 10^5$) de gauche à droite. Bessie sait que la plante $i$ a besoin d'au moins $w_i$ ($0\leq w_i \leq 10^6$) unités d'eau. Bessie dispose d'un système d'irrigation très particulier avec $N-1$ canaux, numérotés de $1$ à $N-1$. Chaque canal $i$ a un coût unitaire associé $c_i$ ($1\le c_i\le 10^6$), de sorte que Bessie peut payer $c_i k$ pour fournir aux plantes $i$ et $i+1$ chacune $k$ unités d'eau, où $k$ est un entier non négatif. Bessie est occupée et n'aura peut-être pas le temps d'utiliser tous les canaux. Pour chaque $2\leq i \leq N$, calculez le coût minimal nécessaire pour arroser les plantes de $1$ à $i$ en utilisant uniquement les $i-1$ premiers canaux.

Entrée

La deuxième ligne contient $N$ entiers $w_1, \ldots, w_N$ séparés par des espaces. La troisième ligne contient $N-1$ entiers $c_1, \ldots, c_{N-1}$ séparés par des espaces.

La troisième ligne contient $N-1$ entiers $c_1, \ldots, c_{N-1}$ séparés par des espaces.

Sortie

Affichez $N-1$ entiers, chacun sur une ligne distincte. Le $(i-1)$-ième entier doit être le coût minimal pour arroser les $i$ premières plantes en utilisant les $i-1$ premiers canaux.

Exemples

Entrée 1

3
39 69 33
30 29

Sortie 1

2070
2127

Entrée 2

3
33 82 36
19 1

Sortie 2

1558
676

Entrée 3

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

Sortie 3

623
4099
4114
6269
6272
6827
8827

Contraintes

• Entrée 4 : $N \leq 200$, et tous les $w_i \leq 200$.
• Entrées 5–6 : Tous les $w_i \leq 200$.
• Entrées 7–10 : $N \leq 5000$.
• Entrées 11–14 : Tous les $w_i$ et $c_i$ sont générés indépendamment et uniformément au hasard.
• Entrées 15–19 : Aucune contrainte supplémentaire.