gCube (Small)

A $D$-dimensional cube has $D$ dimensions of equal length. $D$ is 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 an $N$-dimensional cuboid. Its dimensions are numbered $0, 1, 2, \ldots, N-1$ in order, and dimension $i$ has length $a_i$. Answer $M$ queries of the following form.

1. Take the consecutive dimensions from the $L_i$-th one to the $R_i$-th one, inclusive.
2. Build a $D$-dimensional cuboid from those dimensions, where $D = R_i - L_i + 1$. For example, if $L_i = 3$ and $R_i = 6$, the new cuboid uses dimensions 3, 4, 5, and 6.
3. Reshape that cuboid into a $D$-dimensional cube with exactly the same volume, and report the edge length of the cube.

Every query of a test case uses the same original $N$-dimensional cuboid.

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

Each test case begins with a line holding two integers $N$ and $M$, the number of dimensions and the number of queries. The next line has $N$ positive integers $a_0, a_1, \ldots, a_{N-1}$, the lengths of the dimensions in order. Each of the next $M$ lines has two integers $L_i$ and $R_i$, the range of dimensions used by the $i$-th query.

For each test case, print one line "Case #x:", where x is the number of the test case starting from 1. Then print $M$ lines, where the $i$-th line has the edge length for the $i$-th query.

The edge length for a query is $\left(\prod_{j=L_i}^{R_i} a_j\right)^{1/D}$ with $D = R_i - L_i + 1$. Print it with exactly 9 digits after the decimal point, rounding the exact value half up at the ninth decimal place. The root is usually irrational and the product reaches $10^{90}$, so compute it precisely enough that the ninth decimal digit is correct. Always print at least one digit before the decimal point and never print a plus sign.

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