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
import sys

data = sys.stdin.read().split()
idx = 0
n = int(data[idx]); idx += 1
q = int(data[idx]); idx += 1

a = [0] * (n + 2)
b = [0] * (n + 2)
for i in range(1, n + 1):
    a[i] = int(data[idx]); idx += 1
    b[i] = int(data[idx]); idx += 1

MOD = 10**9 + 7
MAX_TH = 2 * 10**9 + 100

prefix_a = [0] * (n + 2)
for i in range(1, n + 1):
    prefix_a[i] = prefix_a[i - 1] + a[i]

next_mult = [n + 1] * (n + 2)
for i in range(n, 0, -1):
    next_mult[i] = i if b[i] >= 2 else next_mult[i + 1]

# Affine segment tree (M, S) for huge mode
tree_m = [0] * (4 * n + 100)
tree_s = [0] * (4 * n + 100)

def build_aff(node, st, en):
    if st == en:
        if b[st] == 1:
            tree_m[node] = 1
            tree_s[node] = a[st] % MOD
        else:
            tree_m[node] = b[st] % MOD
            tree_s[node] = 0
        return
    md = (st + en) // 2
    build_aff(2 * node, st, md)
    build_aff(2 * node + 1, md + 1, en)
    lm, ls = tree_m[2 * node], tree_s[2 * node]
    rm, rs = tree_m[2 * node + 1], tree_s[2 * node + 1]
    tree_m[node] = (rm * lm) % MOD
    tree_s[node] = (rm * ls + rs) % MOD

if n >= 1:
    build_aff(1, 1, n)

def get_aff(node, st, en, ql, qr):
    if qr < st or en < ql:
        return 1, 0
    if ql <= st and en <= qr:
        return tree_m[node], tree_s[node]
    md = (st + en) // 2
    lm, ls = get_aff(2 * node, st, md, ql, qr)
    rm, rs = get_aff(2 * node + 1, md + 1, en, ql, qr)
    cm = (rm * lm) % MOD
    cs = (rm * ls + rs) % MOD
    return cm, cs

# Queries
answers = []
for _ in range(q):
    x = int(data[idx]); idx += 1
    li = int(data[idx]); idx += 1
    ri = int(data[idx]); idx += 1
    L = li + 1
    R = ri
    if L > R:
        answers.append(str(x % MOD))
        continue
    curr = x
    pos = L
    while pos <= R:
        nxt = next_mult[pos]
        if nxt > R:
            curr += prefix_a[R] - prefix_a[pos - 1]
            break
        curr += prefix_a[nxt - 1] - prefix_a[pos - 1]
        if curr >= MAX_TH:
            curr *= b[nxt]
            pos = nxt + 1
            if pos > R:
                ans = curr % MOD
            else:
                M, S = get_aff(1, 1, n, pos, R)
                ans = (M * (curr % MOD) + S) % MOD
            answers.append(str(ans))
            break
        pos = nxt
        addv = curr + a[pos]
        mulv = curr * b[pos]
        if mulv >= addv:
            curr = mulv
            if curr >= MAX_TH:
                pos += 1
                if pos > R:
                    ans = curr % MOD
                else:
                    M, S = get_aff(1, 1, n, pos, R)
                    ans = (M * (curr % MOD) + S) % MOD
                answers.append(str(ans))
                break
        else:
            curr = addv
        pos += 1
    else:
        ans = curr % MOD
    if 'ans' not in locals() or len(answers) == _:
        answers.append(str(ans if 'ans' in locals() else curr % MOD))

print('\n'.join(answers))