L. Increments
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There is an array $$$a$$$ of size $$$10^9$$$, initially all containing zeroes. There are $$$n$$$ operations done to the array.

The $$$i$$$-th operation specifies operation number $$$op_i$$$ and bounds $$$l_i \le r_i$$$.

  • If $$$op_i=1$$$, then $$$a_l,a_{l+1},\ldots,a_r$$$ will all be incremented by $$$1$$$.
  • If $$$op_i=2$$$, then $$$a_l,a_{l+1},\ldots,a_r$$$ will be incremented by $$$1,2,\ldots,r-l+1$$$ respectively.

After all operations, there are $$$q$$$ queries. The $$$j$$$-th query specifies bounds $$$L_j\le R_j$$$, and you have to determine the sum $$$a_{L_j}+a_{L_j+1}+\ldots+a_{R_j}$$$ modulo $$$10^9+7$$$.

Input

The first line contains an integer $$$n$$$ ($$$1\le n\le 10^6$$$).

The $$$i$$$-th of the next $$$n$$$ lines contains three integers $$$op_i$$$, $$$l_i$$$, and $$$r_i$$$ ($$$1\le op_i\le 2$$$, $$$1\le l_i \le r_i\le 10^9$$$).

The next line contains an integer $$$q$$$ ($$$1\le q\le 10^6$$$).

The $$$j$$$-th of the next $$$q$$$ lines contains two integers $$$L_j$$$ and $$$R_j$$$ ($$$1\le L_j\le R_j\le 10^9$$$).

—

Tests in subtasks are numbered from $$$1-20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Test $$$1$$$ satisfies $$$op_i=1$$$, $$$l_i=r_i \le 10^6$$$, and $$$R_j \le 10^6$$$.

Test $$$2$$$ satisfies $$$op_i=1$$$, $$$r_i \le 10^6$$$, and $$$L_j=R_j \le 10^6$$$.

Tests $$$3-4$$$ satisfy $$$op_i=1$$$, $$$r_i \le 10^6$$$, and $$$R_j \le 10^6$$$.

Tests $$$5-6$$$ satisfy $$$r_i \le 10^6$$$, and $$$L_j=R_j \le 10^6$$$.

Tests $$$7-8$$$ satisfy $$$r_i \le 10^6$$$, and $$$R_j \le 10^6$$$.

Tests $$$9-10$$$ satisfy $$$op_i=1$$$ and $$$l_i=r_i$$$.

Tests $$$11-12$$$ satisfy $$$op_i=1$$$ and $$$L_j=R_j$$$.

Tests $$$13-15$$$ satisfy $$$op_i=1$$$.

Tests $$$16-17$$$ satisfy $$$L_j=R_j$$$.

Tests $$$18-20$$$ satisfy no additional constraints.

Output

For the $$$j$$$-th query, output the sum $$$a_{L_j}+a_{L_j+1}+\ldots+a_{R_j}$$$ modulo $$$10^9+7$$$ on a separate line.

Example
Input
3
1 1 3
2 2 4
2 1 5
3
1 3
2 4
1 5
Output
12
17
24
Note

Since the input size might be large, please add ios_base::sync_with_stdio(0); cin.tie(0); to the start of the main function.

—

Problem Idea: culver0412

Problem Preparation: culver0412

Occurrences: Novice K, Advanced H