{"raw_statement":[{"iden":"statement","content":"IOI 王国由从西向东排列的 $N$ 座城市组成，城市按照从西向东的顺序从 $1$ 到 $N$ 编号。\n\n在 IOI 王国，他们使用 Byou 作为时间单位。IOI 王国的一天被分为 $T$ 个时间单位。从某一天开始后的 $x$ 个 Byous（$0 \\leq x < T$）被称为时间 $x$。因此，当从某一天的时间 $T - 1$ 开始经过 $1$ 个 Byou 时，将成为下一天的时间 $0$。\n\nJOI 组织是 IOI 王国的秘密教派之一。由于它是一个秘密教派，成员必须绕过国家的检查站。因此，JOI 组织成员只能使用 JOY 航空公司运营的航班进行城市间旅行。\n\nJOY 航空公司在城市 $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}$。\n\n这些航班提供了便捷的转机服务，也可以在抵达后立即起飞或在公司的机场过夜。\n\nJOI 组织有 $Q$ 名成员，编号从 $1$ 到 $Q$。成员 $k$（$1 \\leq k \\leq Q$）将他们的运营基地设在城市 $L_k$，生活基地设在城市 $R_k$。因此，他们想知道通过选择从城市 $L_k$ 出发的时间和适当的航班进行，从城市 $L_k$ 出发到城市 $R_k$ 的最短时间。\n\n给定 JOY 航空公司运营的航班和 JOI 组织成员的信息，编写一个程序，找到每个成员 $k$ 从城市 $L_k$ 到城市 $R_k$ 的最短时间。"},{"iden":"input","content":"从标准输入中读取以下数据。\n\n- $N$ $T$\n- $M_1$\n- $A_{1,1}$ $B_{1,1}$\n- $A_{1,2}$ $B_{1,2}$\n- ...\n- $A_{1,M_1}$ $B_{1,M_1}$\n- $M_2$\n- $A_{2,1}$ $B_{2,1}$\n- $A_{2,2}$ $B_{2,2}$\n- ...\n- $A_{2,M_2}$ $B_{2,M_2}$\n- ...\n- $M_{N-1}$\n- $A_{N-1,1}$ $B_{N-1,1}$\n- $A_{N-1,2}$ $B_{N-1,2}$\n- ...\n- $A_{N-1,M_{N-1}}$ $B_{N-1,M_{N-1}}$\n- $Q$\n- $L_1$ $R_1$\n- $L_2$ $R_2$\n- ...\n- $L_Q$ $R_Q$\n"},{"iden":"output","content":"输出 $Q$ 行到标准输出。在第 $k$ 行（$1 \\leq k \\leq Q$），输出成员 $k$ 从城市 $L_k$ 到城市 $R_k$ 所需的最短时间。\n"},{"iden":"note","content":"#### 样例解释 1\n\n作为演示，让我们将成员 $k$ 从城市 $L_k$ 出发的第一天称为第 $1$ 天。成员 $1$ 可以按照以下行动在 $500$ Byou 内从城市 $1$ 前往城市 $3$：\n\n1. 第 $1$ 天时刻 $100$ 从城市 $1$ 出发，并在第 $1$ 天时刻 $300$ 到达城市 $2$。\n2. 第 $1$ 天时刻 $300$ 从城市 $2$ 出发，并在第 $1$ 天时刻 $600$ 到达城市 $3$。\n\n由于没有更快的旅行方式，所以在第 $1$ 行输出 $500$。\n\n成员 $2$ 可以按照以下行动在 $400$ Byou 内从城市 $2$ 前往城市 $4$：\n\n1. 第 $1$ 天时刻 $200$ 从城市 $2$ 出发，并在第 $1$ 天时刻 $400$ 到达城市 $3$。\n2. 第 $1$ 天时刻 $500$ 从城市 $3$ 出发，并在第 $1$ 天时刻 $600$ 到达城市 $4$。\n\n由于没有更快的旅行方式，所以在第 $2$ 行输出 $400$。\n\n成员 $3$ 可以按照以下行动在 $10500$ Byou 内从城市 $1$ 前往城市 $4$：\n\n1. 第 $1$ 天时刻 $100$ 从城市 $1$ 出发，并在第 $1$ 天时刻 $300$ 到达城市 $2$。\n2. 第 $1$ 天时刻 $300$ 从城市 $2$ 出发，并在第 $1$ 天时刻 $600$ 到达城市 $3$。\n3. 第 $2$ 天时刻 $500$ 从城市 $3$ 出发，并在第 $2$ 天时刻 $600$ 到达城市 $4$。\n\n由于没有更快的旅行方式，所以在第 $3$ 行输出 $10500$。\n\n这个样例输入满足子任务 $2,4,5,6$ 的限制条件。\n\n\n#### 样例解释 2\n\n这个样例输入满足所有子任务的约束条件。\n\n### 约束条件\n\n- $2 \\leq N \\leq 100,000$\n- $2 \\leq T \\leq 10^9$\n- $M_i \\geq 1$（$1 \\leq i \\leq N - 1$）\n- $M_1 + M_2 + \\cdots + M_{N-1} \\leq 100,000$\n- $0 \\leq A_{i,j} < B_{i,j} < T$（$1 \\leq i \\leq N - 1, 1 \\leq j \\leq M_i$）\n- $1 \\leq Q \\leq 300,000$\n- $1 \\leq L_k < R_k \\leq N$（$1 \\leq k \\leq Q$）\n- 给定值均为整数。\n\n### 子任务\n\n1. (6 分) $N \\leq 2,000$，$M_i = 1$（$1 \\leq i \\leq N - 1$）\n2. (8 分) $N \\leq 2,000$，$M_i \\leq 5$（$1 \\leq i \\leq N - 1$）\n3. (17 分) $M_i = 1$（$1 \\leq i \\leq N - 1$）\n4. (23 分) $M_i \\leq 5$（$1 \\leq i \\leq N - 1$）\n5. (36 分) $N \\leq 90,000$，$Q \\leq 90,000$，$M_1 + M_2 + \\cdots + M_{N-1} \\leq 90,000$\n6. (10 分) 无额外约束条件。"}],"translated_statement":null,"sample_group":[["4 10000\n1\n100 300\n2\n200 400\n300 600\n1\n500 600\n3\n1 3\n2 4\n1 4","500\n400\n10500"],["6 10000\n1\n100 300\n1\n400 700\n1\n500 600\n1\n300 900\n1\n200 800\n1\n1 6\n","30700"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}