鐵秀和英熙打算在一個圓形排列的 $N$ 個格子的遊戲盤上進行遊戲。第 $i$ 個格子寫有一個非負整數 $x_{i}$。每個格子最多只能放置一顆棋子。

鐵秀有 $N$ 顆黑子，英熙有 $N$ 顆白子。首先，兩人在預先指定的幾個格子中放置棋子。之後，由鐵秀開始，兩人輪流進行回合。在自己的回合中，若存在與自己已放置棋子的格子相鄰的空格，則從中選擇一個放置自己的棋子。若沒有這樣的格子，則直接輪到對手回合。當沒有人能放置棋子時，遊戲結束。

鐵秀和英熙各自的目標是最大化自己棋子所在格子的分數總和。給定回合開始前的棋子配置，假設兩人皆採取最佳策略，請計算出各自的得分。

輸入格式

第一行給定 $N$。($3 \leq N \leq 200\,000$)

第二行給定 $N$ 個整數 $c_{1}, \cdots, c_{N}$，表示 $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$)

輸出格式

第一行輸出鐵秀和英熙各自獲得的總分，以空格分隔。

範例

輸入格式 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