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
#include<iostream>
#include<vector>
#define PB push_back
#define ll long long
constexpr int MN=5e5+15;
constexpr ll MOD=1e9+7;
using namespace std;
ll pref[MN];
ll sum(int i,int j){return pref[j]-pref[i-1];}
int thresh[MN];
int mthresh[MN];
//ll Min[MN*4];
int N=1,n;
ll a[MN];ll b[MN];
/*int wdol(int r,int inx)
{
   // cout<<inx<<' '<<r<<";\n";
    if(inx>=N) return inx;
    if(r>=Min[inx*2]) return wdol(r,inx*2);
    return wdol(r,inx*2+1);
}
int wgore(bool zl,int r,int inx)
{
    if(inx==0) return N*2+1;
  if(zl && r>=Min[inx]) return wdol(r,inx*2+1);
  return wgore(1-inx%2,r,inx/2);
}*/

struct rownanie{
    ll a,b;
    rownanie merge(const rownanie& r){return {(a*r.a)%MOD,(r.a*b+r.b)%MOD};}
    ll f(ll x){return a*x+b;}
}Drzewo[4*MN];

void inicjuj()
{
    for(int j=1;j<=n;j++){if(a[j]==1){Drzewo[N+j-1].a=1;Drzewo[N+j-1].b=b[j];} else Drzewo[N+j-1].a=a[j];}
    for(int j=N-1;j>=1;j--){Drzewo[j]=Drzewo[j*2].merge(Drzewo[j*2+1]);}

  //   for(int j=1;j<=n;j++){if(thresh[j]!=MOD) {Min[j+N-1]=thresh[j]-pref[j-1];}else Min[j+N-1]=1e18;}
  //   for(int j=N-1;j>=1;j--) Min[j]=min(Min[j*2],Min[j*2+1]);
}
rownanie funkcja(int l,int p,int lo,int hi,int inx)
{
    if(l==lo && p==hi) return Drzewo[inx];
    int mid=(lo+hi)/2;
    if(p<=mid) return funkcja(l,p,lo,mid,inx*2);
    if(l>mid) return funkcja(l,p,mid+1,hi,inx*2+1);
    return funkcja(l,mid,lo,mid,inx*2).merge(funkcja(mid+1,p,mid+1,hi,inx*2+1));
}
int main(){
ios_base::sync_with_stdio(0);
int q;
cin>>n>>q; while(N<n)N*=2;
for(int j=1;j<=n;j++) cin>>b[j]>>a[j];

vector<int>mnozenie,dodatnie;
mnozenie.PB(-1);
for(int j=1;j<=n;j++){if(a[j]>1) mnozenie.PB(j);if(b[j]>0) dodatnie.PB(j);}
mnozenie.PB(2*N+1);dodatnie.PB(2*N+1);
for(int j=0;j<n;j++) pref[j+1]=pref[j]+b[j+1];
for(int j=1;j<=n;j++) if(a[j]==1) thresh[j]=MOD;else thresh[j]=(b[j]-1)/(a[j]-1)+1;
for(int j=n;j>0;j--) {if(thresh[j]==MOD)mthresh[j]=mthresh[j+1];else mthresh[j]=max(mthresh[j+1],thresh[j]);}
inicjuj();
//for(int j=1;j<=n;j++) cout<<j<<": "<<pref[j]<<endl;
//for(int j=1;j<=n;j++) cout<<j<<": "<<thresh[j]<<endl;
//for(int j=1;j<=n;j++) cout<<j<<": "<<mthresh[j]<<endl;
//for(int j=1;j<=n;j++) cout<<j<<": "<<Min[j+N-1]<<endl;
int l,p,nowy,inx;ll x;
for(int j=0;j<q;j++)
{
    cin>>x>>l>>p;
    int akt=l;
    if(x==0){int nowy=(*lower_bound(dodatnie.begin(),dodatnie.end(),p));if(nowy>p) {cout<<0<<endl;continue;}l=nowy-1;}
    int lo=0,hi=mnozenie.size()-1;
    while(lo<hi)
    {
        int mid=(lo+hi+1)/2;
        if(x>mnozenie[mid])
            lo=mid;
        else hi=mid-1;
    }
    while(x<mthresh[akt+1] && akt<p)
    {
        lo++;
        int kan=mnozenie[lo];
        if(kan>p){x=(x+pref[p]-pref[akt])%MOD;akt=p;break;}
        x=(MOD+x+pref[kan-1]-pref[akt])%MOD;
        if(x>=thresh[kan]) x=(x*a[kan])%MOD;else x=(x+b[kan])%MOD;
        akt=kan;
    }
   // cout<<akt<<' '<<p<<' '<<x<<endl;
    if(akt<p) x=(funkcja(akt+1,p,1,N,1).f(x))%MOD;
    cout<<x<<endl;
}
}