COW ON TREE

#include <iostream>
#include <cstdio>
#define task ""
using namespace std;
using ll = long long;
using ld = long double;

const int N = 2e5 + 2;
int n, q;
const int Inf = 1e9;
ll a[N], st[N * 4];

void upd(int id, int l, int r, int &pos, ll &val){
    if(l > pos || r < pos)
        return;
    if(l == r && r == pos){
        st[id] = val;
        return;
    }
    upd(id << 1, l, (l + r) / 2, pos, val);
    upd(id << 1 | 1, (l + r) / 2 + 1, r, pos, val);
    st[id] = min(st[id << 1], st[id << 1 | 1]);
}

void Read(){
    cin >> n >> q;
    fill_n(st, N * 4, 1e18);
    for(int i = 1; i <= n; ++i)
        cin >> a[i],
        upd(1, 1, n, i, a[i]);
}

// Thứ gọi là "CON BÒ TRÊN CÂY" đây nhé

int que(int id, int l, int r, int &pos, ll &v){
    if(r < pos || st[id] > v)
        return Inf;
    if(l == r && r >= pos)
        return st[id] <= v ? l : Inf;
    int mid = (l + r) / 2;
    if(mid >= pos && st[id << 1] <= v){
        int ans = que(id << 1, l, mid, pos, v);
        if(ans != Inf)
            return ans;
        return que(id << 1 | 1, mid + 1, r, pos, v);
    }
    return que(id << 1 | 1, mid + 1, r, pos, v);
}

--- END ---

void Solve(){
    while(q--){
        ll v;
        int l, r, now;
        cin >> v >> l >> r;
        do{
            now = que(1, 1, n, l, v);
            if(now <= r)
                v %= a[now];
            //cout << "chosen: " << now << "\n";
            l = now + 1;
        }while(l <= r);
        cout << v << "\n";
    }
}

main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0); if(fopen(task".INP", "r"))
    freopen(task".INP", "r", stdin),
    freopen(task".OUT", "w", stdout);
    Read();
    Solve();
}