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

在 IOI 王国中，他们使用 Byou 作为时间单位。IOI 王国的一天被划分为 $T$ 个时间单位。一天开始后 $x$ Byou 的时刻（$0 \le x < T$）被称为时间 $x$。因此，当从某天的时间 $T - 1$ 过去 $1$ Byou 后，就变成了下一天的时间 $0$。

JOI 集团是 IOI 王国中的一个秘密教派。由于这是一个秘密教派，成员们必须绕过国家的检查站。因此，JOI 集团成员在城市间旅行时仅限于使用 JOY 航空公司运营的航班。

JOY 航空公司运营着从城市 $i$ 出发的 $M_i$ 个航班（$1 \le i \le N - 1$）。第 $j$ 个航班（$1 \le j \le M_i$）每天在时间 $A_{i, j}$ 从城市 $i$ 出发，并在同一天的时间 $B_{i, j}$ 到达城市 $i + 1$。这里满足 $A_{i, j} < B_{i, j}$。这些航班允许便捷的转机，也可以在到达后立即从城市出发，或者在公司的机场过夜。

JOI 集团有 $Q$ 名成员，编号为 $1$ 到 $Q$。成员 $k$（$1 \le k \le 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}$ $\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$

输出格式

向标准输出输出 $Q$ 行。在第 $k$ 行（$1 \le k \le Q$），输出成员 $k$ 从城市 $L_k$ 到城市 $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 + \dots + 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$）
• 输入中的所有值均为整数。

子任务

1. (6 分) $N \le 2\,000, M_i = 1$（$1 \le i \le N - 1$）。
2. (8 分) $N \le 2\,000, M_i \le 5$（$1 \le i \le N - 1$）。
3. (17 分) $M_i = 1$（$1 \le i \le N - 1$）。
4. (23 分) $M_i \le 5$（$1 \le i \le N - 1$）。
5. (36 分) $N \le 90\,000, Q \le 90\,000, M_1 + M_2 + \dots + M_{N-1} \le 90\,000$。
6. (10 分) 无附加限制。

样例

输入格式 1

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

输出格式 1

500
400
10500

说明

作为演示，我们将成员 $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

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

输出格式 2

30700

说明

该样例输入满足所有子任务的限制。