gCube (Large)

$D$차원 정육면체는 길이가 모두 같은 $D$개의 차원으로 이루어진다. $D$는 임의의 양의 정수여도 되므로, 1차원 정육면체는 선분이고 2차원 정육면체는 정사각형이며 4차원 정육면체는 초입방체다. $D$차원 직육면체도 차원이 $D$개지만, 각 차원의 길이는 서로 달라도 된다.

$N$차원 직육면체가 하나 주어진다. 차원에는 순서대로 $0, 1, \dots, N-1$의 번호가 붙고, $i$번 차원의 길이는 $a_i$다. 다음 형태의 부분 문제 $M$개를 풀어라.

1. $L_i$번 차원부터 $R_i$번 차원까지 연속한 차원을 모두 고른다.
2. 고른 차원으로 $D = R_i - L_i + 1$차원 직육면체를 만든다. 예를 들어 $L_i = 3$이고 $R_i = 6$이면 3번, 4번, 5번, 6번 차원으로 4차원 직육면체를 만든다.
3. 이 직육면체와 부피가 정확히 같은 $D$차원 정육면체로 다시 만들고, 그 정육면체의 한 변의 길이를 구한다.

한 테스트 케이스에 들어 있는 부분 문제 $M$개는 모두 같은 $N$차원 직육면체를 쓴다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 테스트 케이스가 $T$개 주어진다.

각 테스트 케이스의 첫 줄에는 차원의 수 $N$과 질의의 수 $M$이 주어진다. 다음 줄에는 차원의 길이 $a_0, a_1, \dots, a_{N-1}$이 순서대로 주어진다. 이어지는 $M$개의 줄 중 $i$번째 줄에는 $i$번째 부분 문제가 쓸 차원의 범위 $L_i$와 $R_i$가 주어진다.

각 테스트 케이스마다 먼저 Case #x: 형식으로 한 줄을 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호다. 그다음 $M$개의 줄을 출력하고, 그중 $i$번째 줄에 $i$번째 부분 문제의 한 변의 길이를 소수점 아래 정확히 아홉 자리로 출력한다. 소수점 아래 열째 자리에서 반올림한다.

한 변의 길이는 $a_{L_i} \times \cdots \times a_{R_i}$의 $D$제곱근이다. 이 값은 대개 무리수이고 크기가 $10^9$까지 커지므로, 배정밀도 부동소수점만으로는 아홉 자리를 맞출 수 없다.

• $1 \le T \le 100$
• $1 \le N \le 1000$
• $1 \le M \le 100$
• $1 \le a_i \le 10^9$
• $0 \le L_i \le R_i < N$