#include <stdio.h>
#define lli long long int
using namespace std;

const int MAXN = 200005;
const int MAX_VAL = 105;

int pref[MAXN];
int v[MAXN];

int get_sum(int l, int r) {
    return pref[r] - pref[l - 1];
}

lli solve(lli idx, int n) {
    int low = 0;
    int high = MAXN * MAX_VAL;
    lli ans = 0;

    if (idx <= 0) {
        return 0;
    }

    while(low <= high) {
        int maxi = (low + high) / 2;

        int l = 1;
        int r = 0;
        lli qt = 0;
        lli add = 0; // what we should add for good segments ending in pos r
        lli tot = 0; // total sum such that every sum is < maxi

        while(r <= n) {
            if (r < l) {
                r++;
                add += 1LL * (r - l + 1) * v[r];
            } else if (get_sum(l, r) < maxi) {
                qt += r - l + 1;
                tot += add;
                r++;
                add += 1LL * (r - l + 1) * v[r];
            } else {
                add -= get_sum(l, r);
                l++;
            }
        }

        if (qt >= idx) {
            high = maxi - 1;
        } else {
            ans = tot + (idx - qt) * maxi;
            low = maxi + 1;
        }
    }
    return ans;
}

int main(void) {
    int t;
    int n, q;
    lli l, r;

    scanf(" %d", &t);
    for (int test = 1; test <= t; test++) {
        scanf(" %d %d", &n, &q);
        pref[0] = 0;
        for (int i = 1; i <= n; i++) {
            scanf(" %d", &v[i]);
            pref[i] = v[i] + pref[i - 1];
        }

        printf("Case #%d:\n", test);
        for (int i = 0; i < q; i++) {
            scanf(" %lld %lld", &l, &r);
            lli ans = solve(r, n) - solve(l - 1, n);
            printf("%lld\n", ans);
        }
    }
    return 0;
}