Escape Route 2

The IOI Kingdom has $N$ cities in a row from west to east, numbered from $1$ to $N$ starting from the west.

The IOI Kingdom uses Byou as its unit of time. A day is divided into $T$ units of time. The moment $x$ Byou ($0 \le x < T$) after the start of a day is called time $x$. So when 1 Byou passes from time $T-1$ on some day, it becomes time $0$ the next day.

JOI Group is one of the secret sects in the IOI Kingdom. Members must avoid the country's checkpoints, so they may only use flights operated by JOY Airlines for travel between cities.

JOY Airlines operates $M_i$ flights departing from city $i$ ($1 \le i \le N-1$). The $j$-th flight ($1 \le j \le 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, where $A_{i,j} < B_{i,j}$. These flights allow convenient transfers. A member can also leave a city right after arriving, or stay overnight at the airline's airports.

The JOI Group has $Q$ members, numbered from $1$ to $Q$. Member $k$ ($1 \le k \le Q$) has an operational base in city $L_k$ and a living base in city $R_k$. Each member wants the minimum time needed to travel from $L_k$ to $R_k$, choosing the departure time from $L_k$ and the flights to take.

Given the flight information and the members' bases, write a program that finds, for each member $k$, the minimum time to travel from city $L_k$ to city $R_k$.

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
...
M_{N-1}
...
Q
L_1 R_1
L_2 R_2
...
L_Q R_Q

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

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