#include <bits/stdc++.h>using namespace std;#define int long longconst int N = 1e6+100;int t, n, a[N], q, sum[N], cnt;int ask(int l, int r) {	int tarL = (l + n - 1) / n, tarR = (r + n - 1) / n, res = 0, ll = l % n, rr = r % n;
	res += (tarR - tarL - 1) * cnt;	if (ll == 0)
		ll = n;	if (rr == 0)
		rr = n;
	res += sum[tarL + n - 1] - sum[tarL + ll - 2];
	res += sum[tarR + rr - 1] - sum[tarR - 1];	return res;
}void solve() {	cin >> n >> q;
	cnt = 0;	for (int i = 1; i <= n; i++) {		cin >> a[i];
		a[i + n] = a[i], cnt += a[i];
	}	for (int i = 1; i <= 2 * n; i++)
		sum[i] = sum[i - 1] + a[i];	while (q--) {		int l, r;		cin >> l >> r;		cout << ask(l, r) << "\n";
	}
}signed main() {
	ios::sync_with_stdio(false);	cin.tie(0), cout.tie(0);	cin >> t;	while (t--)
		solve();	return 0;
}