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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#include <cstdio>
#include <string>
#include <vector>
#include <array>
using namespace std;

template<typename T, T mod, typename U=size_t>
struct basic_mod {
protected:
    T v;
public:
    template<typename V>
    constexpr basic_mod(const V& val) : v((val%mod+mod)%mod) {}
    constexpr basic_mod operator*(basic_mod other) const {other.v=other.v*static_cast<U>(v)%mod; return other;}
    constexpr basic_mod operator+(basic_mod other) const {other.v=(other.v+v)%mod; return other;}
    constexpr basic_mod operator-() const {basic_mod res; res.v=(mod-v)%mod; return res;}
    constexpr basic_mod operator-(const basic_mod& other) const {return operator+(-other);}
    constexpr basic_mod& operator*=(const basic_mod& other) {return *this=operator*(other);}
    constexpr basic_mod& operator+=(const basic_mod& other) {return *this=operator+(other);}
    constexpr basic_mod& operator-=(const basic_mod& other) {return *this=operator-(other);}
    constexpr basic_mod& operator++() {this->v=v==mod-1?0:v+1;return *this;}
    constexpr basic_mod operator++(int) {basic_mod res(*this); this->v=v==mod-1?0:v+1; return res;}
    constexpr basic_mod& operator--() {this->v=v?v-1:mod-1;return *this;}
    constexpr basic_mod operator--(int) {basic_mod res(*this); this->v=v?v-1:mod-1; return res;}
    constexpr explicit operator T&() {return v;}
};
constexpr auto mod = 1'000'000'007;
typedef basic_mod<unsigned, mod> mint;

template<typename T>
struct basic_func {
    T a,b;
    constexpr basic_func() : a(1),b(0) {}
    constexpr basic_func(const T& a, const T& b) : a(a),b(b) {}
    constexpr basic_func(const basic_func& other) : a(other.a),b(other.b) {}
    basic_func& operator=(const basic_func& other) {a=other.a;b=other.b;return *this;}
    template<typename U>
    constexpr basic_func(const basic_func<U>& other) : a(other.a),b(other.b) {}
    template<typename U>
    constexpr basic_func& operator=(const basic_func<U>& other) {a=other.a;b=other.b;return *this;}
    bool operator==(const basic_func& g) const {return a==g.a&&b==g.b;}
    bool operator!=(const basic_func& g) const {return a!=g.a||b!=g.b;}
    // f(x)=f(x)+c
    constexpr basic_func& operator+=(const T& c) {b+=c;return *this;}
    // f(x)=m*f(x)
    constexpr basic_func& operator*=(const T& m) {a*=m;b*=m;return *this;}
    // f∘g
    constexpr basic_func operator*(basic_func g) const {
        g.b+=g.a*this->b;
        g.a*=this->a;
        return g;
    }
    // f=f∘g
    constexpr basic_func& operator*=(const basic_func& g) {
        this->b = this->b*g.a + g.b;
        this->a*=g.a;
        return *this;
    }
    // f(x)
    constexpr T operator()(const T& x) const {return a*x+b;}
};
typedef basic_func<unsigned long> func;
typedef basic_func<mint> mfunc;

struct choice {
    func f,g;
    constexpr choice() : f(), g() {}
    constexpr unsigned long operator()(unsigned long x) const {return max(f(x),g(x));}
};
constexpr size_t lg = 19;
int getint() {
    auto c=getchar_unlocked();
    while (c<'0'||c>'9')c=getchar_unlocked();
    int res = c-'0';
    while ((c=getchar_unlocked())>='0'&&c<='9')
        res*=10,res+=c-'0';
    return res;
}
int main() {
    int n=getint(),q=getint();
    vector<pair<unsigned,choice>> choices;
    int choiceid[n+1];
    unsigned long addpref[n+1];
    addpref[0]=0;
    for (int i=0;i<n;++i) {
        int a=getint(),b=getint();
        addpref[i+1]=addpref[i]+a;
        if (!i||choices.back().second.f!=choices.back().second.g)choices.emplace_back(i,choice());
        choices.back().second.f+=a;
        if (b>1) choices.back().second.g*=b;
        else choices.back().second.g+=a;
        choiceid[i]=choices.size()-1;
    }
    const int m = choices.size();
    choiceid[n]=m;
    unsigned nextinc[m];
    array<mfunc,lg> sparse[m];
    unsigned lastinc=m;
    for (int i=m-1;i>=0;--i) {
        if (choices[i].second(0)) lastinc=i;
        nextinc[i]=lastinc;

        sparse[i][0]=choices[i].second.g;
        for (unsigned h=1;h<lg;++h)
            if (i+(1<<(h-1))<m) sparse[i][h]=sparse[i][h-1]*sparse[i+(1<<(h-1))][h-1];
            else sparse[i][h]=sparse[i][h-1];
    }
    // f(l)∘f(l+1)∘...∘f(r-1)
    auto getfunc = [&sparse](unsigned l, unsigned r) {
        mfunc res;
        if (l>=r) return res;
        const auto diff = r-l;
        for (unsigned h=0;h<lg;++h)
            if (diff&(1u<<h)) {
                res*=sparse[l][h];
                l+=1<<h;
            }
        return res;
    };
    string out;
    while (q--) {
        unsigned long x=getint(); unsigned l=getint(),r=getint(); 
        auto b=choiceid[l],e=choiceid[r];
        if (b==e) out.append(to_string((x+addpref[r]-addpref[l])%mod)).push_back('\n');
        else {
            x=choices[b].second(x-(addpref[l]-addpref[choices[b].first]));++b;
            if (!x)// if x is 0, it wont increae >= *2, so we jump to the next increase
                b=nextinc[b];
            while (b<e&&x<mod) x=choices[b++].second(x);
            mint v = getfunc(b, e)(x); // x>=a_i => 2x>=x+a_i, so we always take multiply
            if (e<m) v+=addpref[r]-addpref[choices[e].first];
            out.append(to_string(unsigned(v))).push_back('\n');
        }
    }
    fwrite_unlocked(out.c_str(), 1, out.size(), stdout);
}