Grasz w popularną grę wideo Escape the BThouse. Jak można się domyślić, celem jest ucieczka z domu.

Dom składa się z $n$ pokoi ustawionych w rzędzie i ponumerowanych od $1$ do $n$, oraz $n+1$ drzwi pomiędzy nimi. Pierwsze drzwi to wyjście znajdujące się w pokoju $1$, podobnie $n+1$-sze drzwi to wyjście z pokoju $n$. Wszystkie pozostałe drzwi $2 \le i \le n$ łączą pokoje $(i-1, i)$. Twoim celem jest ucieczka z domu przez pierwsze lub $n+1$-sze drzwi.

Aby otworzyć $i$-te drzwi, wymagane jest posiadanie co najmniej $b_i$ punktów doświadczenia. Doświadczenie można zdobyć poprzez rozwiązywanie zadań w pokojach, przy czym zadanie w pokoju $i$ daje $a_i$ punktów doświadczenia. Formalnie, aby rozwiązać zadanie, wystarczy wejść do pokoju. Gra posiada również wbudowaną mechanikę monetyzacji: w dowolnym momencie możesz dokupić dowolną ilość doświadczenia w cenie $1$ jednostka doświadczenia za $1$ monetę.

Musisz wybrać pokój startowy; twoja postać pojawi się w nim z $0$ jednostkami doświadczenia. Dla każdego pokoju oblicz minimalną liczbę monet potrzebną do ucieczki z domu, rozpoczynając grę w tym pokoju.

Wejście

Pierwsza linia wejścia zawiera jedną liczbę całkowitą $n$ ($1 \le n \le 10^6$).

Druga linia zawiera $n$ liczb całkowitych oddzielonych spacjami $a_1, \dots, a_n$ ($0 \le a_i \le 10^9$).

Trzecia linia zawiera $n+1$ liczb całkowitych oddzielonych spacjami $b_1, \dots, b_{n+1}$ ($0 \le b_i \le 10^9$).

Wyjście

Wypisz $n$ liczb całkowitych oddzielonych spacjami $ans_1, \dots, ans_n$, gdzie $ans_i$ to minimalna liczba monet niezbędna do ukończenia gry, zaczynając w pokoju $i$.

Podzadania

Problem zawiera 8 podzadań, które spełniają następujące wymagania:

1. $n \le 500$. Wartość: 12 punktów.
2. $n \le 5000$. Wartość: 8 punktów.
3. $n \le 2 \cdot 10^5$, $a_i = 0$. Wartość: 10 punktów.
4. $n \le 2 \cdot 10^5$, $b_1 \le b_2 \le \dots \le b_{n+1}$. Wartość: 10 punktów.
5. $n \le 2 \cdot 10^5$, $b_i \le 100$. Wartość: 19 punktów.
6. $n \le 2 \cdot 10^5$. Wartość: 21 punktów.
7. Oryginalne ograniczenia problemu. Wartość: 20 punktów.

Przykład

Wejście 1

3
2 1 3
9 8 5 7

Wyjście 1

6 4 3

Wejście 2

3
1 3 3
10 2 5 6

Wyjście 2

1 1 2

Uwagi

Rozważmy pierwszy przykład. Optymalna strategia dla pierwszego pokoju jest następująca:

1. Zdobądź 2 jednostki doświadczenia w 1. pokoju.
2. Kup 6 jednostek doświadczenia za 6 monet.
3. Przejdź do 2. pokoju przez 2. drzwi.
4. Zdobądź 1 jednostkę doświadczenia w 2. pokoju.
5. Przejdź do 1. pokoju przez 2. drzwi.
6. Ucieknij przez 1. drzwi.

W sumie potrzeba tylko 6 monet.

Dla drugiego pokoju:

1. Zdobądź 1 jednostkę doświadczenia w 2. pokoju.
2. Kup 4 jednostki doświadczenia za 4 monety.
3. Przejdź do 3. pokoju przez 3. drzwi.
4. Zdobądź 3 jednostki doświadczenia w 3. pokoju.
5. Ucieknij przez 4. drzwi.

Potrzeba tylko 4 monet.

Dla trzeciego pokoju:

1. Zdobądź 3 jednostki doświadczenia w 3. pokoju.
2. Kup 2 jednostki doświadczenia za 2 monety.
3. Przejdź do 2. pokoju przez 3. drzwi.
4. Zdobądź 1 jednostkę doświadczenia w 2. pokoju.
5. Przejdź do 3. pokoju przez 3. drzwi.
6. Kup 1 jednostkę doświadczenia za 1 monetę.
7. Ucieknij przez 4. drzwi.

Potrzeba tylko 3 monet.