1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <bits/stdc++.h>
 
using namespace std;

#define ll long long
 
constexpr ll MOD = 1e9 + 7;
constexpr ll INF = numeric_limits<ll>::infinity(); 

ll modInv(ll n) {
    ll res = 1;
    ll exp = MOD - 2;
    n %= MOD;
    while (exp) {
        if (exp % 2) res = (res * n) % MOD;
        n = (n * n) % MOD;
        exp /= 2;
    }
    return res;
}

int jumpToMult(int nodes, int l, int r, ll x_to_mult, const vector<ll>& lookup) {
    int cur_node = l + nodes - 1;
    while (cur_node <= r + nodes - 1) {
        if (cur_node % 2) {
            if (lookup[cur_node] < x_to_mult) {
                break;
            } else {
                cur_node++;
            }
        }
        cur_node /= 2;
    }
    if (!cur_node || lookup[cur_node] >= x_to_mult) return -1;
    while (cur_node < nodes) {
        if (lookup[2 * cur_node] < x_to_mult) {
            cur_node = 2 * cur_node;
        } else {
            cur_node = 2 * cur_node + 1;
        }
    }
    return (cur_node - nodes + 1 <= r) ? cur_node - nodes + 1 : -1;
}

int main() {
    int n, q;
    cin >> n >> q;

    vector<ll> a(n + 1), b(n + 1);
    vector<ll> sums(n + 1), switch_to_mult(n + 1), mult_res(n + 1), add_res(n + 1);

    sums[0] = 0;
    mult_res[0] = 1;
    add_res[0] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        sums[i] = sums[i - 1] + a[i];
        if (b[i] > 1) {
            ll min_x_to_mult = a[i] / (b[i] - 1);
            switch_to_mult[i] = min_x_to_mult - sums[i - 1];
        }
        ll m_op = (b[i] > 1) ? b[i] % MOD : 1;
        ll a_op = (b[i] == 1) ? a[i] % MOD : 0;
        mult_res[i] = (mult_res[i - 1] * m_op) % MOD;
        add_res[i] = (add_res[i - 1] * m_op + a_op) % MOD;
    }

    int nodes = 1;
    while (nodes <= n) nodes *= 2;
    vector<ll> lookup(nodes * 2);
    for (int i = 1; i <= n; i++) lookup[nodes + i - 1] = switch_to_mult[i];
    for (int i = nodes - 1; i >= 1; i--) lookup[i] = min(lookup[2 * i], lookup[2 * i + 1]);

    for (int i = 0; i < q; i++) {
        ll x;
        int l, r;
        bool above_mod = false;

        cin >> x >> l >> r;
        //int curr = l;
        int curr = l + 1;

        while (curr <= r) {
            if (above_mod) {
                ll mults = (mult_res[r] * modInv(mult_res[curr - 1])) % MOD;
                ll adds = (add_res[r] - mults * add_res[curr - 1]) % MOD;
                while (adds < 0) adds += MOD;
                x = (mults * x + adds) % MOD;
                break;
            }

            ll x_to_mult = x - sums[curr - 1];
            int mult_idx = jumpToMult(nodes, curr, r, x_to_mult, lookup);

            if (mult_idx == -1) { 
                x = (x + sums[r] - sums[curr - 1]) % MOD;
                break;
            } else {
                ll adds = sums[mult_idx - 1] - sums[curr - 1];
                if (x + adds > MOD) {
                    x = (x + adds) % MOD;
                    x = (x * b[mult_idx]) % MOD;
                    above_mod = true;
                } else {
                    x = x + adds;
                    x = x * b[mult_idx];
                    if (x > MOD) {
                        above_mod = true;
                        x %= MOD;
                    }
                }
                curr = mult_idx + 1;
            }
        }
        cout << x << endl;
    }
    return 0;
}