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
140
141
142
143
144
#include <cstdio>
#include <cstdlib>
#include <cstdint>
#include <cassert>

#include <algorithm>

const uint64_t MODULUS = 1000 * 1000 * 1000 + 7;

uint32_t add_wrapping(uint32_t a, uint32_t b) {
    return uint32_t((uint64_t(a) + uint64_t(b)) % MODULUS);
}

uint32_t neg_wrapping(uint32_t a) {
    return (a > 0) ? MODULUS - a : 0;
}

uint32_t mul_wrapping(uint32_t a, uint32_t b) {
    return uint32_t((uint64_t(a) * uint64_t(b)) % MODULUS);
}

std::pair<int32_t, int32_t> extended_euclid(int32_t a, int32_t b) {
    if (b == 0) {
        return {1, 0};
    } else {
        const auto [x, y] = extended_euclid(b, a - (a / b) * b);
        return {y, x - (a / b) * y};
    }
}

uint32_t inverse_wrapping(uint32_t a) {
    auto [x, y] = extended_euclid(MODULUS, a);
    // fprintf(stderr, "%d * %d + %d * %d = 1\n", x, (uint32_t)MODULUS, y, a);
    if (y < 0) {
        y += MODULUS;
    }
    return y;
}

struct encounter_t {
    uint32_t add;
    uint32_t mul;

    static encounter_t merge(const encounter_t& b, const encounter_t& a) {
        // a(x) = a.add + a.mul * x;
        // b(x) = b.add + b.mul * x;
        // (a.b)(x) = a.add + a.mul * (b.add + b.mul * x);
        // (a.b)(x) = (a.add + a.mul * b.add) + (a.mul * b.mul) * x;
        return encounter_t {
            .add = add_wrapping(a.add, mul_wrapping(a.mul, b.add)),
            .mul = mul_wrapping(a.mul, b.mul),
        };
    }

    encounter_t inverse() const {
        // y = a.add + a.mul * x;
        // y - a.add = a.mul * x;
        // (y - a.add) * a.mul^-1 = x;
        // y * a.mul^-1 - a.add * a.mul^-1 = x;
        const uint32_t inv_mul = inverse_wrapping(mul);
        return encounter_t {
            .add = neg_wrapping(mul_wrapping(add, inv_mul)),
            .mul = inv_mul,
        };
    }

    uint32_t apply(uint64_t x) const {
        return add_wrapping(mul_wrapping(x, mul), add);
    }
};

encounter_t encounters[500 * 1000 + 1];
encounter_t prefix_mul_prefer[500 * 1000 + 1];
uint64_t prefix_sums[500 * 1000 + 1];
int next_mul[500 * 1000 + 1];

int main() {
    int n, q;
    scanf("%d %d", &n, &q);

    prefix_mul_prefer[0].add = 0;
    prefix_mul_prefer[0].mul = 1;
    prefix_sums[0] = 0;
    for (int i = 0; i < n; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        encounters[i].add = a;
        encounters[i].mul = b;
        const auto mul_prefer_encounter = (b > 1)
            ? encounter_t{.add = 0, .mul = uint32_t(b)}
            : encounter_t{.add = uint32_t(a), .mul = 1};
        prefix_mul_prefer[i + 1] = encounter_t::merge(prefix_mul_prefer[i], mul_prefer_encounter);
        prefix_sums[i + 1] = prefix_sums[i] + uint64_t(a);

        // SANITY CHECK
        // auto inv_encounter = prefix_encounters[i + 1].inverse();
        // auto identity_encounter = encounter_t::merge(inv_encounter, prefix_encounters[i + 1]);
        // assert(identity_encounter.add == 0);
        // assert(identity_encounter.mul == 1);
    }

    int curr_next_mul = n;
    for (int i = n - 1; i >= 0; i--) {
        next_mul[i] = curr_next_mul;
        if (encounters[i].mul > 1) {
            curr_next_mul = i;
        }
    }

    for (int i = 0; i < q; i++) {
        // fprintf(stderr, "Processing request %d\n", i);
        int x, l, r;
        scanf("%d %d %d", &x, &l, &r);

        uint64_t state = x;
        while (true) {
            // fprintf(stderr, " Current state at %d: %llu\n", l, state);
            if (l == r) {
                // fprintf(stderr, " Arrived\n");
                break;
            }
            state = std::max(state + encounters[l].add, state * encounters[l].mul);
            // fprintf(stderr, " State is now %llu after applying better option\n", state);
            if (state >= MODULUS) {
                l++;
                // fprintf(stderr, " Limit reached\n");
                break;
            }
            int curr_next_mul = std::min(next_mul[l], r);
            state += prefix_sums[curr_next_mul] - prefix_sums[l + 1];
            l = curr_next_mul;
            // fprintf(stderr, " State is now %llu after summing (l = %d)\n", state, l);
            if (state >= MODULUS) {
                // fprintf(stderr, " Limit reached\n");
                break;
            }
        }
        state %= MODULUS;
        state = encounter_t::merge(prefix_mul_prefer[l].inverse(), prefix_mul_prefer[r]).apply(state);
        printf("%d\n", (int)state);
    }

    return 0;
}