구간 합 질의

정수 $n$개로 이루어진 리스트 $L$이 있다. 두 인덱스 $i$와 $j$에 대한 구간 합 질의 $\mathrm{RSQ}(i, j)$는 인덱스 $i$부터 $j$까지의 원소를 양 끝을 포함해 모두 더한 값이다.

$\mathrm{RSQ}(i, j) = L[i] + L[i+1] + L[i+2] + \dots + L[j]$

인덱스는 0번부터 시작한다.

첫째 줄에 테스트 케이스의 수 $t$가 주어진다 ($1 \le t \le 5$).

각 테스트 케이스 앞에는 빈 줄이 하나 놓이고, 그다음 줄에 두 정수 $n$과 $q$가 주어진다 ($1 \le n, q \le 100{,}000$).

이어지는 줄에 리스트 $L$을 이루는 음이 아닌 정수 $n$개가 주어진다. 각 값은 $1{,}000{,}000{,}000$ 이하다.

그다음 $q$개의 줄에 질의가 한 줄에 하나씩 주어진다. 각 줄에는 두 정수 $i$와 $j$가 주어지며, $0 \le i \le j < n$이고 $j < 10{,}000$이다.

질의마다 $\mathrm{RSQ}(i, j)$의 값을 한 줄에 하나씩 출력한다. 연속한 두 테스트 케이스의 출력 사이에는 빈 줄을 하나 넣는다.