|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|5 초||512 MB||11||9||9||81.818%|
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:
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 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.
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.
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