31735번 - Escape Route 2 서브태스크다국어

The IOI Kingdom consists of $N$ cities lined up from west to east, with cities numbered from $1$ to $N$ in order from west.

In the IOI Kingdom, they use Byou as the unit of time. A day in the IOI Kingdom is divided into $T$ units of time. The moment $x$ Byous ($0 ≤ x < T$) after the beginning of a day is called time $x$. Therefore, when $1$ Byou passes from time $T - 1$ of a certain day, it becomes time $0$ of the next day.

JOI Group is one of the secret sects in the IOI Kingdom. Since it is a secrect sect, members must navigate around the country’s checkpoints. Consequently, JOI Group members are restricted to using only flights operated by JOY Airlines for intercity travel.

JOY Airlines operate $M_i$ flights departing from city $i$ ($1 ≤ i ≤ N - 1$). The $j$-th flight ($1 ≤ j ≤ M_i$) departs from city $i$ at time $A_{i, j}$ every day 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 allow convenient transfers, and it is also possible to depart from a city immediately upon arrival or stay overnight at the company’s airports.

The JOI Group has $Q$ members, numbered from $1$ to $Q$. Member $k$ ($1 ≤ k ≤ Q$) places their operational base in city $L_k$ and their living base in city $R_k$. Therefore, they want to know the minimum time required to travel from city $L_k$ to city $R_k$ by selecting the departure time from city $L_k$ and flights to use appropriately.

Given information about the flights operated by JOY Airlines and the members of the JOI Group, create a program to find the minimum time required for each member $k$ to travel from city $L_k$ to city $R_k$.

Read the following data from the standard input.

$N$ $T$

$M_1$

$A_{1,1}$ $B_{1,1}$

$A_{1,2}$ $B_{1,2}$

$\vdots$

$A_{1,M_1}$ $B_{1,M_1}$

$M_2$

$A_{2,1}$ $B_{2,1}$

$A_{2,2}$ $B_{2,2}$

$\vdots$

$A_{2,M_2}$ $B_{2,M_2}$

$\vdots$

$M_{N-1}$

$A_{N-1,1}$ $B_{N-1,1}$

$A_{N-1,2}$ $B_{N-1,2}$

$\vdots$

$A_{N-1,M_{N-1}}$ $B_{N-1,M_{N-1}}$

$Q$

$L_1$ $R_1$

$L_2$ $R_2$

$\vdots$

$L_Q$ $R_Q$

Output $Q$ lines to the standard output. On the $k$-th line ($1 ≤ k ≤ Q$), output the minimum time required for the member $k$ to travel from city $L_k$ to city $R_k$.

• $2 ≤ N ≤ 100\, 000$.
• $2 ≤ T ≤ 10^9$.
• $M_i ≥ 1$ ($1 ≤ i ≤ N - 1$).
• $M_1 + M_2 + \cdots + M_{N-1} ≤ 100\, 000$.
• $0 ≤ A_{i, j} < B_{i, j} < T$ ($1 ≤ i ≤ N - 1$, $1 ≤ j ≤ M_i$).
• $1 ≤ Q ≤ 300\, 000$.
• $1 ≤ L_k < R_k ≤ N$ ($1 ≤ k ≤ Q$).
• Given values are all integers.