ns lives a happy and fulfilling life in the garden. One day, $n$ pillars suddenly fall from the sky and line up on the school road. The $i$-th pillar has an original height of $h_i$ meters. However, when someone stands on the $i$-th pillar, its height decreases by $t_i$ meters (i.e., the current height becomes $h_i - t_i$ while someone is standing on it), and it returns to its original height after they leave. ns is very interested in these pillars. He can jump from one pillar to any pillar (including the one he is currently standing on) whose original height is no greater than the current height of the pillar he is currently on. If there are multiple such pillars, he will jump to one of them with equal probability. If no such pillar exists, he will jump to the ground.

ns wants to know, if he starts from the $i$-th pillar, what is the expected number of jumps he will make before reaching the ground.

Input

The first line contains an integer $n$, representing the number of pillars.

The second line contains $n$ space-separated integers $h_i$, representing the original height of each pillar (in meters).

The third line contains $n$ space-separated integers $t_i$, representing the height reduction of each pillar when someone stands on it (in meters).

Output

Output a single line containing $n$ floating-point numbers, separated by spaces. The $i$-th number represents the expected number of jumps ns makes starting from the $i$-th pillar to reach the ground. If the expected number of jumps is infinite, output $0$. Your answer will be considered correct if the absolute difference between each of your floating-point numbers and the standard answer is no more than $0.001$.

Note that we use a special program to judge the correctness of your answer; the string length of each floating-point number you output should not exceed $20$.

Infinity is defined to participate in operations as follows: infinity + X = infinity, infinity - X = infinity, infinity * X = infinity, infinity / X = infinity (where X is any real number, and X is non-zero in division).

Examples

Input 1

4
4 2 2 3
2 1 1 2

Output 1

2.000 1.000 1.000 1.000

Input 2

4
4 2 2 3
0 1 1 0

Output 2

2.833 1.000 1.000 2.500

Input 3

4
4 2 2 3
0 0 0 0

Output 3

0 0 0 0

Constraints

See the input format above. Every input number is an integer. The specific constraints for each test case are as follows: