Problem Description

Alice and Bob, who are sufficiently intelligent, are playing a board game. The game requires a long board with $(n+1)$ squares, numbered from left to right as $0, 1, \cdots, n$. Each square, except for the one numbered $n$, has two numbers $p_i$ and $q_i$. At the start of the game, a piece is placed on the $0$th square. The game is played in turns, with Alice going first.

When it's a player's turn, they can decide the number of steps to move based on the current square's $p$ value. Specifically, if the piece is on the $k$th square, the player can move the piece forward by $x$ squares, where $x$ is any integer satisfying $1 \le x \le p_k$. If the player does not move the full $p_k$ squares, i.e., $x < p_k$, they can choose whether to initiate a challenge after moving. If they choose not to challenge, the other player takes the next turn. Otherwise, if the player chooses to challenge, the system will generate two random integers $u$ and $v$: $u$ represents the challenge energy, generated uniformly in the range $\left[1, p_k - x\right]$; $v$ represents the activation energy required for the challenge, generated uniformly in the range $\left[0, q_k + q_{k+x}\right]$. The system will automatically determine the result of the challenge based on the following rules:

• If $u > v$, the challenge is successful, and the opponent's turn is skipped, allowing the current player to continue.
• If $u = v$, the challenge results in a draw, and nothing happens, with the opponent taking the turn.
• If $u < v$, the challenge fails, and the current player's next turn is skipped, allowing the opponent to take two consecutive turns.

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

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

It is important to note that regardless of how many consecutive turns are taken, each turn must move the piece forward by at least one square. As in most games, the player who moves the piece to the final square (numbered $n$) wins.

Alice and Bob are both sufficiently intelligent to calculate the optimal move for their current position. As an observer, you do not have their mental calculation abilities; however, you want to use your programming skills to calculate Alice's win probability when she starts first from the $0$th square.

Input Format

The first line of input contains a positive integer $n$, representing the number of squares on the board, numbered $0, 1, \cdots, n$.

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

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

Output Format

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

Sample Input and Output

Sample Input #1

3
3 3 3
1 2 3

Sample Output #1

1.000000000000000000

Sample Input #2

3
2 3 3
1 2 3

Sample Output #2

0.250000000000000000

Sample Input #3

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

Sample Output #3

0.833333333333333333

Notes

Sample Explanation 1

Alice starts first and can directly move from the $0$th square to the final $3$rd square, ensuring her victory.

Sample Explanation 2

Alice starts first but cannot directly move to the $3$rd square. Regardless of whether she ends her move on the $1$st or $2$nd square, Bob can directly move to the final $3$rd square. Therefore, Alice must attempt a challenge. Moving to the $1$st square and initiating a challenge, the probability of success is $1/4$, hence Alice's win probability is $1/4$.

Data Range

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

见题面 Input 部分

见题面 Output 部分