Đã đến Tết rồi, ai ai cũng muốn nghỉ ngơi. Riêng tôi, trong vai trò là Trợ Lí Giám Đốc của ngài stack_queue_4977 (xem lại bài Giải 2 dấu sigma), tôi lại không muốn các đồng chí cấp dưới của tôi chỉ mải chơi bời, sau đi làm lại không được gì cả. Thế nên, tôi cũng đã nghỉ ra một bài tập nhẹ nhàng cho mấy anh em làm dịp Tết. "Mong các bạn lúc đọc bài này cũng tham gia làm cho vui, với trình độ của các bạn thì chắc phải 1 đấm AC nhé":

"Gọi hai dãy số gồm n số nguyên dương và các con số có thể khác nhau, có thể giống nhau. Mỗi dãy như thế chính là một dãy số biểu hiện kiểu gen giới tính của một người bất kì. Và kiểu gen như thế, sẽ xác định giới tính của một người như sau:

• Nếu như tổng các số trong dãy đó là số chẵn, thì người đó sẽ mang giới tính Nữ (giống như cặp NST đồng điệu \(XX\) của nữ mà SGK hay viết)

• Nếu như tổng các số trong dãy đó là số lẻ, thì người đó sẽ mang giới tính Nam (giống như cặp NST không đồng điệu \(XY\) của nam mà SGK hay viết)

Và nếu như mỗi đôi nam nữ sống cùng nhau thì nguyên tắc cho con cái của họ sẽ như sau: Lấy một đoạn con liên tiếp trong đoạn gen giới tính của bạn nữ, và một đoạn con liên tiếp trong đoạn gen giới tính của bạn nam (độ dài các đoạn ghép này phải \(<n\)), ghép chúng lại với nhau sao cho đoạn gen của con cũng có đủ n phần tử.

Các bạn hãy cho biết, nếu có 2 người ở chung một nhà, thì xác suất bao nhiêu họ sẽ cho ra con gái, xác suất bao nhiêu sẽ cho ra con trai nhé. Kết quả cần làm tròn đến 6 chữ số thập phân".

Input

• Dòng 1 gồm số \(n\).

• Dòng 2 gồm bộ dãy số gen của người 1 "Person 1".

• Dòng 3 gồm bộ dãy số gen của người 2 "Person 2".

Output

• Làm như ở dưới Test 1, giải thích cho cách làm thì ở bên dưới.

Constants

• \(n\leq4000\).

• Các phần tử trong dãy số luôn \(\leq 100000\).

Example

3
12 3 4
9 10 5

Lenght of Gene: 
Person 1: 
Person 2: 
Probability of Boy: 50.000000% 
Probability of Girl: 50.000000%

Lenght of Gene: 3
Person 1: 12 3 4
Person 2: 9 10 5
Probability of Boy: 50.000000%
Probability of Girl: 50.000000%

[12,9,10] -> 31 boy
[12,10,5] -> 27 boy
[3,9,10]  -> 22 girl
[3,10,5]  -> 18 girl
[4,9,10]  -> 23 boy
[4,10,5]  -> 19 boy
[12,3,9]  -> 24 girl
[12,3,10] -> 25 boy
[12,3,5]  -> 20 girl 
[3,4,9]   -> 16 girl
[3,4,10]  -> 17 boy
[3,4,5]   -> 12 girl