// Problem: P5609 [Ynoi2013] 对数据结构的爱
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5609
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;

template<class T>
bool chmax(T &a, const T &b){
	if(a < b){ a = b; return true; }
	return false;
}

template<class T>
bool chmin(T &a, const T &b){
	if(a > b){ a = b; return true; }
	return false;
}

template<class T>
inline T read() {
    T x = 0, f = 1;
    char ch = getchar_unlocked();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar_unlocked();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x <<  1) + (ch ^ 48);
        ch = getchar_unlocked();
    }
    return x * f;
}

template<class T>
inline void write(T x) {
    if (x < 0) {
        putchar_unlocked('-');
        x = -x;
    }
    if (x > 9) write(x / 10);
    putchar_unlocked(x % 10 + '0');
    return;
}

const i64 inf = 2e18;
i64 Max(const i64 a, const i64 b) { return (a > b ? a : b); }
i64 Min(const i64 a, const i64 b) { return (a < b ? a : b); }

struct Node {
    int l, r;
    i64 sum;
    vector<i64> c;
};
using Tree = vector<Node>;
inline int ls(const int u) { return 2 * u + 1; }
inline int rs(const int u) { return 2 * u + 2; }

inline void pushup(Tree& tr, const int u, const int p) {
    tr[u].sum = tr[ls(u)].sum + tr[rs(u)].sum;

    const int lenl = tr[ls(u)].r - tr[ls(u)].l + 1;
    const int lenr = tr[rs(u)].r - tr[rs(u)].l + 1;
    const auto &lc = tr[ls(u)].c, &rc = tr[rs(u)].c;
    const auto sum = tr[ls(u)].sum;
    auto &c = tr[u].c;
    
    for (int x = 0, y = 0; x <= lenl; x = -~x) {
        const i64 tmp = 1LL * x * p;
        if (y > lenr) y = ~-y;
        for (; y <= lenr; y = -~y) {
            const i64 nd = lc[x + 1] - 1 - tmp + sum;
            if (rc[y] > nd) {
                --y;
                break;
            }
            c[x + y] = Min(c[x + y], Max(lc[x], rc[y] + tmp - sum));
        }
    }
}

inline void build(Tree& tr, const int u, const int l, const int r, 
           const vector<i64>& a, const int p) {
    
    const int siz = r - l + 3;
    tr[u].l = l;
    tr[u].r = r;
    tr[u].c.resize(siz);
    tr[u].c[0] = -inf;
    for (int i = 1; i < siz; i = -~i) tr[u].c[i] = inf;
    
    if (l == r) {
        tr[u].sum = a[l];
        tr[u].c[1] = p - a[l];
        return;
    }
    
    const int mid = (l + r) >> 1;
    build(tr, ls(u), l, mid, a, p);
    build(tr, rs(u), mid + 1, r, a, p);
    pushup(tr, u, p);
}

inline i64 query(Tree& tr, const int u, const int l, const int r, 
          const i64 x, const int p) {
    
	if (l <= tr[u].l && tr[u].r <= r) {
	    const auto& c = tr[u].c;
		i64 pos = upper_bound(c.begin(), c.end(), x) - c.begin() - 1;
		return x + tr[u].sum - p * pos;
	}
	
	int mid = (tr[u].l + tr[u].r) >> 1;
	if (r <= mid) return query(tr, ls(u), l, r, x, p);
	if (l > mid) return query(tr, rs(u), l, r, x, p);
	return query(tr, rs(u), l, r, query(tr, ls(u), l, r, x, p), p);
} 

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	const int n = read<int>(), m = read<int>(), p = read<int>();
	
	vector<i64> a(n);
	for (int i = 0; i < n; i = -~i) a[i] = read<i64>();
	
	Tree tr(n << 2);
	build(tr, 0, 0, ~-n, a, p);
	
	i64 lst = 0;
	for (int i = 0, l, r, x; i < m; i = -~i) {
	    l = read<int>();
	    r = read<int>();
	    x = read<int>();
	    
	    l ^= lst, r ^= lst, x ^= lst;
	    l = ~-l, r = ~-r;
	    
	    write(lst = query(tr, 0, l, r, x, p));
	    putchar('\n');
	    lst = (lst % n + n) % n;
	}
	
	return 0;
}

T的点的时间 $\in [1, 1.15]s$

试过 fread，五彩斑斓一片