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
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

constexpr ll P = 1e9 + 7;
constexpr ll N = 5e5 + 5;
ll n, q, a[N], b[N], sfm[N], sfa[N], l, r, x, mul, nxt[N], p[N], aa, bb;
// next[j] holds the next index i > j where b_i > 1


ll bp(ll num, ll pow) {
    ll ans = 1;
    while(pow) {
        if(pow&1) ans = (ans * num) % P;
        num = (num * num) % P;
        pow >>= 1;
    }
    return ans;
}

ll inv(ll num) { return bp(num, P - 2); }

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    for(int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
    p[1] = a[1];
    for(int i = 2; i <= n; ++i) p[i] = (p[i - 1] + a[i]) % P;
    x = -1;
    for(int i = n; i > 0; --i) {
        nxt[i] = x;
        if(b[i] > 1) x = i;
    }
    mul = 1, aa = 1, bb = 0;
    for(int i = n; i > 0; --i) {
        if(b[i] > 1) aa = (aa * b[i]) % P;
        else bb = (bb + aa * a[i]) % P;
        sfm[i] = aa, sfa[i] = bb;
    }
    sfm[n + 1] = 1, sfa[n + 1] = 0;
    for(int t = 0; t < q; ++t) {
        cin >> x >> l >> r;
        bool us = false;
        ++l;
        while(x <= P && l <= r) {
            x = max(x + a[l], x * b[l]); //conajmniej podwaja x
            if(nxt[l] != -1) x += p[min(r, nxt[l] - 1)] - p[l];
            else {us = true; break; };
            l = nxt[l];
        }
        x %= P;
        if(l > r) {
            cout << x << '\n';
            continue;
        }
        if(!us) x = max(x + a[l], x * b[l]) % P;
        if(nxt[l] == -1) {
            x = (x + p[r] - p[l]) % P;
            cout << x << '\n';
            continue;
        }
        // mxt[l] != -1 and l <= r, l-th choice wasnt made
        // l < r and l-th choice wasnt made
        if(r == n) {
            x = x * sfm[l + 1] % P + sfa[l + 1];
            x %= P;
        } else {
            x = x * sfm[l + 1] % P * inv(sfm[r + 1]) % P;
            x += (sfa[l + 1] - sfa[r + 1] + P) % P * inv(sfm[r + 1]) % P;
            x %= P;
        }
        cout << x << '\n';
    }
}