题目描述

题目译自 JOISC 2024 Day4 T1 「逃走経路 2 / Escape Route 2」

IOI 国由 $N$ 个城市组成，这些城市自西向东排成一行，并从西开始编号为 $1$ 到 $N$。

IOI 国的一天被分为 $T$ 秒。在一天开始后的 $x$ $(0 \le x < T)$ 秒后被称为时刻 $x$。因此，当某天的时刻 $T-1$ 过去一秒后，就变成了下一天的时刻 $0$。

秘密结社 JOI 团是 IOI 国中的一个暗中活动的组织。因为它是一个秘密结社，其成员必须绕开国家的检查点。因此 JOI 团的成员必须通过 JOY 航空的航班来进行城际旅行。

JOY 航空有 $M_i$ 架航班从城市 $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$ 出发，通过选择合适的航班到达 $R_k$ 的最小所需时间。

给定 JOY 航空的航班和 JOI 团成员的信息，写一个程序求出成员 $k$ 从 $L_k$ 到 $R_k$ 的最小用时。

输入格式

第一行两个整数 $N$, $T$。

接下来 $N-1$ 块数据，描述 $N-1$ 个城市的航班。对于每块数据，第一行一个整数 $M_i$，接下来 $M_i$ 行，每行两个整数 $A_{i,j}$, $B_{i,j}$。

接下来一行一个整数 $Q$。

接下来 $Q$ 行，每行两个整数 $L_k$, $R_k$。

输出格式

输出 $Q$ 行，第 $k$ $(1 \le k \le Q)$ 行输出从城市 $L_k$ 到 $R_k$ 的最小用时。

样例1：

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

500
400
10500

为了方便描述，我们令成员 $k$ 从城市 $L_k$ 出发的日子为第一天。

成员 $1$ 可以从城市 $1$ 花 $500$ 秒到城市 $3$： 在第一天的时刻 $100$ 从城市 $1$ 出发，在第一天的时刻 $300$ 到城市 $2$。 在第一天的时刻 $300$ 从城市 $2$ 出发，在第一天的时刻 $600$ 到城市 $3$。 因为没有更快的方式，所以第一行输出 $500$。

成员 $2$ 可以从城市 $2$ 花 $400$ 秒到城市 $4$： 在第一天的时刻 $200$ 从城市 $2$ 出发，在第一天的时刻 $400$ 到城市 $3$。 在第一天的时刻 $500$ 从城市 $3$ 出发，在第一天的时刻 $600$ 到城市 $4$。 因为没有更快的方式，所以第二行输出 $400$。

成员 $3$ 可以从城市 $1$ 花 $10500$ 秒到城市 $4$： 在第一天的时刻 $100$ 从城市 $1$ 出发，在第一天的时刻 $300$ 到城市 $2$。 在第一天的时刻 $300$ 从城市 $2$ 出发，在第一天的时刻 $600$ 到城市 $3$。 在第二天的时刻 $500$ 从城市 $3$ 出发，在第二天的时刻 $600$ 到城市 $4$。 因为没有更快的方式，所以第三行输出 $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

30700

这组样例满足所有子任务的限制。

数据规模与约定

$2 \le N \le 10^5$

$2 \le T \le 10^9$

$M_i \ge 1$ $(1 \le i \le N-1)$

$M_1 + M_2 + \ldots + M_{N-1} \le 10^5$

$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 3 \times 10^5$

$1 \le L_k < R_k \le N$ $(1 \le k \le Q)$

详细子任务附加限制及分值如下表所示。

$子任务编号$	$附加限制$	$分值$
$1$	$N \le 2,000$, $M_i = 1$ $(1 \le i \le N-1)$	$6$
$2$	$N \le 2,000$, $M_i \le 5$ $(1 \le i \le N-1)$	$8$
$3$	$M_i = 1$ $(1 \le i \le N-1)$	$17$
$4$	$M_i \le 5$ $(1 \le i \le N-1)$	$23$
$5$	$N, Q \le 90,000$, $M_1 + \ldots + M_{N-1} \le 90,000$	$36$
$6$	$无附加限制$	$10$