Problem Description

The IOI Kingdom consists of $N$ cities arranged from west to east. The cities are numbered from $1$ to $N$ in order from west to east.

In the IOI Kingdom, they use Byou as the unit of time. One day in the IOI Kingdom is divided into $T$ time units. The time $x$ Byous ($0 \leq x < T$) after the start of some day is called time $x$. Therefore, when $1$ Byou passes starting from time $T - 1$ of some day, it becomes time $0$ of the next day.

The JOI Organization is one of the secret cults in the IOI Kingdom. Since it is a secret cult, its members must bypass the kingdom’s checkpoints. Therefore, JOI Organization members can only travel between cities using flights operated by JOY Airlines.

JOY Airlines offers $M_i$ flights in city $i$ ($1 \leq i \leq N - 1$). Flight $j$ ($1 \leq j \leq M_i$) departs from city $i$ every day 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}$ holds.

These flights provide convenient connections: you may depart immediately after arriving, or stay overnight at the airline’s airport.

The JOI Organization has $Q$ members, numbered from $1$ to $Q$. Member $k$ ($1 \leq k \leq Q$) has their operation base in city $L_k$ and their living base in city $R_k$. Therefore, they want to know the shortest time needed to travel from city $L_k$ to city $R_k$, by choosing a departure time from city $L_k$ and taking suitable flights.

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

Input Format

Read the following data from standard input.

• $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 standard output. On line $k$ ($1 \leq k \leq Q$), output the shortest time required for member $k$ to travel from city $L_k$ to city $R_k$.

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

500
400
10500

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

30700

Hint

Sample Explanation 1

For demonstration, let us call the first day on which member $k$ departs from city $L_k$ Day $1$. Member $1$ can travel from city $1$ to city $3$ in $500$ Byou as follows.

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

Member $2$ can travel from city $2$ to city $4$ in $400$ Byou as follows.

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

Member $3$ can travel from city $1$ to city $4$ in $10500$ Byou as follows.

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

This sample input satisfies the constraints for Subtasks $2,4,5,6$.

Sample Explanation 2

This sample input satisfies the constraints for all subtasks.

Constraints

• $2 \leq N \leq 100,000$
• $2 \leq T \leq 10^9$
• $M_i \geq 1$ ($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$ ($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$ ($1 \leq k \leq Q$)
• All given values are integers.

Subtasks

1. (6 points) $N \leq 2,000$, $M_i = 1$ ($1 \leq i \leq N - 1$).
2. (8 points) $N \leq 2,000$, $M_i \leq 5$ ($1 \leq i \leq N - 1$).
3. (17 points) $M_i = 1$ ($1 \leq i \leq N - 1$).
4. (23 points) $M_i \leq 5$ ($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.

Translated by ChatGPT 5