题目描述

IOI 王国由从西向东排列的 $N$ 座城市组成，城市按照从西向东的顺序从 $1$ 到 $N$ 编号。

在 IOI 王国，他们使用 Byou 作为时间单位。IOI 王国的一天被分为 $T$ 个时间单位。从某一天开始后的 $x$ 个 Byous（$0 \leq x < T$）被称为时间 $x$。因此，当从某一天的时间 $T - 1$ 开始经过 $1$ 个 Byou 时，将成为下一天的时间 $0$。

JOI 组织是 IOI 王国的秘密教派之一。由于它是一个秘密教派，成员必须绕过国家的检查站。因此，JOI 组织成员只能使用 JOY 航空公司运营的航班进行城市间旅行。

JOY 航空公司在城市 $i$（$1 \leq i \leq N - 1$）提供 $M_i$ 趟航班。第 $j$ 趟航班（$1 \leq j \leq M_i$）每天从城市 $i$ 在时间 $A_{i,j}$ 起飞，于当天的时间 $B_{i,j}$ 到达城市 $i + 1$。这里，满足 $A_{i,j} < B_{i,j}$。

这些航班提供了便捷的转机服务，也可以在抵达后立即起飞或在公司的机场过夜。

JOI 组织有 $Q$ 名成员，编号从 $1$ 到 $Q$。成员 $k$（$1 \leq k \leq Q$）将他们的运营基地设在城市 $L_k$，生活基地设在城市 $R_k$。因此，他们想知道通过选择从城市 $L_k$ 出发的时间和适当的航班进行，从城市 $L_k$ 出发到城市 $R_k$ 的最短时间。

给定 JOY 航空公司运营的航班和 JOI 组织成员的信息，编写一个程序，找到每个成员 $k$ 从城市 $L_k$ 到城市 $R_k$ 的最短时间。

输入格式

从标准输入中读取以下数据。

• $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$

输出格式

输出 $Q$ 行到标准输出。在第 $k$ 行（$1 \leq k \leq Q$），输出成员 $k$ 从城市 $L_k$ 到城市 $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

提示

样例解释 1

作为演示，让我们将成员 $k$ 从城市 $L_k$ 出发的第一天称为第 $1$ 天。成员 $1$ 可以按照以下行动在 $500$ Byou 内从城市 $1$ 前往城市 $3$：

1. 第 $1$ 天时刻 $100$ 从城市 $1$ 出发，并在第 $1$ 天时刻 $300$ 到达城市 $2$。
2. 第 $1$ 天时刻 $300$ 从城市 $2$ 出发，并在第 $1$ 天时刻 $600$ 到达城市 $3$。

由于没有更快的旅行方式，所以在第 $1$ 行输出 $500$。

成员 $2$ 可以按照以下行动在 $400$ Byou 内从城市 $2$ 前往城市 $4$：

1. 第 $1$ 天时刻 $200$ 从城市 $2$ 出发，并在第 $1$ 天时刻 $400$ 到达城市 $3$。
2. 第 $1$ 天时刻 $500$ 从城市 $3$ 出发，并在第 $1$ 天时刻 $600$ 到达城市 $4$。

由于没有更快的旅行方式，所以在第 $2$ 行输出 $400$。

成员 $3$ 可以按照以下行动在 $10500$ Byou 内从城市 $1$ 前往城市 $4$：

1. 第 $1$ 天时刻 $100$ 从城市 $1$ 出发，并在第 $1$ 天时刻 $300$ 到达城市 $2$。
2. 第 $1$ 天时刻 $300$ 从城市 $2$ 出发，并在第 $1$ 天时刻 $600$ 到达城市 $3$。
3. 第 $2$ 天时刻 $500$ 从城市 $3$ 出发，并在第 $2$ 天时刻 $600$ 到达城市 $4$。

由于没有更快的旅行方式，所以在第 $3$ 行输出 $10500$。

这个样例输入满足子任务 $2,4,5,6$ 的限制条件。

样例解释 2

这个样例输入满足所有子任务的约束条件。

约束条件

• $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$）
• 给定值均为整数。

子任务

1. (6 分) $N \leq 2,000$，$M_i = 1$（$1 \leq i \leq N - 1$）
2. (8 分) $N \leq 2,000$，$M_i \leq 5$（$1 \leq i \leq N - 1$）
3. (17 分) $M_i = 1$（$1 \leq i \leq N - 1$）
4. (23 分) $M_i \leq 5$（$1 \leq i \leq N - 1$）
5. (36 分) $N \leq 90,000$，$Q \leq 90,000$，$M_1 + M_2 + \cdots + M_{N-1} \leq 90,000$
6. (10 分) 无额外约束条件。