Chul-soo et Young-hee jouent à un jeu sur un plateau comportant $N$ cases disposées en cercle. Un entier non négatif $x_{i}$ est inscrit sur la $i$-ième case. Chaque case peut contenir au plus une pierre.

Chul-soo possède $N$ pierres noires et Young-hee possède $N$ pierres blanches. Au début, les deux joueurs placent des pierres sur certaines cases prédéfinies. Ensuite, ils jouent à tour de rôle, en commençant par Chul-soo. À son tour, un joueur choisit une case vide adjacente à l'une de ses propres pierres et y place une de ses pierres. S'il n'existe aucune case de ce type, le tour passe à l'adversaire. Le jeu se termine lorsque personne ne peut plus placer de pierre.

Chul-soo et Young-hee cherchent chacun à maximiser la somme des valeurs des cases sur lesquelles leurs pierres sont placées. Étant donné la disposition initiale des pierres et en supposant que les deux joueurs jouent de manière optimale, calculez les scores finaux de chacun.

Entrée

La première ligne contient $N$. ($3 \leq N \leq 200\,000$)

La deuxième ligne contient $N$ entiers $c_{1}, \cdots, c_{N}$ séparés par des espaces, représentant la disposition initiale des pierres. ($0 \leq c_{i} \leq 2$) Si $c_{i} = 1$, une pierre noire est placée sur la $i$-ième case ; si $c_{i} = 2$, une pierre blanche est placée sur la $i$-ième case ; si $c_{i} = 0$, aucune pierre n'est placée sur la case.

La troisième ligne contient $N$ entiers $x_1, \cdots, x_{N}$ séparés par des espaces, inscrits sur les cases. ($0 \leq x_i \leq 10^9$)

Sortie

La première ligne affiche les scores obtenus par Chul-soo et Young-hee, séparés par un espace.

Exemples

Entrée 1

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

Sortie 1

12 33

Entrée 2

4
0 0 0 0
6 9 8 8

Sortie 2

0 0

Entrée 3

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

Sortie 3

37 0

Entrée 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

Sortie 4

493 458