부분배열 합의 합 (큰 입력)

앨리스는 친구 밥에게 양의 정수 $N$개로 이루어진 배열을 주었다. 배열의 인덱스는 $1$번부터 $N$번까지다. 앨리스는 "이 두 인덱스 사이에 있는 수의 합은 얼마인가?" 형태의 질의를 잔뜩 던졌지만, 밥은 너무 쉽게 답했다.

그래서 앨리스는 이 배열에서 비어 있지 않은 부분배열 $N(N+1)/2$개를 모두 찾았다. 각 부분배열의 합을 구한 다음 그 값을 작은 것부터 차례로 정렬해, 인덱스가 $1$번부터 $N(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]$이 나온다.

앨리스는 처음 배열과 함께 "새 배열에서 인덱스 $L_i$번부터 $R_i$번까지, 양 끝을 포함한 수의 합은 얼마인가?" 형태의 질의 $Q$개를 밥에게 주었다. 이번에는 밥이 막혔다. 밥을 도와주자.

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

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

제한

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

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

배열 $[5, 4, 3, 2, 1]$로 만들어지는 새 배열은 $[1, 2, 3, 3, 4, 5, 5, 6, 7, 9, 9, 10, 12, 14, 15]$이다.