시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 3 3 2 100.000%

문제

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 Li-th dimension and Ri-th dimension, inclusive.

2. Use those dimensions to form a D-dimensional cuboid, where D = Ri - Li + 1. (For example, if Li = 3 and Ri = 6, we would form a 4-dimensional cuboid using the 3rd, 4th, 5th, and 6th 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, TT test cases follow.

Each test case begins with two integers N and MN is the number of dimensions and M is the number of queries. Then there is one line with N positive integers ai, which are the lengths of the dimensions, in order. Then, M lines follow. In the ith line, there are two integers Li and Ri, which give the range of dimensions to use for the ith subproblem.

Limits

  • 1 ≤ T ≤ 100.
  • 1 ≤ ai ≤ 109
  • 0 ≤ Li ≤ Ri < N.
  • 1 ≤ N ≤ 10.
  • 1 ≤ M ≤ 10.

출력

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 ith line has the edge length for the ith subproblem. An edge length will be considered correct if it is within an absolute error of 10-6 of the correct answer. See the FAQ for an explanation of what that means, and what formats of real numbers we accept.

예제 입력 1

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

예제 출력 1

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

채점

  • 예제는 채점하지 않는다.