On The Way To Shopping

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

#define int long long
#define ii pair<int, int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const int MAX = 800100;
const int LOG_MAX = 20;

int n; // the queries will be performed in the range [0, n - 1]
int L[LOG_MAX * MAX]; // L[node] is the left child of node
int R[LOG_MAX * MAX]; // R[node] is the right child of node
int tree[LOG_MAX * MAX]; // tree[node] is the value stored in the node
int root[MAX]; // stores the root of each version
int next_vertex; // next index for a vertex
int version_count; // number of different versions of the tree

void calc(int node) {
    int sum = 0;
    if(L[node]) sum += tree[L[node]];
    if(R[node]) sum += tree[R[node]];
    tree[node] = sum;
}
void update(int prev, int node, int start, int end, int idx, int value) {
    if(start == end)
        tree[node] = tree[prev] + value;
    else {
        int mid = (start + end) / 2;
        if(start <= idx and idx <= mid) {
        R[node] = R[prev];
        if(L[node] == 0) L[node] = next_vertex++;
        update(L[prev], L[node], start, mid, idx, value);
        } else {
        L[node] = L[prev];
        if(R[node] == 0) R[node] = next_vertex++;
        update(R[prev], R[node], mid + 1, end, idx, value);
        }
        calc(node);
    }
}
int query(int node, int start, int end, int l, int r) {
    if(l > end or r < start) return 0;
    if(l <= start and end <= r) return tree[node];
    int mid = (start + end) / 2, q1 = 0, q2 = 0;
    if(L[node]) q1 = query(L[node], start, mid, l, r);
    if(R[node]) q2 = query(R[node], mid + 1, end, l, r);
    return q1 + q2;
}

void init() {
    root[0] = 0;
    next_vertex = 1;
    version_count = 1;
}
int update(int idx, int value, int prev_version = -1) {
    if(prev_version == -1) prev_version = version_count - 1;
    root[version_count] = next_vertex++;
    update(root[prev_version], root[version_count], 0, n - 1, idx, value);
    version_count++;
    return version_count - 1;
}
int query(int l, int r, int version = -1) {
    if(l == -1 or r == -1) return 0;
    if(version == -1) version = version_count - 1;
    return query(root[version], 0, n - 1, l, r);
}

int query_budget(int node_l, int node_r, int start, int end, int budget) {
    if(tree[node_r] - tree[node_l] <= budget)
        return tree[node_r] - tree[node_l];

    if(start == end)  return 0;

    int s = 0;
    if(L[node_r]) s = tree[L[node_r]] - tree[L[node_l]];

    int mid = (start + end) / 2;

    if(s <= budget) {
        if(R[node_r])
           s += query_budget(R[node_l], R[node_r], mid + 1, end, budget - s);
    } else {
        s = 0;
        if(L[node_r])
            s = query_budget(L[node_l], L[node_r], start, mid, budget);
    }
    return s;
}

void solve(){
    int q, sum = 0;
    cin >> n >> q;

    map<int, bool> cor;
    map<int, int> mapping;

    vector<int> price(n);
    for(int &w : price) cin >> w, sum += w, cor[w] = true;

    int id = 0;
    for(auto it : cor)
        mapping[it.fi] = id++;

    auto get_pos = [&](int x) {
        auto it = mapping.upper_bound(x);
        if(it == mapping.begin()) return -1ll;
        it--;
        return it->se;
    };

    vector<int> version = {0};

    init();

    for(int i = 0; i < n; ++i)
        version.push_back(update(get_pos(price[i]), price[i], version.back()));

    int ans = 0;

    for(int i = 1; i <= q; ++i) {
        int x, y, z;
        cin >> x >> y >> z;

        int l = 1 + (((x + ans - 1) % n) + n) % n;
        int r = 1 + (((y + ans - 1) % n) + n) % n;
        int budget = z + ans;

        ans = query_budget(root[version[l - 1]], root[version[r]], 0, n - 1, budget);
        cout << ans << '\n';
    }

}

int32_t main() {
    fastio;
    solve();
    return 0;
}