Vous jouez au jeu vidéo populaire Escape the BThouse. Comme vous l'aurez sans doute deviné, l'objectif est de s'échapper de la maison.

La maison se compose de $n$ pièces, disposées en rangée et numérotées de $1$ à $n$, avec $n+1$ portes entre les pièces. La $1$-ère porte est la sortie située dans la pièce $1$, et de même, la $(n+1)$-ième porte est la sortie depuis la pièce $n$. Toutes les autres portes $2 \le i \le n$ relient les pièces $(i-1, i)$. Votre but est de sortir de la maison par la première ou la $(n+1)$-ième porte.

Pour ouvrir la $i$-ième porte, au moins $b_i$ points d'expérience sont requis. L'expérience peut être obtenue en résolvant des quêtes dans les pièces, la quête dans la pièce $i$ rapportant $a_i$ points d'expérience. Formellement, pour résoudre une quête, il suffit simplement d'entrer dans la pièce. De plus, le jeu intègre des mécaniques de monétisation : à tout moment, vous pouvez acheter une quantité arbitraire d'expérience au prix de $1$ unité d'expérience pour $1$ pièce de monnaie du jeu.

Vous devez choisir la pièce de départ ; votre personnage apparaîtra dans cette pièce avec $0$ unité d'expérience. Pour chaque pièce, calculez le nombre minimal de pièces de monnaie nécessaires pour s'échapper de la maison en commençant le jeu dans cette pièce.

Entrée

La première ligne de l'entrée contient un entier $n$ ($1 \le n \le 10^6$).

La deuxième ligne contient $n$ entiers séparés par des espaces $a_1, \dots, a_n$ ($0 \le a_i \le 10^9$).

La troisième ligne contient $n+1$ entiers séparés par des espaces $b_1, \dots, b_{n+1}$ ($0 \le b_i \le 10^9$).

Sortie

Affichez $n$ entiers séparés par des espaces $ans_1, \dots, ans_n$, où $ans_i$ est le nombre minimal de pièces de monnaie nécessaires pour terminer le jeu en commençant dans la pièce $i$.

Sous-tâches

Ce problème contient 8 sous-tâches, répondant aux exigences suivantes :

1. $n \le 500$. Vaut 12 points.
2. $n \le 5000$. Vaut 8 points.
3. $n \le 2 \cdot 10^5$, $a_i = 0$. Vaut 10 points.
4. $n \le 2 \cdot 10^5$, $b_1 \le b_2 \le \dots \le b_{n+1}$. Vaut 10 points.
5. $n \le 2 \cdot 10^5$, $b_i \le 100$. Vaut 19 points.
6. $n \le 2 \cdot 10^5$. Vaut 21 points.
7. Contraintes originales du problème. Vaut 20 points.

Exemples

Entrée 1

3
2 1 3
9 8 5 7

Sortie 1

6 4 3

Entrée 2

3
1 3 3
10 2 5 6

Sortie 2

1 1 2

Remarque

Étudions le premier exemple. La stratégie optimale pour la première pièce est la suivante :

1. Obtenir 2 unités d'expérience dans la 1-ère pièce.
2. Acheter 6 unités d'expérience pour 6 pièces.
3. Aller dans la 2-nde pièce par la 2-nde porte.
4. Obtenir 1 unité d'expérience dans la 2-nde pièce.
5. Aller dans la 1-ère pièce par la 2-nde porte.
6. S'échapper par la 1-ère porte.

Seulement 6 pièces sont nécessaires au total.

Pour la deuxième pièce :

1. Obtenir 1 unité d'expérience dans la 2-nde pièce.
2. Acheter 4 unités d'expérience pour 4 pièces.
3. Aller dans la 3-ième pièce par la 3-ième porte.
4. Obtenir 3 unités d'expérience dans la 3-ième pièce.
5. S'échapper par la 4-ième porte.

Seulement 4 pièces sont nécessaires.

Pour la troisième pièce :

1. Obtenir 3 unités d'expérience dans la 3-ième pièce.
2. Acheter 2 unités d'expérience pour 2 pièces.
3. Aller dans la 2-nde pièce par la 3-ième porte.
4. Obtenir 1 unité d'expérience dans la 2-nde pièce.
5. Aller dans la 3-ième pièce par la 3-ième porte.
6. Acheter 1 unité d'expérience pour 1 pièce.
7. S'échapper par la 4-ième porte.

Seulement 3 pièces sont nécessaires.