AT_past19_n 有限べき級数

長さ $ N $ の非負整数列 $ A=(A _ 1,A _ 2,\ldots,A _ N) $ と $ 0 $ より大きく $ 1 $ 以下の実数 $ x $ が与えられます。 整数の組 $ (l,r)\ (1\leq l\leq r\leq N) $ に対して、 $ f(l,r) $ を以下のように定めます。 $ \begin{aligned}f(l,r)&=A _ l+A _ {l+1}x+A _ {l+2}x ^ 2+\cdots+A _ {r}x ^ {r-l}\\&=\sum _ {i=0} ^ {r - l}A _ {i+l}x ^ i\end{aligned} $ $ Q $ 個の質問に答えてください。 $ i $ 個目の質問 $ (1\leq i\leq Q) $ では整数の組 $ (l _ i,r _ i)\ (1\leq l _ i\leq r _ i\leq N) $ が与えられるので、 $ f(l _ i,r _ i) $ の値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A _ 1 $ $ A _ 2 $ $ \ldots $ $ A _ N $ $ x $ $ Q $ $ l _ 1 $ $ r _ 1 $ $ l _ 2 $ $ r _ 2 $ $ \vdots $ $ l _ Q $ $ r _ Q $

$ Q $ 行出力せよ。 $ i $ 行目 $ (1\leq i\leq Q) $ には $ i $ 個目の質問 $ (l _ i,r _ i) $ に対する $ f(l _ i,r _ i) $ の値を出力せよ。 真の値との相対誤差もしくは絶対誤差が $ 10 ^ {-6} $ 以下であれば正解と判定される。

### Sample Explanation 1 各質問について、答えはそれぞれ以下のようになります。 - $ f(1,3)=A _ 1\times0.25 ^ 0+A _ 2\times0.25 ^ 1+A _ 3\times0.25 ^ 2=3+0.25+0.25=3.5 $ です。 - $ f(3,6)=A _ 3\times0.25 ^ 0+A _ 4\times0.25 ^ 1+A _ 5\times0.25 ^ 2+A _ 6\times0.25 ^ 3=4+0.25+0.3125+0.140625=4.703125 $ です。 - $ f(1,7)=A _ 1\times0.25 ^ 0+A _ 2\times0.25 ^ 1+A _ 3\times0.25 ^ 2+A _ 4\times0.25 ^ 3+A _ 5\times0.25 ^ 4+A _ 6\times0.25 ^ 5+A _ 7\times0.25 ^ 6=3+0.25+0.25+0.015625+0.01953125+0.0087890625+0.00048828125=3.54443359375 $ です。 - $ f(2,2)=A _ 2\times0.25 ^ 0=1 $ です。 相対誤差もしくは絶対誤差が $ 10 ^ {-6} $ 以下であれば正解になるので、 ``` 3.5 4.703125 3.54443359375 0.999999 ``` や ``` 3.4999965 4.703129703125 3.54443004931640625 1.000001 ``` のように出力しても正解になります。 ### Constraints - $ 1\leq N\leq2\times10 ^ 5 $ - $ 0\leq A _ i\leq10 ^ 9\ (1\leq i\leq N) $ - $ 0\lt x\leq 1 $ - $ 1\leq Q\leq2\times10 ^ 5 $ - $ 1\leq l _ i\leq r _ i\leq N\ (1\leq i\leq Q) $ - $ N,A _ i,Q,l _ i,r _ i $ は整数 - $ x $ は小数点以下たかだか $ 15 $ 桁の実数として与えられる