Description

Ryoku 在第 $i$ 时刻会了解到有一个新知识 $i$，这个新知识的实际价值为 $w_i$，由于 Ryoku 爱学习，所以她不会选择不学习知识，但她只有 $p_i$ 的概率能成功掌握这个知识。

然而如果 Ryoku 同时掌握了太多知识，由于 Ryoku 内心的疲倦等因素，Ryoku 感受到的对知识的喜爱程度会改变，我们用一个数值 $R$ 来描述喜爱程度的大小。具体而言，设 $R=f(l,r)$ 代表 Ryoku 连续掌握时刻 $l$ 至时刻 $r$ 的知识时对这些知识的喜爱程度的总和，有参数 $a, b$（$0 < a, b<1$），则有：

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

Ryoku 想要知道她期望能掌握的每一段连续时刻的知识的喜爱程度之和是多少（需要注意的是，这里所说的连续时刻的知识不能被一段更长的所包含）。你能帮帮她吗？

Input Format

输入包含三行。
第一行包含一个整数 $n$，两个实数 $a,b$。
第二行包含 $n$ 个整数，为 $w_i$。
第三行包含 $n$ 个实数，为 $p_i$。

Output Format

输出包含一行一个正实数，为答案。

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

【样例 1 说明】

掌握知识 $1$、知识 $2$、知识 $3$ 时，每一段连续掌握知识的喜爱程度之和为 $\left(\dfrac 12\right)^{\frac12\times 2}(2+3+3)=4$。

掌握知识 $1$、知识 $2$ 时，每一段连续掌握知识的喜爱程度之和为 $\left(\dfrac 12\right)^{\frac12\times 1}(2+3)=\dfrac {5\sqrt2}2\approx 3.536$。

掌握知识 $1$、知识 $3$ 时，每一段连续掌握知识的喜爱程度之和为 $\left(\dfrac 12\right)^{\frac12\times 0}\times 2 +\left(\dfrac 12\right)^{\frac12\times 0}\times 3 = 5$。

掌握知识 $2$、知识 $3$ 时，每一段连续掌握知识的喜爱程度之和为 $\left(\dfrac 12\right)^{\frac12\times 1}(3+3)=3\sqrt 2\approx 4.243$。

只掌握知识 $1$ 时，每一段连续掌握知识的喜爱程度之和为 $\left(\dfrac 12\right)^{\frac12\times 0}\times 2 = 2$。

只掌握知识 $2$ 时，每一段连续掌握知识的喜爱程度之和为 $\left(\dfrac 12\right)^{\frac12\times 0}\times 3 = 3$。

只掌握宝物 $3$ 时，每一段连续掌握知识的喜爱程度之和为 $\left(\dfrac 12\right)^{\frac12\times 0}\times 3 = 3$。

什么都不掌握时，每一段连续掌握知识的喜爱程度之和为 $0$。

以上 $8$ 种情况出现的概率均为 $\dfrac 18$，所以答案约为：

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

---

【数据规模与约定】

对于 $20\%$ 的数据，$n \le 18$。
对于另外 $15\%$ 的数据，$w_i = 1$。
对于 $55\%$ 的数据，$n \le 10^3$。
对于另外 $15\%$ 的数据，$w_i = 1$。
对于另外 $15\%$ 的数据，$b_i \le 0.2$。

此外，对于 $100\%$ 的数据，$0<n\le10^5$，$0<a,b,p_i<1$，$0<w_i\le10^3$。保证输入数据的精度不超过 $10^{-2}$。

本题使用 Special Judge，如果某个测试点中你的答案与标准答案相差小于等于 $10^{-3}$，你就可以通过该测试点。