N - Finite Power Series Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

長さ 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) の値を求めてください。

制約

  • 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 桁の実数として与えられる

入力

入力は以下の形式で標準入力から与えられる。

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} 以下であれば正解と判定される。

入力例 1

7
3 1 4 1 5 9 2
0.25
4
1 3
3 6
1 7
2 2

出力例 1

3.5
4.703125
3.54443359375
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

のように出力しても正解になります。

入力例 2

15
6 45 81 83 28 40 31 30 51 31 59 50 94 36 0
0.998244353
20
1 2
1 5
1 10
2 5
2 10
3 3
3 8
3 12
4 4
4 14
5 5
5 11
5 13
5 14
6 7
7 7
8 10
10 13
10 14
12 14

出力例 2

50.920995885
242.004326432639783195178618854259
422.764240065920208662445303267128
236.419395434977014285377699356
417.497217803865912440022892137641
81
292.066191815728552247199317241863
480.544234637661958884554506013369
83
528.144974561396676686531955107577
28
268.416129630805326045766513470066
410.492717775411750526215653552396
445.927866482402907904585917660160
70.945574943
31
111.801707440188046879
233.226782486727123857410847838
268.974634315843968519190799533618
179.708673560669989924

Problem Statement

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).

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.

Input

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

Output

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 Input 1

7
3 1 4 1 5 9 2
0.25
4
1 3
3 6
1 7
2 2

Sample Output 1

3.5
4.703125
3.54443359375
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.

Sample Input 2

15
6 45 81 83 28 40 31 30 51 31 59 50 94 36 0
0.998244353
20
1 2
1 5
1 10
2 5
2 10
3 3
3 8
3 12
4 4
4 14
5 5
5 11
5 13
5 14
6 7
7 7
8 10
10 13
10 14
12 14

Sample Output 2

50.920995885
242.004326432639783195178618854259
422.764240065920208662445303267128
236.419395434977014285377699356
417.497217803865912440022892137641
81
292.066191815728552247199317241863
480.544234637661958884554506013369
83
528.144974561396676686531955107577
28
268.416129630805326045766513470066
410.492717775411750526215653552396
445.927866482402907904585917660160
70.945574943
31
111.801707440188046879
233.226782486727123857410847838
268.974634315843968519190799533618
179.708673560669989924