Estás jugando al popular videojuego Escape the BThouse. Como ya habrás adivinado, el objetivo es escapar de la casa.

La casa consta de $n$ habitaciones, dispuestas en una fila y numeradas del 1 al $n$, y $n + 1$ puertas entre las habitaciones. La primera puerta es la salida ubicada en la habitación 1; de manera similar, la puerta $n + 1$ es la salida desde la habitación $n$. Todas las demás puertas $2 \leq i \leq n$ conectan las habitaciones $(i - 1, i)$. Tu objetivo es salir de la casa a través de la primera puerta o de la puerta $n + 1$.

Para abrir la $i$-ésima puerta se requieren al menos $b_i$ puntos de experiencia. La experiencia se puede obtener resolviendo misiones en las habitaciones, donde la misión en la habitación $i$ otorga $a_i$ puntos de experiencia. Formalmente, para resolver una misión es suficiente con simplemente entrar en la habitación. Además, el juego tiene integradas mecánicas de monetización: en cualquier momento, puedes comprar una cantidad arbitraria de experiencia a un precio de 1 unidad de experiencia por 1 moneda del juego.

Debes elegir la habitación inicial; tu personaje aparecerá en esa habitación con 0 unidades de experiencia. Para cada habitación, calcula el número mínimo de monedas necesarias para escapar de la casa, comenzando el juego en esa habitación.

Entrada

La primera línea de entrada contiene un entero $n$ ($1 \leq n \leq 10^6$).

La segunda línea contiene $n$ enteros separados por espacios $a_1, \dots, a_n$ ($0 \leq a_i \leq 10^9$).

La tercera línea contiene $n + 1$ enteros separados por espacios $b_1, \dots, b_{n+1}$ ($0 \leq b_i \leq 10^9$).

Salida

Imprime $n$ enteros separados por espacios $ans_1, \dots, ans_n$, donde $ans_i$ es el número mínimo de monedas necesarias para completar el juego comenzando en la habitación $i$.

Subtareas

Este problema contiene 8 subtareas que cumplen los siguientes requisitos:

1. $n \leq 500$. Vale 12 puntos.
2. $n \leq 5000$. Vale 8 puntos.
3. $n \leq 2 \cdot 10^5$, $a_i = 0$. Vale 10 puntos.
4. $n \leq 2 \cdot 10^5$, $b_1 \leq b_2 \leq \dots \leq b_{n+1}$. Vale 10 puntos.
5. $n \leq 2 \cdot 10^5$, $b_i \leq 100$. Vale 19 puntos.
6. $n \leq 2 \cdot 10^5$. Vale 21 puntos.
7. Restricciones originales del problema. Vale 20 puntos.

Ejemplos

Entrada 1

3
2 1 3
9 8 5 7

Salida 1

6 4 3

Entrada 2

3
1 3 3
10 2 5 6

Salida 2

1 1 2

Nota

Consideremos el primer ejemplo. La estrategia óptima para la primera habitación es la siguiente:

1. Obtener 2 unidades de experiencia en la 1-ra habitación.
2. Comprar 6 unidades de experiencia por 6 monedas.
3. Ir a la 2-da habitación a través de la 2-da puerta.
4. Obtener 1 unidad de experiencia en la 2-da habitación.
5. Ir a la 1-ra habitación a través de la 2-da puerta.
6. Escapar a través de la 1-ra puerta.

Solo se requieren 6 monedas en total.

Para la segunda habitación:

1. Obtener 1 unidad de experiencia en la 2-da habitación.
2. Comprar 4 unidades de experiencia por 4 monedas.
3. Ir a la 3-ra habitación a través de la 3-ra puerta.
4. Obtener 3 unidades de experiencia en la 3-ra habitación.
5. Escapar a través de la 4-ta puerta.

Solo se requieren 4 monedas.

Para la tercera habitación:

1. Obtener 3 unidades de experiencia en la 3-ra habitación.
2. Comprar 2 unidades de experiencia por 2 monedas.
3. Ir a la 2-da habitación a través de la 3-ra puerta.
4. Obtener 1 unidad de experiencia en la 2-da habitación.
5. Ir a la 3-ra habitación a través de la 3-ra puerta.
6. Comprar 1 unidad de experiencia por 1 moneda.
7. Escapar a través de la 4-ta puerta.

Solo se requieren 3 monedas.