题目描述

Googler 们对方块非常感兴趣，但他们已经厌倦了普通的三维方块，还想研究其他种类的方块！一个“$D$ 维方块”有 $D$ 个维度，所有维度的长度均相等。（$D$ 可以是任意正整数；例如，$1$ 维方块是一条线段，$2$ 维方块是一个正方形，$4$ 维方块是一个超立方体。）一个“$D$ 维长方体”有 $D$ 个维度，但这些维度的长度不一定全都相等。

假设我们有一个 $N$ 维长方体。这 $N$ 个维度按顺序编号（$0$，$1$，$2$，...，$N - 1$），每个维度都有一定的长度。我们想要解决许多个以下类型的子问题：

1. 选取第 $L_i$ 维到第 $R_i$ 维（包含两端）之间的所有连续维度。
2. 利用这些维度构成一个 $D$ 维长方体，其中 $D = R_i - L_i + 1$。（例如，若 $L_i = 3$ 且 $R_i = 6$，我们将利用原 $N$ 维长方体的第 $3$，$4$，$5$ 和 $6$ 维构成一个 $4$ 维长方体。）
3. 将其重塑为一个体积与该 $D$ 维长方体完全相同的 $D$ 维方块，并求出该方块的边长。

每个测试用例将包含 $M$ 个这样的子问题，所有子问题均使用同一个原始的 $N$ 维长方体。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来是 $T$ 个测试用例。

每个测试用例以两个整数 $N$ 和 $M$ 开始；$N$ 是维度的数量，$M$ 是查询的数量。接下来一行包含 $N$ 个正整数 $a_i$，它们是各维度的长度，按顺序给出。然后，下面有 $M$ 行。在第 $i$ 行中，有两个整数 $L_i$ 和 $R_i$，给出了第 $i$ 个子问题所使用的维度范围。

输出格式

对于每个测试用例，输出一行内容为 Case #x:，其中 $x$ 是测试用例编号（从 $1$ 开始）。此后，输出 $M$ 行，其中第 $i$ 行包含第 $i$ 个子问题的边长。如果边长与正确答案的绝对误差或相对误差在 $10^{-6}$ 以内，则认为该边长正确。

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

提示

限制

$1 \le T \le 100$。

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

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

小数据集（测试集 1 - 可见）

$1 \le N \le 10$。

$1 \le M \le 10$。

大数据集（测试集 2 - 隐藏）

$1 \le N \le 1000$。

$1 \le M \le 100$。

翻译由 DeepSeek V4 Pro 完成