부분합의 합 (작은 문제)

앨리스가 친구 밥에게 1번부터 $N$번까지 번호가 붙은 양의 정수 $N$개짜리 배열을 주었다. 그리고 "두 인덱스 사이에 있는 수를 모두 더하면 얼마인가"를 묻는 질의를 잔뜩 던졌다. 밥은 이 질의를 너무 쉽게 풀어냈다.

그래서 앨리스는 이 배열에서 비어 있지 않은 연속 부분 배열 $N \times (N + 1) / 2$개를 모두 찾았다. 각 부분 배열의 합을 구한 다음 그 값을 오름차순으로 정렬해 1번부터 $N \times (N + 1) / 2$번까지 번호가 붙은 새 배열을 만들었다. 예를 들어 처음 배열이 [2, 3, 2]라면 부분 배열은 [2], [3], [2], [2, 3], [3, 2], [2, 3, 2]이다. [2, 2]는 연속하지 않으므로 부분 배열이 아니다. 합은 차례로 2, 3, 2, 5, 5, 7이고, 이를 정렬하면 새 배열 [2, 2, 3, 5, 5, 7]이 된다.

앨리스는 밥에게 처음 배열과 함께 질의 $Q$개를 주었다. $i$번째 질의는 "새 배열에서 $L_i$번부터 $R_i$번까지의 수를 모두 더하면 얼마인가"를 묻는다. 밥을 도와 각 질의의 답을 구하라.

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

각 테스트 케이스의 첫째 줄에는 처음 배열의 길이 $N$과 질의의 개수 $Q$가 공백을 사이에 두고 주어진다. 둘째 줄에는 처음 배열의 원소 $N$개가 공백을 사이에 두고 주어진다. 이어지는 $Q$개의 줄에는 $i$번째 질의의 인덱스 $L_i$와 $R_i$가 공백을 사이에 두고 주어진다. 양 끝 인덱스를 모두 포함한다.

제한

• $1 \le T \le 10$
• $1 \le N \le 1000$
• $1 \le Q \le 20$
• 처음 배열의 각 원소는 1 이상 100 이하이다.
• $1 \le L_i \le R_i \le N \times (N + 1) / 2$

각 테스트 케이스마다 먼저 Case #x:를 한 줄에 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이다. 이어서 $Q$개의 줄에 질의의 답을 질문받은 순서대로 한 줄에 하나씩 출력한다.

첫 번째 예제에서 앨리스가 만든 새 배열은 [1, 2, 3, 3, 4, 5, 5, 6, 7, 9, 9, 10, 12, 14, 15]이다.