합들의 합

Alice는 친구 Bob에게 1부터 N까지의 인덱스가 매겨진 N개의 양의 정수로 이루어진 배열을 제시했다. 그녀는 Bob에게 "이 두 인덱스 사이에 있는 수들의 합은 얼마인가?"라는 형태의 많은 질의를 냈다. 하지만 Bob은 문제를 너무 쉽게 풀 수 있었다.

Alice는 자신의 배열에서 비어 있지 않은 모든 N*(N+1)/2개의 부분 배열을 찾았다. 그녀는 각 부분 배열의 합을 구한 다음, 그 값들을 비내림차순으로 정렬하여 1부터 N*(N+1)/2까지의 인덱스가 매겨진 새 배열을 만들었다. 예를 들어, 초기 배열이 $[2, 3, 2]$이면 Alice는 부분 배열 $[2]$, $[3]$, $[2]$, $[2, 3]$, $[3, 2]$, $[2, 3, 2]$을 생성한다($[2, 2]$은 예를 들어 NOT 부분 배열이라는 점에 유의하라). 그런 다음 합들인 2, 3, 2, 5, 5, 7을 구하고 정렬하여 $[2, 2, 3, 5, 5, 7]$이라는 새 배열을 얻는다.

Alice는 Bob에게 초기 배열과 함께 "what is the sum of the numbers from index $L_{i}$ to $R_{i}$, inclusive, in the new array?" 형태의 Q개 질의를 주었다. 이제 Bob은 곤경에 처했다! 그를 도울 수 있는가?

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1 GB. 1 ≤ T ≤ 10. 1 ≤ Q ≤ 20. 1 ≤ 초기 배열의 각 원소 ≤ 100. 1 ≤ $L_{i}$ ≤ $R_{i}$ ≤ N*(N+1)/2.

소규모 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ N ≤ $10^{3}$.

대규모 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ N ≤ 200000.

입력의 첫째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 공백으로 구분된 두 정수 N과 Q가 있는 한 줄로 시작하며, 각각 초기 배열의 원소 수와 Alice의 질의 수를 나타낸다. 다음 한 줄에는 공백으로 구분된 N개의 정수가 주어지며, Alice의 초기 배열 원소를 나타낸다. 마지막으로 공백으로 구분된 두 정수가 각각 주어지는 Q개의 줄이 더 주어진다. 이 정수는 i번째 질의에서 양 끝을 포함하는 인덱스 경계 $L_{i}$와 $R_{i}$이다.

각 테스트 케이스마다 Case #x:가 있는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이다. 이어서 Q개의 줄을 더 출력하며, 각 줄에는 질의의 답을 질의가 주어진 순서대로 나타내는 하나의 정수를 출력한다.

예제 케이스 #1에서 Alice의 새 배열은 다음과 같다: $[1, 2, 3, 3, 4, 5, 5, 6, 7, 9, 9, 10, 12, 14, 15]$.