У Чхольсу и Ёнхи есть игровое поле с $N$ ячейками, расположенными по кругу. В $i$-й ячейке записано неотрицательное целое число $x_{i}$. В каждой ячейке может находиться не более одного камня.

У Чхольсу есть $N$ черных камней, а у Ёнхи — $N$ белых камней. Сначала игроки расставляют камни на несколько заранее определенных ячеек. Затем они ходят по очереди, начиная с Чхольсу. В свой ход игрок может выбрать любую пустую ячейку, соседнюю с той, где уже лежит его камень, и положить туда свой камень. Если такой ячейки нет, ход переходит к другому игроку. Игра заканчивается, когда никто не может сделать ход.

Чхольсу и Ёнхи стремятся максимизировать сумму чисел в ячейках, занятых их камнями. Определите итоговые очки каждого игрока, если оба играют оптимально, исходя из заданного начального расположения камней.

Входные данные

В первой строке задано число $N$ ($3 \leq N \leq 200\,000$).

Во второй строке через пробел заданы $N$ целых чисел $c_{1}, \dots, c_{N}$, описывающих начальное расположение камней. Если $c_{i} = 1$, в $i$-й ячейке лежит черный камень; если $c_{i} = 2$, в $i$-й ячейке лежит белый камень; если $c_{i} = 0$, ячейка пуста.

В третьей строке через пробел заданы $N$ целых чисел $x_1, \dots, x_{N}$ ($0 \leq x_i \leq 10^9$).

Выходные данные

В первой строке выведите через пробел итоговые очки Чхольсу и Ёнхи соответственно.

Примеры

Входные данные 1

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

Выходные данные 1

12 33

Входные данные 2

4
0 0 0 0
6 9 8 8

Выходные данные 2

0 0

Входные данные 3

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

Выходные данные 3

37 0

Входные данные 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

Выходные данные 4

493 458