$N$개의 칸이 원형으로 배치된 게임판을 갖고 철수와 영희가 게임을 하려고 한다. $i$번째 칸에는 음이 아닌 정수 $x_{i}$가 쓰여 있다. 각 칸에는 돌을 최대 하나씩 놓을 수 있다.

철수는 검은 돌을 $N$개 갖고 있고, 영희는 흰 돌을 $N$개 갖고 있다. 먼저 두 사람이 정해진 몇 개의 칸에 돌을 놓는다. 이후 철수부터 시작해서 번갈아 가며 턴을 진행한다. 자신의 턴에는 자신의 돌이 놓인 칸과 인접한 빈칸이 있을 때, 그중 하나를 골라 자신의 돌을 놓는다. 그러한 칸이 없다면 그대로 상대의 턴으로 넘어간다. 아무도 돌을 놓을 수 없는 경우 게임이 종료된다.

철수와 영희는 각자 자신의 돌이 놓인 칸의 점수의 합을 최대화하려고 한다. 턴을 진행하기 전의 돌의 배치가 주어지고 두 사람 모두가 최적의 수를 두었을 때 각자의 점수를 구하여라.

Input

첫 줄에 $N$이 주어진다. ($3 \leq N \leq 200\,000$)

둘째 줄에 $N$개 칸의 돌 배치를 나타내는 정수 $c_{1}$, $\cdots$, $c_{N}$이 공백을 사이에 두고 주어진다. ($0 \leq c_{i} \leq 2$) $c_{i} = 1$이면 $i$번째 칸에 검은 돌이 놓여 있음을, $c_{i} = 2$이면 흰 돌이 놓여 있음을, $c_{i} = 0$이면 어떤 색의 돌도 놓여 있지 않음을 의미한다.

셋째 줄에 $N$개 칸에 적힌 정수 $x_1$, $\cdots$, $x_{N}$이 공백을 사이에 두고 주어진다. ($0 \leq x_i \leq 10^9$)

Output

첫 줄에 철수와 영희가 얻게 되는 각자의 점수를 공백을 사이에 두고 출력한다.

Examples

Input 1

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

Output 1

12 33

Input 2

4
0 0 0 0
6 9 8 8

Output 2

0 0

Input 3

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

Output 3

37 0

Input 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

Output 4

493 458