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
#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll modi = 1'000'000'007;
 
void solve(){
    ll n, q; cin>>n>>q;

    vector<ll> a(n, 0), b(n, 0);
    for(int i=0; i<n; i++) cin>>a[i]>>b[i];

    vector<ll> aPrefsum(n, 0); aPrefsum[0] = a[0];
    for(int i=1; i<n; i++) aPrefsum[i] = aPrefsum[i-1] + a[i];

    set<int> bNonOne;
    for(int i=0; i<n; i++) if(b[i] != 1) bNonOne.insert(i);

    // sparse table

    vector<vector<pair<ll, ll>>> st(20, vector<pair<ll, ll>>(n));
    for(int i=0; i<n; i++){
        if(b[i] != 1) st[0][i] = {0, b[i]};
        else st[0][i] = {a[i], 1};
    }

    for(int k=1; k<20; k++)
        for(int i=0; i<n; i++)
            if(i+(1LL << (k-1)) < n){
                pair<ll, ll> leftSide = st[k-1][i];
                pair<ll, ll> rightSide = st[k-1][i+(1 << (k-1))];
                
                st[k][i] = {leftSide.first * rightSide.second + rightSide.first, leftSide.second * rightSide.second};
                st[k][i].first %= modi;
                st[k][i].second %= modi;
            }


    //

    while(q--){
        ll x, l, r; cin>>x>>l>>r;

        bool overModi = 0;

        while(!overModi){
            auto it = bNonOne.lower_bound(l);

            if(it != bNonOne.end() && *it < r){
                int nextB = *it;

                if(nextB != 0) x += aPrefsum[nextB-1];
                if(l != 0) x -= aPrefsum[l-1];

                if(x >= modi) overModi = 1;
                x %= modi;
                
                if(x * b[nextB] > x + a[nextB]) x *= b[nextB];
                else x += a[nextB];

                l = nextB+1;
                if(x >= modi) overModi = 1;
                x %= modi;
            }
            else{
                if(r != 0) x += aPrefsum[r-1];
                if(l != 0) x -= aPrefsum[l-1];

                if(x >= modi) overModi = 1;
                x %= modi;

                l = r;
                break;
            }
        }

        //cout<<x<<'\n';

        if(l != r){
            for(ll k=20; k>=0; k--){
                if(l + (1LL << k) <= r){
                    x *= st[k][l].second; x %= modi;
                    x += st[k][l].first; x %= modi;
                    l += (1LL << k);
                }
            }
        }

        cout<<x<<'\n';
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cout.tie(0); cin.tie(0);
 
    int sets; sets=1;
    while(sets--){
        solve();
    }
    return 0;
}