The "sufficiently intelligent" Alice and Bob are playing a board game. The game uses a strip-shaped board with $(n+1)$ squares, numbered $0, 1, \cdots, n$ from left to right. Except for the square numbered $n$, each square has two values $p_i$ and $q_i$. Before the game starts, a piece is placed on square $0$. The game is played by two players in turns, and we assume Alice goes first.

When it is a player's turn, they can decide how many steps to move forward based on the $p$ value of the current square. Specifically, if the piece is currently at square $k$, the current player can move the piece forward by $x$ squares, where $x$ can be any integer such that $1 \le x \le p_k$. If the player does not move the full $p_k$ squares (i.e., $x < p_k$), the player can choose whether to initiate a challenge after completing the move. If they choose not to challenge, the other player takes the next turn. Otherwise, if the current player chooses to challenge, the system will generate two random integers $u$ and $v$, where: $u$ represents the challenge energy, generated uniformly at random in $[1, p_k-x]$; $v$ represents the activation energy required for the challenge, generated uniformly at random in $[0, q_k + q_{k+x}]$. Based on the values of $u$ and $v$, the system automatically determines the challenge result according to the following rules:

• If $u > v$, the challenge is successful, the opponent's turn is skipped, and the current player continues to operate.
• If $u = v$, the challenge is a draw, nothing happens, and the opponent takes the next turn.
• If $u < v$, the challenge fails, the current player's next turn is skipped, meaning the opponent can take two consecutive turns.

To prevent one player from being skipped indefinitely, the following rules apply:

• If the current player gains an extra turn through their own challenge, that player cannot initiate a second challenge during that extra turn.
• If the current player gains an extra turn because the opponent's challenge failed, that player cannot initiate a challenge at the end of their first turn; they can only choose whether to initiate a challenge at the end of their second turn, and can only take a third turn if the challenge is successful.

Note that regardless of how many consecutive turns are taken, each move must advance the piece by at least $1$ square. As in most games, the player who moves the piece to the finish line (i.e., the square numbered $n$) wins.

Alice and Bob are both sufficiently intelligent and can calculate the move that maximizes their own probability of winning from the current position. As an observer, you do not have their mental calculation ability; however, you want to use your programming skills to calculate Alice's winning probability when she starts from square $0$.

Input

The input is read from standard input.

The first line contains a positive integer $n$, representing that the board contains $(n+1)$ squares, numbered $0, 1, \cdots, n$.

The second line contains $n$ positive integers $p_0, p_1, \cdots, p_{n-1}$, representing the $p$ values of squares $0$ to $n-1$.

The third line contains $n$ positive integers $q_0, q_1, \cdots, q_{n-1}$, representing the $q$ values of squares $0$ to $n-1$.

Output

Output to standard output.

Output a real number representing Alice's winning probability when she starts the game. Your output is considered correct if the absolute error between your output and the standard output does not exceed $10^{-6}$.

Examples

Input 1

3
3 3 3
1 2 3

Output 1

1.000000000000000000

Note 1

Alice goes first. Since she can move directly from square $0$ to the finish line at square $3$, Alice will move the piece directly to square $3$ and is guaranteed to win.

Input 2

3
2 3 3
1 2 3

Output 2

0.250000000000000000

Note 2

Alice goes first, but cannot move directly to square $3$. Regardless of whether the piece is at square $1$ or $2$ after her move, Bob can move it directly to the finish line at square $3$, so Alice must attempt a challenge. Moving the piece to square $1$ and initiating a challenge results in a success probability of $1/4$, so Alice's winning probability is $1/4$.

Input 3

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

Output 3

0.833333333333333333

Subtasks

For $100\%$ of the data, it is guaranteed that $1 \le n \le 100000$ and $1 \le p_i, q_i \le 333$.