Problem Description

Recently in Bajtocja, a mobile game called Potyczki Survival Shooter has become very popular. In this game, we control a squad of warriors moving along a straight path. From time to time, the squad encounters an event. In the $i$-th event, the player has two options: go on the left side of the road and gain $a_i$ additional warriors; or go on the right side and multiply the current number of warriors by $b_i$. Although everyone knows that having more warriors is better, the game’s ads clearly state that making the right decision can sometimes be very complicated.

After the first $l$ events, Bajtazar has $x$ warriors. (The number $x$ does not necessarily have to be obtainable from the first $l$ events according to the rules above—after all, these are warriors, not tourists, and a bad player may lose some of them in fights with zombies; those rules are not described in this problem.) He wants to know how many warriors he will have after event $r$ if he plays optimally. Please help him compute it.

Input Format

The first line contains integers $n$ and $q$ ($1 \leq n \leq 500\,000$, $1 \leq q \leq 100\,000$).

The next $n$ lines describe the events; the $i$-th line contains two integers $a_i$ and $b_i$ ($0 \leq a_i \leq 10^9 + 7$, $1 \leq b_i \leq 10^9 + 7$).

The next $q$ lines describe the queries; the $i$-th line contains three integers $x_i$, $l_i$, and $r_i$ ($0 \leq x_i \leq 10^9 + 7$, $0 \leq l_i \leq r_i \leq n$).

Output Format

For each query, output one number: the number of warriors when using the optimal strategy. Output the result modulo $10^9 + 7$.

10 2
3 2
3 2
3 2
0 1000
0 1000
0 1000
0 1000
0 1000
0 1000
123 1
1 0 3
1 3 9

16
49

Hint

Sample explanation: In the first query, Bajtazar starts with $1$ warrior. In the first event, he can gain $3$ additional warriors, or multiply the number of warriors by $2$. Under the optimal strategy, he chooses the first option, so he will have $4$ warriors. The next two events are the same, but this time doubling the number of warriors is more beneficial. In the end, Bajtazar will have $16$ warriors.

Translated by ChatGPT 5