#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
int n, q, s;
const int maxN = 4e5 + 10;
int a[maxN], b[maxN], l[maxN], r[maxN];
int x[maxN], y[maxN];
vector<pair<int,int>> ask[maxN];
ll fenw[2][maxN];
int N;
void upd(ll *fenw, int v, int by) {
    while (v <= N) {
        fenw[v] += by;
        v = (v | (v - 1)) + 1;
    }
}
ll get(ll *fenw, int r) {
    ll ans = 0;
    while (r > 0) {
        ans += fenw[r];
        r &= (r - 1);
    }
    return ans;
}

int lower_bound(ll* fenw, ll lim) {
    int lg = 21;
    int res = 0;
    for (int k = lg; k >= 0; k--) {
        int p = (res + (1 << k));
        if (p <= N && fenw[p] < lim) {
            lim -= fenw[p];
            res += (1 << k);
        }
    }
    return res + 1;
}
ll ans[maxN];
void solve() {
    cin >> n >> q >> s;
    vector<pair<int,int>> ps;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i] >> l[i] >> r[i];
        l[i] += i;
        r[i] += i;
        ps.emplace_back(b[i] - a[i], i);
        ask[i].clear();
    }
    sort(ps.begin(), ps.end());
    N = ps.size();
    for (int i = 1; i <= N; i++) {
        fenw[0][i] = fenw[1][i] = 0;
    }
    for (int i = 1; i <= q; i++) {
        cin >> x[i] >> y[i];
        ans[i] = -1;
        ask[x[i]].emplace_back(x[i] + y[i], i);
    }
    int L = s;
    int R = s;
    ll add = 0;
    int SZ = 0;
    for (int i = 1; i <= n; i++) {
        add += a[i];
        int t = lower_bound(ps.begin(), ps.end(), make_pair(b[i] - a[i], i)) - ps.begin() + 1;
//        cout << " UPD " << t << endl;
        upd(fenw[0], t, 1);
        upd(fenw[1], t, b[i] - a[i]);
        SZ++;
//        cout << " HI " << i << " " << SZ << endl;
        R += 2;
        while (L < l[i] && L < R) {
            int T = lower_bound(fenw[0], 1);
            upd(fenw[0], T, -1);
            upd(fenw[1], T, -ps[T - 1].first);
            add += ps[T - 1].first;
            L += 2;
            SZ--;
        }
        while (R > r[i] && L < R) {
            int T = lower_bound(fenw[0], SZ);
//            cout << T << " " << ps.size() << " ???? " <<  ;
            upd(fenw[0], T, -1);
            upd(fenw[1], T, -ps[T - 1].first);
            R -= 2;
            SZ--;
        }
        if (L < l[i] || R > r[i]) break;
        for (auto& it : ask[i]) {
//            if (i == 2 && it.first == 3) {
//                cout << " HIHI " << L << " " <
//            }
            if (it.first % 2 != L % 2) continue;
            if (it.first < L || it.first > R) continue;
            int take = (it.first - L) / 2;
            if (take == 0) {
                ans[it.second] = add;
            }
            else {
                int T = lower_bound(fenw[0], take);
                ans[it.second] = get(fenw[1], T) + add;
            }
        }
    }
    for (int i = 1; i <= q; i++) {
        cout << ans[i] << '\n';
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    int tst;
    cin >> tst;
    while (tst--) {
        solve();
    }
    return 0;
}