gCube (Large)

A $D$-dimensional cube has $D$ dimensions whose lengths are all equal. $D$ may be any positive integer, so a 1-dimensional cube is a line segment, a 2-dimensional cube is a square, and a 4-dimensional cube is a hypercube. A $D$-dimensional cuboid also has $D$ dimensions, but their lengths may differ.

You are given one $N$-dimensional cuboid. Its dimensions are numbered $0, 1, \dots, N-1$ in order, and dimension $i$ has length $a_i$. Solve $M$ subproblems of the following form.

1. Take every dimension from dimension $L_i$ to dimension $R_i$, inclusive.
2. Use those dimensions to form a $D$-dimensional cuboid, where $D = R_i - L_i + 1$. For example, if $L_i = 3$ and $R_i = 6$, you form a 4-dimensional cuboid from dimensions 3, 4, 5, and 6.
3. Reshape it into a $D$-dimensional cube with exactly the same volume, and find the edge length of that cube.

All $M$ subproblems of one test case use the same $N$-dimensional cuboid.

The first line has the number of test cases $T$. Then $T$ test cases follow.

The first line of each test case has the number of dimensions $N$ and the number of queries $M$. The next line has the lengths of the dimensions $a_0, a_1, \dots, a_{N-1}$ in order. Of the $M$ lines that follow, line $i$ has the range $L_i$ and $R_i$ of dimensions that the $i$-th subproblem uses.

For each test case, first print one line of the form Case #x:, where $x$ is the test case number starting at 1. Then print $M$ lines; line $i$ has the edge length of the $i$-th subproblem, written with exactly nine digits after the decimal point. Round at the tenth digit after the decimal point.

The edge length is the $D$-th root of $a_{L_i} \times \cdots \times a_{R_i}$. That value is usually irrational and reaches $10^9$ in size, so double precision floating point alone does not give nine correct digits.

• $1 \le T \le 100$
• $1 \le N \le 1000$
• $1 \le M \le 100$
• $1 \le a_i \le 10^9$
• $0 \le L_i \le R_i < N$