Cheolsu y Younghee van a jugar un juego en un tablero con $N$ casillas dispuestas en círculo. En la $i$-ésima casilla hay un número entero no negativo $x_{i}$. Se puede colocar como máximo una piedra en cada casilla.

Cheolsu tiene $N$ piedras negras y Younghee tiene $N$ piedras blancas. Primero, ambos jugadores colocan piedras en algunas casillas predeterminadas. Después, se turnan para jugar, comenzando por Cheolsu. En su turno, si hay una casilla vacía adyacente a una casilla donde ya tiene una piedra, el jugador puede elegir una de esas casillas vacías y colocar su piedra allí. Si no existe tal casilla, el turno pasa al oponente. El juego termina cuando nadie puede colocar más piedras.

Cheolsu y Younghee intentan maximizar la suma de los valores de las casillas donde han colocado sus piedras. Dada la disposición inicial de las piedras antes de comenzar los turnos, calcula las puntuaciones de cada uno asumiendo que ambos juegan de manera óptima.

Entrada

La primera línea contiene $N$. ($3 \leq N \leq 200\,000$)

La segunda línea contiene $N$ enteros $c_{1}, \cdots, c_{N}$ separados por espacios, que representan la disposición inicial de las piedras. ($0 \leq c_{i} \leq 2$) Si $c_{i} = 1$, significa que hay una piedra negra en la $i$-ésima casilla; si $c_{i} = 2$, hay una piedra blanca; si $c_{i} = 0$, la casilla está vacía.

La tercera línea contiene $N$ enteros $x_1, \cdots, x_{N}$ separados por espacios, escritos en cada casilla. ($0 \leq x_i \leq 10^9$)

Salida

La primera línea muestra las puntuaciones obtenidas por Cheolsu y Younghee, respectivamente, separadas por un espacio.

Ejemplos

Entrada 1

9
0 1 0 2 0 0 2 0 0
1 2 3 4 5 6 7 8 9

Salida 1

12 33

Entrada 2

4
0 0 0 0
6 9 8 8

Salida 2

0 0

Entrada 3

8
1 0 0 0 0 0 0 1
2 9 4 8 1 8 5 0

Salida 3

37 0

Entrada 4

36
1 1 0 0 2 2 0 1 0 0 0 0 2 0 0 0 1 0 0 0 1 0 0 2 0 0 0 2 0 0 0 1 0 0 0 1
18 23 18 20 40 30 19 15 13 11 19 21 12 25 43 37 23 21 10 4 9 7 3 60 54 32 18 39 42 55 71 92 4 2 40 1

Salida 4

493 458