数轴上有 n 个区间 [l_i,r_i]，满足 l_1 < l_2 <\cdots < l_n，r_1 < r_2 <\cdots < r_n。考虑构造一张无向图，顶点分别代表这 n 个区间，两点间连边当且仅当对应区间相交。在这些区间中，有一些区间是特别的，开始时给定每个区间是否是特别的。接下来你需要回答 q 次询问，每次询问给定两个区间，你需要回答出：
这两个区间对应图上顶点之间的最短路长度；
有多少个特别区间，其对应图上顶点出现在这两点至少一条最短路上。
保证 n,q\leq 2\times 10^5。
Problem B
游戏中有 n 个据点，你需要在这些据点刷一些金币。一开始的时候，每个据点什么都没有。在接下来的时间内，据点 i 会以每秒 m_i 个金币的速度产生金币。据点之间有若干单向道路，第 i 条道路从 a_i 出发到达 b_i，你需要花费 t_i 秒的时间通行。你可以从任意据点开始，每次经过某个据点时可以获取它之前产生的所有金币。这里认为获取金币的过程不耗费时间。
你需要回答 q 次询问，每次询问给定一个时间节点 s 以及一个终止据点 e。你需要计算：
如果你的采集金币时间只有 s 秒，且在这 s 秒结束后必须位于据点 e 以开启后续关卡，那么这 s 秒时间内你最多能获得多少金币？
注意到，对两个区间 X,Y，假设 X 在 Y 左侧，那么从 X 出发到达 Y 时，为了使路程最短，我们每次一定会选取当前能走到的区间中最右边的那个。我们可以对每个区间预处理出它向右最优能走到的那个区间，并在两个区间之间连一条有向边，这样会形成一棵有根树的结构；然后做树上倍增就可以在单次 O(\log n) 的时间内回答两点间的最短路了，也就解决了第一个问题。
接下来解决第二个问题。方便起见先暂定全部的区间都是特别的。显见区间 Z 出现在 X,Y 的至少一条最短路上意味着 Z 一定位于 X,Y 中间，且 \mathrm{dis}(X,Z)+\mathrm{dis}(Z,Y)=\mathrm{dis}(X,Y)。令 k=\mathrm{dis}(X,Y)，对每个 c=0,...,k，我们希望统计满足 \mathrm{dis}(X,Z)=c,\mathrm{dis}(Z,Y)=k-c 的区间 Z 的数量。不妨设 X 向右走 c-1 步、c 步分别最远能走到的区间编号为 r_{c-1},r_c，Y 向左走 k-c-1 步、k-c 步分别最远能走到的区间编号为 l_{c-1},l_c，那么我们待求的区间 Z 的编号取值就是 (r_{c-1},r_c] 和 [l_c,l_{c-1}) 的交集。注意到：
这个区间的并集一定不空。这是因为最短路一定存在，那么这条最短路上的第 c 个区间是一个符合条件的 Z。
倒着考虑这个过程：我们从 e 开始，在 s 秒内不断游走，每次走到一个点该点就会被控制，之后我们可以不断获取该点产出的金币；需要最大化获得的总金币数。
对一个最后被控制的点，我们定义其 损失量 为在我们走到该点之前该点产出的金币总量。假设我们最后控制的点集为 S，设 S 中产出金币的总速度为 v，损失量的总和为 k，此时消耗的时间为 t。那么需要满足 t\leq s，且此时我们得到的金币总量即为 vs-k。对固定的 S，v 也是固定的；我们希望最小化 k 的值。考虑通过状压 DP 计算出对每个 S，k 能取到的最小可能值；这样，我们每次在所有的 S 中，取 vs-k 最大的即可。
在设计状态时，值得考虑的是：需不需要把 t 算进状态里？我们发现，如果 t 需要进入状态，那么状态总数可能是无法承受的；但要是不算，又有 t\leq s 的限制。幸运的是，如果 t > s，那么说明我们还有某个点是没有访问到的，并且我们提前计算了这个点产生的损失量；如果我们把这个点去掉（也就是缩小 S），一定可以找到一组更优解。这说明 t > s 的时候我们就算计算到了，它也不会影响答案。
我们的 DP 便出来了：对每个点集 S 和顶点 u,v\in S，记 f(u,v,S) 为从 u 开始游走，在 v 结束游走，经过了 S 中全部节点，能达到的损失量的最小值。如果考虑每次在 v 端添加一个节点，转移会很困难，因为贡献涉及到总共消耗的时间；我们考虑在 u 端添加一个节点，这样贡献就是这条边的边权乘上点集内所有点的产出速度和。也就是：