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
#include <algorithm>
#include <iostream>
#include <vector>

#define lol long long

const lol m1e9p7 = 1'000'000'000 + 7;

using namespace std;

lol div_mod(lol a, lol b) {
    int M = m1e9p7;
    int y = 0, x = 1;

    while (b > 1) {
        int q = b / M;
        int t = M;
        M = b % M, b = t;
        t = y;
        y = x - q * y;
        x = t;
    }
    if (x < 0) x += m1e9p7;

    return (a * x) % m1e9p7;
}

int main() {
    int n, q;
    cin >> n >> q;
    struct multi_step {
        lol index;
        lol mul;
        lol add;
        lol pref_mul;
        lol pref_add;
        auto operator<=>(multi_step that) { return this->index <=> that.index; }
    };
    vector<multi_step> steps(0);
    steps.push_back(multi_step{-1, 1, 0, 1, 0});
    vector<lol> pref_adds(n + 1);
    pref_adds[0] = 0;
    for (int i = 1; i < n + 1; i++) {
        lol add, mul;
        cin >> add >> mul;
        pref_adds[i] = pref_adds[i - 1] + add;
        if (mul > 1) {
            steps.push_back(multi_step{
                i,                                                                                                                   //
                mul,                                                                                                                 //
                add,                                                                                                                 //
                (steps.back().pref_mul * mul) % m1e9p7,                                                                              //
                ((steps.back().pref_add + (pref_adds[i - 1] - pref_adds[max(steps.back().index, (lol)0)]) % m1e9p7) * mul) % m1e9p7  //
            });
        }
    }
    for (int i = 0; i < q; i++) {
        lol x, l, r;
        cin >> x >> l >> r;
        auto bound = upper_bound(steps.begin(), steps.end(), multi_step{l, 0, 0, 0, 0});
        while (bound != steps.end() && bound->index <= r && x < m1e9p7) {  // zadziala max 30 razy
            x += max(pref_adds[bound->index - 1] - pref_adds[l], (lol)0);
            l = bound->index;
            if (x * bound->mul > x + bound->add)
                x *= bound->mul;
            else
                x += bound->add;
            bound++;
        }
        if (bound == steps.end() || bound->index > r) {  // wczesne wyjscie
            x += pref_adds[r] - pref_adds[l];
            x %= m1e9p7;
            cout << x << "\n";
            continue;
        }
        // teraz mamy pewność, że x >= m1e9p7, więc mnozenie jest zawsze oplacalne
        x %= m1e9p7;

        bound--;
        auto ceiling = --upper_bound(steps.begin(), steps.end(), multi_step{r, 0, 0, 0, 0});
        lol total_mul = div_mod(ceiling->pref_mul, bound->pref_mul);
        lol total_add = (ceiling->pref_add + m1e9p7 - (bound->pref_add*total_mul) % m1e9p7) % m1e9p7;
        x *= total_mul;
        x %= m1e9p7;
        x += total_add;
        x += pref_adds[r] - pref_adds[ceiling->index];
        x %= m1e9p7;
        cout << x << "\n";
    }
}