Recently, the mobile game Potyczki Survival Shooter has become very popular in Byteotia. In this game, you control a squad of warriors marching along a straight path. From time to time, the squad encounters an event. In the $i$-th event, the player has two options: go to the left side of the road and receive $a_i$ additional warriors, or go to the right side of the road and multiply the current number of warriors by $b_i$. Although everyone knows that the more warriors, the better, the game's advertisements clearly show that making the right decision can be very complicated.

Bajtazar has $x$ warriors after the first $l$ events. (The number $x$ does not necessarily have to be obtainable from those first $l$ events using the rules above – after all, these are warriors, not tourists; a weak player might lose some in a fight with zombies, the rules of which we do not describe in this task.) He wonders how many warriors he will have after event number $r$ if he plays optimally. Help him calculate this!

Input

The first line of input contains two integers $n$ and $q$ ($1 \le n \le 500\,000$, $1 \le q \le 100\,000$). The next $n$ lines contain descriptions of the events; the $i$-th line contains two integers $a_i$ and $b_i$ ($0 \le a_i < 10^9 + 7$, $1 \le b_i < 10^9 + 7$). The next $q$ lines contain descriptions of the queries; the $i$-th line contains three integers $x_i$, $l_i$, and $r_i$ ($0 \le x_i < 10^9 + 7$, $0 \le l_i < r_i \le n$).

Output

For each query, output a single number – the number of warriors when using the optimal strategy. Output the results modulo $10^9 + 7$.

Examples

Input 1

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

Output 1

16
49

Note

In the first query, Bajtazar starts with 1 warrior. In the first event, he can either get 3 additional warriors or multiply the number of warriors by 2. In the optimal strategy, he will choose the first option, resulting in 4 warriors. The next two events are the same, but this time it is more profitable to double the number of warriors. Ultimately, Bajtazar will have 16 warriors.