Background

Ryoku inherited Riri’s talent for studying, so she really loves studying. However, no matter how much she loves it, Ryoku can still get tired.

Problem Description

At time $i$, Ryoku will learn that there is a new piece of knowledge $i$. The actual value of this knowledge is $w_i$. Since Ryoku loves studying, she will not choose to skip any knowledge, but she only has probability $p_i$ of successfully mastering this knowledge.

However, if Ryoku masters too much knowledge at the same time, due to factors such as her inner tiredness, Ryoku’s level of “liking” for knowledge will change. We use a value $R$ to describe the magnitude of this liking level. Specifically, let $R=f(l,r)$ represent the total liking level for the knowledge from time $l$ to time $r$ that Ryoku masters continuously. With parameters $a, b$ ($0 < a, b<1$), we have:

$$f(l,r)=a^{b(r-l)} \sum_{i=l}^r w_i$$

Ryoku wants to know the expected total liking level of every continuous segment of time that she can master (note that the continuous segment here must not be contained in a longer one). Can you help her?

Input Format

The input contains three lines.
The first line contains an integer $n$ and two real numbers $a,b$.
The second line contains $n$ integers, which are $w_i$.
The third line contains $n$ real numbers, which are $p_i$.

Output Format

Output one line containing one positive real number, which is the answer.

3 0.5 0.5
2 3 3
0.5 0.5 0.5

3.097

6 0.8 0.2
1 1 4 5 1 4
0.9 0.6 0.7 0.7 0.6 0.8

10.521

Hint

[Sample 1 Explanation]

When mastering knowledge $1$, knowledge $2$, and knowledge $3$, the sum of liking levels over each continuously mastered segment is $\left(\dfrac 12\right)^{\frac12\times 2}(2+3+3)=4$.

When mastering knowledge $1$ and knowledge $2$, the sum of liking levels over each continuously mastered segment is $\left(\dfrac 12\right)^{\frac12\times 1}(2+3)=\dfrac {5\sqrt2}2\approx 3.536$.

When mastering knowledge $1$ and knowledge $3$, the sum of liking levels over each continuously mastered segment is $\left(\dfrac 12\right)^{\frac12\times 0}\times 2 +\left(\dfrac 12\right)^{\frac12\times 0}\times 3 = 5$.

When mastering knowledge $2$ and knowledge $3$, the sum of liking levels over each continuously mastered segment is $\left(\dfrac 12\right)^{\frac12\times 1}(3+3)=3\sqrt 2\approx 4.243$.

When only mastering knowledge $1$, the sum of liking levels over each continuously mastered segment is $\left(\dfrac 12\right)^{\frac12\times 0}\times 2 = 2$.

When only mastering knowledge $2$, the sum of liking levels over each continuously mastered segment is $\left(\dfrac 12\right)^{\frac12\times 0}\times 3 = 3$.

When only mastering “treasure” $3$, the sum of liking levels over each continuously mastered segment is $\left(\dfrac 12\right)^{\frac12\times 0}\times 3 = 3$.

When mastering nothing, the sum of liking levels over each continuously mastered segment is $0$.

The probabilities of the above $8$ cases are all $\dfrac 18$, so the answer is approximately:

$$(4+3.536+5+4.243+2+3+3+0)\times \dfrac 18\approx3.0973$$

---

[Constraints]

For $20\%$ of the testdata, $n \le 18$.
For another $15\%$ of the testdata, $w_i = 1$.
For $55\%$ of the testdata, $n \le 10^3$.
For another $15\%$ of the testdata, $w_i = 1$.
For another $15\%$ of the testdata, $b_i \le 0.2$.

In addition, for $100\%$ of the testdata, $0<n\le10^5$, $0<a,b,p_i<1$, $0<w_i\le10^3$. It is guaranteed that the input precision does not exceed $10^{-2}$.

This problem uses Special Judge. If, for some test point, the difference between your answer and the standard answer is less than or equal to $10^{-3}$, you can pass that test point.

Translated by ChatGPT 5