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
#include <bits/stdc++.h>
#define nl '\n'

using namespace std;
using ll = long long;
using pll = pair<ll,ll>;
const int mod = 1e9+7;
const int MAXN = 5e5+1;
const int TSIZE = 1<<19;

pll choices[MAXN];
vector<pll> tree(TSIZE<<1, {1, 0});
ll prefix[MAXN];
int next_decision[MAXN];

pll combine(pll f1, pll f2){
    auto [a1, b1] = f1;
    auto [a2, b2] = f2;
    return {a1*a2%mod, (a2*b1+b2)%mod};
}

pll query(int a, int b){
    a += TSIZE;
    b += TSIZE;
    pll res1 = {1, 0};
    pll res2 = {1, 0};
    while(a < b){
        if(a & 1){
            res1 = combine(res1, tree[a]);
            a++;
        }
        if(~b & 1){
            res2 = combine(tree[b], res2);
            b--;
        }
        a >>= 1;
        b >>= 1;
    }
    if(a==b){
        res1 = combine(res1, tree[a]);
    }
    return combine(res1, res2);
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, q;
    cin>>n>>q;
    for(int i=1; i<=n; i++){
        ll b, a;
        cin>>b>>a;
        choices[i] = {a, b};
        prefix[i] = prefix[i-1] + b;
        if(a == 1){
            tree[i+TSIZE] = {a, b};
        }else{
            tree[i+TSIZE] = {a, 0};
        }
    }
    next_decision[n] = n+1;
    for(int i=n-1; i>=0; i--){
        next_decision[i] = choices[i+1].first <= 1 ? next_decision[i+1] : i+1;
    }
    for(int i=TSIZE-1; i>0; i--){
        tree[i] = combine(tree[2*i], tree[2*i+1]);
    }
    while(q--){
        int l, r;
        ll x;
        cin>>x>>l>>r;
        l++;
        while(x < mod && l <= r){
            //cerr<<l<<' ';
            x = max(x*choices[l].first, x+choices[l].second);
            x += prefix[min(next_decision[l], r+1)-1] - prefix[l];
            l = min(next_decision[l], r+1);
            //l++;
        }
        //cerr<<nl;
        x %= mod;
        auto [a, b] = query(l, r);
        cout<<(a*x%mod+b)%mod<<nl;
    }
    return 0;
}