题目描述

Googlers are very interested in cubes, but they are bored with normal three-dimensional cubes and also want to think about other kinds of cubes! A "$D$-dimensional cube" has $D$ dimensions, all of equal length. ($D$ may be any positive integer; for example, a $1$-dimensional cube is a line segment, and a $2$-dimensional cube is a square, and a $4$-dimensional cube is a hypercube.) A "$D$-dimensional cuboid" has $D$ dimensions, but they might not all have the same lengths.

Suppose we have an $N$-dimensional cuboid. The $N$ dimensions are numbered in order ($0$, $1$, $2$, ..., $N - 1$), and each dimension has a certain length. We want to solve many subproblems of this type:

1. Take all consecutive dimensions between the $L_i$-th dimension and $R_i$-th dimension, 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$, we would form a $4$-dimensional cuboid using the $3$rd, $4$th, $5$th, and $6$th dimensions of our $N$-dimensional cuboid.)
3. Reshape it into a $D$-dimensional cube that has exactly the same volume as that $D$-dimensional cuboid, and find the edge length of that cube.

Each test case will have $M$ subproblems like this, all of which use the same original $N$-dimensional cuboid.

输入格式

The first line of the input gives the number of test cases, $T$. $T$ test cases follow.

Each test case begins with two integers $N$ and $M$; $N$ is the number of dimensions and $M$ is the number of queries. Then there is one line with $N$ positive integers $a_i$, which are the lengths of the dimensions, in order. Then, $M$ lines follow. In the $i$th line, there are two integers $L_i$ and $R_i$, which give the range of dimensions to use for the $i$th subproblem.

输出格式

For each test case, output one line containing "Case #x:", where x is the test case number (starting from 1). After that, output $M$ lines, where the $i$th line has the edge length for the $i$th subproblem. An edge length will be considered correct if it is within an absolute error of $10^{-6}$ of the correct answer.

2
2 2
1 4
0 0
0 1
3 2
1 2 3
0 1
1 2

Case #1:
1.000000000
2.000000000
Case #2:
1.414213562
2.449489743

提示

Limits

$1 \le T \le 100$.

$1 \le a_i \le 10^9$.

$0 \le L_i \le R_i < N$.

Small dataset (Test Set 1 - Visible)

$1 \le N \le 10$.

$1 \le M \le 10$.

Large dataset (Test Set 2 - Hidden)

$1 \le N \le 1000$.

$1 \le M \le 100$.