Kejin Player

Problem Description

Cuber QQ always envies those Kejin players, who pay a lot of RMB to get a higher level in the game. So he worked so hard that you are now the game designer of this game. He decided to annoy these Kejin players a little bit, and give them the lesson that RMB does not always work. This game follows a traditional Kejin rule of "when you are level $i$, you have to pay $a_i$ RMB to get to level $i+1$". Cuber QQ now changed it a little bit: "when you are level $i$, you pay $a_i$ RMB, are you get to level $i+1$ with probability $p_i$; otherwise you will turn into level $x_i$ ($x_i \le i$)". Cuber QQ still needs to know how much money expected the Kejin players needs to ``ke'' so that they can upgrade from level $l$ to level $r$, because you worry if this is too high, these players might just quit and never return again.

Input

The first line of the input is an integer $t$, denoting the number of test cases. For each test case, there is two space-separated integers $n$ ($1 \le n \le 500~000$) and $q$ ($1 \le q \le 500~000$) in the first line, meaning the total number of levels and the number of queries. Then follows $n$ lines, each containing integers $r_i$, $s_i$, $x_i$, $a_i$ ($1 \le r_i \le s_i \le 10^9$, $1 \le x_i \le i$, $0 \le a_i \le 10^9$), space separated. Note that $p_i$ is given in the form of a fraction $\frac{r_i}{s_i}$. The next $q$ lines are $q$ queries. Each of these queries are two space-separated integers $l$ and $r$ ($1 \le l < r \le n + 1$). The sum of $n$ and sum of $q$ from all $t$ test cases both does not exceed $10^6$.

Output

For each query, output answer in the fraction form modulo $10^9+7$, that is, if the answer is $\frac{P}{Q}$, you should output $P \cdot Q^{-1}$ modulo $10^9+7$, where $Q^{-1}$ denotes the multiplicative inverse of $Q$ modulo $10^9+7$.

Sample Input

1

3 2

1 1 1 2

1 2 1 3

1 3 3 4

1 4

3 4

Sample Output

22

12

Hint

Huge IO (Over 40MB)! IO optimization is preferred.

Source

2019 Multi-University Training Contest 7