$N$個のマスが円状に配置されたゲーム盤を使って、鉄秀（チョルス）と英姫（ヨンヒ）がゲームを行う。$i$番目のマスには非負の整数 $x_{i}$ が書かれている。各マスには石を最大1つまで置くことができる。

鉄秀は黒い石を $N$ 個持っており、英姫は白い石を $N$ 個持っている。まず、2人はあらかじめ決められたいくつかのマスに石を置く。その後、鉄秀から始めて交互にターンを行う。自分のターンには、自分の石が置かれているマスと隣接する空きマスがある場合、その中から1つを選んで自分の石を置く。そのようなマスがない場合は、そのまま相手のターンに移る。誰も石を置くことができない場合、ゲームは終了する。

鉄秀と英姫はそれぞれ、自分の石が置かれたマスの点数の合計を最大化しようとする。ターンを開始する前の石の配置が与えられたとき、両者が最適にプレイした場合のそれぞれの点数を求めよ。

入力

1行目に $N$ が与えられる。 ($3 \leq N \leq 200\,000$)

2行目に $N$ 個のマスの石の配置を表す整数 $c_{1}, \cdots, c_{N}$ が空白区切りで与えられる。 ($0 \leq c_{i} \leq 2$) $c_{i} = 1$ ならば $i$番目のマスに黒い石が置かれていることを、$c_{i} = 2$ ならば白い石が置かれていることを、$c_{i} = 0$ ならばどの色の石も置かれていないことを意味する。

3行目に $N$ 個のマスに書かれた整数 $x_1, \cdots, x_{N}$ が空白区切りで与えられる。 ($0 \leq x_i \leq 10^9$)

出力

1行目に鉄秀と英姫が獲得するそれぞれの点数を空白区切りで出力する。

入出力例

入力 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