#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()

using namespace std;
using ll = long long;

struct Node;

void rsum(Node* v);

struct Node {
    ll sum = 0;
    ll maxsum = 0;
    ll toLeft = 0;
    ll toRight = 0;
    int l = -1, r = -1;
    Node(int l, int r) : l(l), r(r) {
        rsum(this);
    }
    Node(int key = 0) : sum(key), maxsum(key), toLeft(key), toRight(key), l(-1), r(-1) {
    }
};

int ITR = 0;
const int MSIZE = 3 * (1 << 21);
Node BUFFER[MSIZE];

__inline__ void rsum(Node* v) {
    if (v->l == -1 && v->r == -1) {
        v->maxsum = v->sum;
        v->toLeft = v->sum;
        v->toRight = v->sum;
        return;
    }
    if (v->r == -1) {
        v->sum = BUFFER[v->l].sum;
        v->maxsum = BUFFER[v->l].maxsum;
        v->toLeft = BUFFER[v->l].toLeft;
        v->toRight = BUFFER[v->l].toRight;
        return;
    }
    if (v->l == -1) {
        v->sum = BUFFER[v->r].sum;
        v->maxsum = BUFFER[v->r].maxsum;
        v->toLeft = BUFFER[v->r].toLeft;
        v->toRight = BUFFER[v->r].toRight;
        return;
    }
    v->sum = BUFFER[v->l].sum + BUFFER[v->r].sum;
    v->toLeft = max(BUFFER[v->r].sum + BUFFER[v->l].toLeft, BUFFER[v->r].toLeft);
    v->toRight = max(BUFFER[v->l].sum + BUFFER[v->r].toRight, BUFFER[v->l].toRight);
    v->maxsum = max(BUFFER[v->l].maxsum, BUFFER[v->r].maxsum);
    v->maxsum = max(v->maxsum, BUFFER[v->l].toLeft + BUFFER[v->r].toRight);
}

int CreateNode(int val) {
    BUFFER[ITR] = Node(val);
    rsum(&BUFFER[ITR]);
    return ITR++;
}

int CreateNode(int l, int r) {
    BUFFER[ITR].l = l;
    BUFFER[ITR].r = r;
    rsum(&BUFFER[ITR]);
    return ITR++;
}

int Build(int tl, int tr, vector<int>& arr) {
    if (tl + 1 == tr) {
        return CreateNode(arr[tl]);
    } else {
        int tm = (tl + tr) / 2;
        return CreateNode(Build(tl, tm, arr), Build(tm, tr, arr));
    }
}

int Update(int v, int tl, int tr, int i, int value) {
    if (tl + 1 == tr) {
        return CreateNode(value);
    } else {
        int tm = (tl + tr) / 2;
        if (i < tm) {
            return CreateNode(Update(BUFFER[v].l, tl, tm, i, value), BUFFER[v].r);
        } else {
            return CreateNode(BUFFER[v].l, Update(BUFFER[v].r, tm, tr, i, value));
        }
    }
}


int Get(int v, int tl, int tr, int l, int r) {
    if (tl >= r || tr <= l) return -1;
    if (tl >= l && tr <= r) {
        return v;
    } else {
        int cur = ITR++;
        int tm = (tl + tr) / 2;
        BUFFER[cur].l = Get(BUFFER[v].l, tl, tm, l, r);
        BUFFER[cur].r = Get(BUFFER[v].r, tm, tr, l, r);
        rsum(&BUFFER[cur]);
        return cur;
    }
}

ll Get(int root, int l, int r, int n) {
    int ind = Get(root, 0, n, l, r);
    if (ind == -1) return 0;
    return BUFFER[ind].maxsum;
}

map<int, int> vers;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, D;
    cin >> n >> D;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    vers[0] = Build(0, n, arr);
    int m;
    cin >> m;
    while (m--) {
        int d, x, y;
        cin >> d >> x >> y;
        auto it = prev(vers.end())->second;
        it = Update(it, 0, n, x - 1, y);
        vers[d] = it;
    }
    const int DEFITR = ITR;

    int q;
    cin >> q;
    ll z = 0;
    for (int i = 1; i <= q; i++) {
        int d = (z + i) % D + 1;
        int l, r;
        cin >> l >> r;
        l--, r--;
        auto it = prev(vers.upper_bound(d))->second;
        z = max(Get(it, l, r + 1, n), 0LL);
        ITR = DEFITR;
        cout << z << "\n";
    }
}