큐브

구글 직원들은 큐브에 큰 관심이 있지만, 일반적인 삼차원 큐브에는 싫증이 났고 다른 종류의 큐브에 대해서도 생각해 보고 싶어 한다! "D차원 큐브"는 길이가 모두 같은 D개의 차원을 가진다. (D는 임의의 양의 정수일 수 있다. 예를 들어, 1차원 큐브는 선분이고, 2차원 큐브는 정사각형이며, 4차원 큐브는 초입방체이다.) "D차원 직육면체"는 D개의 차원을 가지지만, 그 길이가 모두 같지는 않을 수도 있다.

N차원 직육면체가 있다고 하자. N개의 차원에는 순서대로 (0, 1, 2, ..., N - 1) 번호가 매겨져 있으며, 각 차원은 특정한 길이를 가진다. 다음과 같은 유형의 여러 부분 문제를 해결하고자 한다:

1. L_{i번째 차원부터 R_{i번째 차원까지 양 끝을 포함한 모든 연속된 차원을 취한다.

2. 그 차원들을 사용하여 D = R_{i - L_{i + 1인 D차원 직육면체를 만든다. (예를 들어, L_{i = 3이고 R_{i = 6이면, N차원 직육면체의 3번째, 4번째, 5번째, 6번째 차원을 사용하여 4차원 직육면체를 만든다.)

3. 이 직육면체와 부피가 정확히 같은 D차원 큐브로 변형하고, 그 큐브의 모서리 길이를 구한다.

각 테스트 케이스에는 이와 같은 M개의 부분 문제가 있으며, 모두 동일한 원래의 N차원 직육면체를 사용한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. 1 ≤ $a_{i}$ ≤ $10^{9}$. 0 ≤ $L_{i}$ ≤ $R_{i}$ < N.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ N ≤ 10. 1 ≤ M ≤ 10.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ N ≤ 1000. 1 ≤ M ≤ 100.

입력의 첫 번째 줄에는 테스트 케이스의 수 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} 이내이면 정답으로 인정된다. 이것이 무엇을 의미하는지와 허용되는 실수 형식에 대한 설명은 FAQ을 참조하라.