{"problem":{"name":"[JOIST 2024] 逃生路线 2 / Escape Route 2","description":{"content":"IOI 王国由从西向东排列的 $N$ 座城市组成，城市按照从西向东的顺序从 $1$ 到 $N$ 编号。 在 IOI 王国，他们使用 Byou 作为时间单位。IOI 王国的一天被分为 $T$ 个时间单位。从某一天开始后的 $x$ 个 Byous（$0 \\leq x < T$）被称为时间 $x$。因此，当从某一天的时间 $T - 1$ 开始经过 $1$ 个 Byou 时，将成为下一天的时间 $0$。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10439"},"statements":[{"statement_type":"Markdown","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$ 的最短时间。\n\n## Input\n\n从标准输入中读取以下数据。\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\n## Output\n\n输出 $Q$ 行到标准输出。在第 $k$ 行（$1 \\leq k \\leq Q$），输出成员 $k$ 从城市 $L_k$ 到城市 $R_k$ 所需的最短时间。\n\n[samples]\n\n## Note\n\n#### 样例解释 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#### 样例解释 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 分) 无额外约束条件。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10439","tags":["2024","JOISC/JOIST（日本）"],"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"]],"created_at":"2026-03-03 11:09:25"}}