Problem Description

The Kingdom of IOI consists of \( N \) cities arranged from west to east, numbered from 1 to \( N \) in order from west to east.

In the Kingdom of IOI, they use Byou as the unit of time. A day in the kingdom is divided into \( T \) time units. The time \( x \) (where \( 0 \leq x < T \)) after the start of a day is referred to as time \( x \). Therefore, when 1 Byou passes after time \( T - 1 \) of a day, it becomes time 0 of the next day.

The JOI organization is one of the secret sects in the Kingdom of IOI. Being a secret sect, its members must bypass checkpoints in the country. Thus, members of the JOI organization can only travel between cities using flights operated by JOY Airlines.

JOY Airlines offers \( M_i \) flights in city \( i \) (where \( 1 \leq i \leq N - 1 \)). The \( j \)-th flight (where \( 1 \leq j \leq M_i \)) departs from city \( i \) at time \( A_{i,j} \) and arrives at city \( i + 1 \) at time \( B_{i,j} \) on the same day. Here, \( A_{i,j} < B_{i,j} \).

These flights provide convenient transfer services, allowing immediate departures upon arrival or overnight stays at the company's airports.

The JOI organization has \( Q \) members, numbered from 1 to \( Q \). Member \( k \) (where \( 1 \leq k \leq Q \)) has their operational base in city \( L_k \) and their living base in city \( R_k \). Therefore, they want to know the shortest time to travel from city \( L_k \) to city \( R_k \) by choosing the appropriate departure time from city \( L_k \) and suitable flights.

Given the flights operated by JOY Airlines and the information about the members of the JOI organization, write a program to find the shortest time for each member \( k \) to travel from city \( L_k \) to city \( R_k \).

Input Format

The input is read from the standard input and contains the following data:

• \( N \) \( T \)
• \( M_1 \)
• \( A_{1,1} \) \( B_{1,1} \)
• \( A_{1,2} \) \( B_{1,2} \)
• ...
• \( A_{1,M_1} \) \( B_{1,M_1} \)
• \( M_2 \)
• \( A_{2,1} \) \( B_{2,1} \)
• \( A_{2,2} \) \( B_{2,2} \)
• ...
• \( A_{2,M_2} \) \( B_{2,M_2} \)
• ...
• \( M_{N-1} \)
• \( A_{N-1,1} \) \( B_{N-1,1} \)
• \( A_{N-1,2} \) \( B_{N-1,2} \)
• ...
• \( A_{N-1,M_{N-1}} \) \( B_{N-1,M_{N-1}} \)
• \( Q \)
• \( L_1 \) \( R_1 \)
• \( L_2 \) \( R_2 \)
• ...
• \( L_Q \) \( R_Q \)

Output Format

Output \( Q \) lines to the standard output. On the \( k \)-th line (where \( 1 \leq k \leq Q \)), output the shortest time required for member \( k \) to travel from city \( L_k \) to city \( R_k \).

Sample Input and Output

Sample Input #1

4 10000
1
100 300
2
200 400
300 600
1
500 600
3
1 3
2 4
1 4

Sample Output #1

500
400
10500

Sample Input #2

6 10000
1
100 300
1
400 700
1
500 600
1
300 900
1
200 800
1
1 6

Sample Output #2

30700

Notes/Hints

Sample Explanation 1

As a demonstration, let's refer to the day on which member \( k \) departs from city \( L_k \) as day 1. Member 1 can travel from city 1 to city 3 in 500 Byou by following these actions:

1. Depart from city 1 at time 100 on day 1 and arrive at city 2 at time 300 on day 1.
2. Depart from city 2 at time 300 on day 1 and arrive at city 3 at time 600 on day 1.

Since there is no faster way to travel, output 500 on the first line.

Member 2 can travel from city 2 to city 4 in 400 Byou by following these actions:

1. Depart from city 2 at time 200 on day 1 and arrive at city 3 at time 400 on day 1.
2. Depart from city 3 at time 500 on day 1 and arrive at city 4 at time 600 on day 1.

Since there is no faster way to travel, output 400 on the second line.

Member 3 can travel from city 1 to city 4 in 10500 Byou by following these actions:

1. Depart from city 1 at time 100 on day 1 and arrive at city 2 at time 300 on day 1.
2. Depart from city 2 at time 300 on day 1 and arrive at city 3 at time 600 on day 1.
3. Depart from city 3 at time 500 on day 2 and arrive at city 4 at time 600 on day 2.

Since there is no faster way to travel, output 10500 on the third line.

This sample input satisfies the constraints of subtasks 2, 4, 5, and 6.

Sample Explanation 2

This sample input satisfies the constraints of all subtasks.

Constraints

• \( 2 \leq N \leq 100,000 \)
• \( 2 \leq T \leq 10^9 \)
• \( M_i \geq 1 \) (where \( 1 \leq i \leq N - 1 \))
• \( M_1 + M_2 + \cdots + M_{N-1} \leq 100,000 \)
• \( 0 \leq A_{i,j} < B_{i,j} < T \) (where \( 1 \leq i \leq N - 1, 1 \leq j \leq M_i \))
• \( 1 \leq Q \leq 300,000 \)
• \( 1 \leq L_k < R_k \leq N \) (where \( 1 \leq k \leq Q \))
• All given values are integers.

Subtasks

1. (6 points) \( N \leq 2,000 \), \( M_i = 1 \) (where \( 1 \leq i \leq N - 1 \))
2. (8 points) \( N \leq 2,000 \), \( M_i \leq 5 \) (where \( 1 \leq i \leq N - 1 \))
3. (17 points) \( M_i = 1 \) (where \( 1 \leq i \leq N - 1 \))
4. (23 points) \( M_i \leq 5 \) (where \( 1 \leq i \leq N - 1 \))
5. (36 points) \( N \leq 90,000 \), \( Q \leq 90,000 \), \( M_1 + M_2 + \cdots + M_{N-1} \leq 90,000 \)
6. (10 points) No additional constraints.

见题面 Input 部分

见题面 Output 部分