Una universidad tiene un molinete para entrar o salir de un edificio. Determina el instante en que cada persona atravesará el molinete. Cada persona tarda un segundo en atravesarlo.

Cuando varias personas llegan al molinete al mismo tiempo, se aplican las siguientes reglas:

1. Si el molinete no fue utilizado durante el segundo anterior, tienen prioridad las personas que salen.
2. Si la última persona salió, la siguiente persona que sale tiene prioridad.
3. Si la última persona entró, la siguiente persona que entra tiene prioridad.
4. Si dos personas que van en la misma dirección llegan al mismo tiempo, pasa primero la persona con el índice más pequeño.

⸻

Ejemplo 1

Entrada

n = 4

time = [0, 0, 1, 5]

direction = [0, 1, 1, 0]

entrar = 0
salir = 1

Salida

[2, 0, 1, 5]

Explicación

Los números de cada fila representan el tiempo.

0.
Llegan dos estudiantes.
La persona 1 quiere salir y la persona 0 quiere entrar.
Se aplica la Regla 1.
La persona 1 sale.

1.
Llega la persona 2 y quiere salir.
Se aplica la Regla 2.
La persona 2 sale.

2.
La persona 0 entra.

3.
No hay nadie en el molinete.

4.
No hay nadie en el molinete.

5.
La persona 3 entra.

⸻

Ejemplo 2

Entrada

n = 5

time = [0, 1, 1, 3, 3]

direction = [0, 1, 0, 0, 1]

Salida

[0, 2, 1, 4, 3]

Explicación

0.
Llega la persona 0 y entra.

1.
La persona 1 quiere salir y la persona 2 quiere entrar.
Se aplica la Regla 3.
La persona 2 entra.

2.
La persona 1 sale.

3.
La persona 3 quiere entrar y la persona 4 quiere salir.
Se aplica la Regla 2.
La persona 4 sale.

4.
La persona 3 entra.

⸻

Restricciones

1 ≤ n ≤ 100000

0 ≤ time[i] ≤ 10^9

time[i] ≤ time[i + 1]

direction[i] puede ser 0 (entrar) o 1 (salir)