Chul-soo và Young-hee chơi một trò chơi trên một bàn cờ có $N$ ô được sắp xếp theo hình tròn. Trên ô thứ $i$ có ghi một số nguyên không âm $x_i$. Mỗi ô chỉ có thể chứa tối đa một viên đá.

Chul-soo có $N$ viên đá đen và Young-hee có $N$ viên đá trắng. Ban đầu, một số viên đá đã được đặt sẵn trên bàn cờ. Sau đó, hai người chơi lần lượt thực hiện các lượt đi, bắt đầu từ Chul-soo. Trong lượt của mình, nếu có một ô trống nằm cạnh một ô đã có đá của mình, người chơi có thể chọn một trong các ô trống đó để đặt viên đá của mình vào. Nếu không có ô trống nào như vậy, lượt chơi sẽ chuyển sang cho đối thủ. Trò chơi kết thúc khi không ai có thể đặt thêm đá.

Chul-soo và Young-hee đều muốn tối đa hóa tổng giá trị các số ghi trên những ô có đá của mình. Cho biết trạng thái ban đầu của các viên đá, hãy tính điểm số của mỗi người khi cả hai đều chơi một cách tối ưu.

Dữ liệu vào

Dòng đầu tiên chứa $N$ ($3 \leq N \leq 200\,000$).

Dòng thứ hai chứa $N$ số nguyên $c_1, \dots, c_N$ cách nhau bởi dấu cách, biểu thị trạng thái ban đầu của các ô. ($0 \leq c_i \leq 2$). Nếu $c_i = 1$, ô thứ $i$ có đá đen; nếu $c_i = 2$, ô thứ $i$ có đá trắng; nếu $c_i = 0$, ô thứ $i$ trống.

Dòng thứ ba chứa $N$ số nguyên $x_1, \dots, x_N$ cách nhau bởi dấu cách, biểu thị giá trị ghi trên các ô. ($0 \leq x_i \leq 10^9$).

Dữ liệu ra

In ra điểm số của Chul-soo và Young-hee trên một dòng, cách nhau bởi dấu cách.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

12 33

Dữ liệu vào 2

4
0 0 0 0
6 9 8 8

Dữ liệu ra 2

0 0

Dữ liệu vào 3

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

Dữ liệu ra 3

37 0

Dữ liệu vào 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

Dữ liệu ra 4

493 458