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
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define pll pair<ll,ll>
#define pii pair<int,int>
#define ld long double
using namespace std;
const int N = 5e5+1,mod = 1e9+7;
ll A[N],B[N],granica[N],loga[N],pref[N],product[N],prefproduct[N];
int n,q;

ll fastpow(ll x,ll p){
    if(p == 0)return 1;
    if(p == 1)return x % mod;
    ll temp = fastpow(x,p>>1);
    temp = (temp*temp)%mod;
    if(p&1)temp = (temp*x)%mod;
    return temp;
}

ll table[20][N];
void set_table(){
    for(int i = 1;i < 20;i++){
        for(int j = 1;j + (1<<(i-1)) <= n;j++){
            table[i][j] = min(table[i-1][j],table[i-1][j + (1<<(i-1))]);
        }
    }
}

void set_prefix_products(){
    product[0] = 1;
    for(int i = 1;i <= n;i++)product[i] = (product[i-1] * B[i])%mod;
    for(int i = 1;i <= n;i++){
        if(B[i] == 1)prefproduct[i] = (prefproduct[i-1] + A[i]) % mod;
        else prefproduct[i] = (prefproduct[i-1] * B[i]) % mod;
    }
}

ll rangeproduct(int l,int r){
    return (product[r] * fastpow(product[l-1],mod-2)) % mod;
}

ll przedzial(ll amount, int l,int r){
    ll x1 = (amount * rangeproduct(l,r)) % mod;
    ll x2 = (prefproduct[r] - ((prefproduct[l-1] * rangeproduct(l,r)) % mod) + mod) % mod;
    //cout << x1 << " " << x2 << "\n";
    return (x1 + x2) % mod;
}

ll query(int l,int r){
    int len = r - l + 1;
    int pietro = loga[len];
    return min(table[pietro][l],table[pietro][r - (1<<pietro) + 1]);
}

int znajdz_nast(int poz,ll amount){
    int a = poz - 1,b = n+1,c;
    while(b - a > 1){
        c = (a + b) / 2;
        if(query(poz,c) + pref[poz - 1] - amount < 0)b = c;
        else a = c;
    }
    return b;
}



int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    for(int i = 1;i <= n;i++){
        cin >> A[i] >> B[i];
        if(B[i] == 1)granica[i] = (ll)1e18;
        else granica[i] = A[i] / (B[i] - 1) + (A[i] % (B[i]- 1) > 0);
    }
    for(int i = 1;i <= n;i++){
        if(i > 1)loga[i] = loga[i/2] + 1;
        pref[i] = pref[i-1] + A[i];
        table[0][i] = granica[i] - pref[i-1];
    }
    set_table();
    set_prefix_products();

    //for(int i = 1;i <= n;i++)cout << prefproduct[i] << " ";
    //cout << "\n";
    //cout << przedzial(2,3,7);
    for(int i = 0;i < q;i++){
        int l,r,poz;
        ll amount;
        cin >> amount >> l >> r;
        l++;
        while(amount < mod && l <= r){
            poz = znajdz_nast(l,amount);
            //cout << poz << "\n";
            if(poz > r){
                amount = (amount + pref[r] - pref[l-1]) % mod;
                l = r+1;
                break;
            }
            amount += pref[poz-1] - pref[l-1];
            amount *= B[poz];
            l = poz + 1;
        }
        if(l <= r)amount = przedzial(amount,l,r);
        cout << amount << "\n";
    }
}