Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
 Register new ID

Kejin Player

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 2405    Accepted Submission(s): 1005

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.

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$.

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


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


Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-04-15 23:21:16, Gzip enabled