Gracze A i B rozgrywają grę na planszy składającej się z $N$ pól ułożonych w okrąg. Na $i$-tym polu zapisana jest nieujemna liczba całkowita $x_{i}$. Na każdym polu można umieścić co najwyżej jeden kamień.
Gracz A posiada $N$ czarnych kamieni, a gracz B posiada $N$ białych kamieni. Na początku gry na planszy znajduje się pewna liczba kamieni w określonych polach. Następnie gracze wykonują ruchy na zmianę, zaczynając od gracza A. W swojej turze gracz może wybrać puste pole sąsiadujące z polem, na którym znajduje się już jego kamień, i umieścić na nim swój kamień. Jeśli gracz nie ma możliwości wykonania ruchu, tura przechodzi na przeciwnika. Gra kończy się, gdy żaden z graczy nie może wykonać ruchu.
Gracze A i B dążą do zmaksymalizowania sumy wartości pól, na których znajdują się ich kamienie. Mając dane początkowe rozmieszczenie kamieni, oblicz końcowe wyniki obu graczy, zakładając, że obaj grają optymalnie.
Wejście
W pierwszym wierszu podano liczbę $N$ ($3 \leq N \leq 200\,000$).
W drugim wierszu podano $N$ liczb całkowitych $c_{1}, \cdots, c_{N}$ oddzielonych spacjami, reprezentujących początkowe rozmieszczenie kamieni ($0 \leq c_{i} \leq 2$). Jeśli $c_{i} = 1$, na $i$-tym polu znajduje się czarny kamień; jeśli $c_{i} = 2$, znajduje się tam biały kamień; jeśli $c_{i} = 0$, pole jest puste.
W trzecim wierszu podano $N$ liczb całkowitych $x_1, \cdots, x_{N}$ oddzielonych spacjami, gdzie $x_i$ to wartość przypisana do $i$-tego pola ($0 \leq x_i \leq 10^9$).
Wyjście
W pierwszym wierszu należy wypisać dwie liczby całkowite oddzielone spacją, reprezentujące odpowiednio końcowy wynik gracza A (czarne kamienie) oraz gracza B (białe kamienie).
Przykład
Wejście 1
9 0 1 0 2 0 0 2 0 0 1 2 3 4 5 6 7 8 9
Wyjście 1
12 33
Wejście 2
4 0 0 0 0 6 9 8 8
Wyjście 2
0 0
Wejście 3
8 1 0 0 0 0 0 0 1 2 9 4 8 1 8 5 0
Wyjście 3
37 0
Wejście 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
Wyjście 4
493 458