AT_past19_n 有限べき級数

You are given a length- $ N $ sequence $ A=(A _ 1,A _ 2,\ldots,A _ N) $ of non-negative integers, and a real value $ x $ strictly greater than $ 0 $ and less than or equal to $ 1 $ . For an integer pair $ (l,r)\ (1\leq l\leq r\leq N) $ , we define $ f(l,r) $ as follows: $ \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} $ Answer $ Q $ queries. In the $ i $ -th query $ (1\leq i\leq Q) $ , given an integer pair $ (l _ i,r _ i)\ (1\leq l _ i\leq r _ i\leq N) $ , find $ f(l _ i,r _ i) $ .

The input is given from Standard Input in the following format: > $ N $ $ A _ 1 $ $ A _ 2 $ $ \ldots $ $ A _ N $ $ x $ $ Q $ $ l _ 1 $ $ r _ 1 $ $ l _ 2 $ $ r _ 2 $ $ \vdots $ $ l _ Q $ $ r _ Q $

Print $ Q $ lines. The $ i $ -th line $ (1\leq i\leq Q) $ should contain the value $ f(l _ i,r _ i) $ for the $ i $ -th query $ (l _ i,r _ i) $ . Your answer is considered correct if the relative or absolute error from the true value is at most $ 10 ^ {-6} $ .

### Sample Explanation 1 For each query, the answer is as follows. - $ 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 $ . Since your answer is considered correct if the relative or absolute error is at most $ 10 ^ {-6} $ , output like ``` 3.5 4.703125 3.54443359375 0.999999 ``` and ``` 3.4999965 4.703129703125 3.54443004931640625 1.000001 ``` are also accepted. ### 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 $ , and $ r _ i $ are integers. - $ x $ is a real value with at most $ 15 $ decimal places.