在数轴上有 个闭区间 。现在要从中选出 个区间，使得这 个区间共同包含至少一个位置。换句话说，就是使得存在一个 ，使得对于每一个被选中的区间 ，都有 。

对于一个合法的选取方案，它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 的长度定义为 ，即等于它的右端点的值减去左端点的值。

求所有合法方案中最小的花费。

森林中有 个点， 条边，每个点有点权，执行 次操作：

1. 查询两点间点权的第 小；
2. 连接两个点，保证图在操作后仍然为森林。

一个有向图 称为半连通的（Semi-Connected），如果满足：

，满足 或 ，即对于图中任意两点 ，，存在一条 到 的有向路径或者从 到 的有向路径。

若 满足 ， 是 中所有跟 有关的边，则称 是 的一个导出子图。 若 是 的导出子图，且 半连通，则称 为 的半连通子图。 若 是 所有半连通子图中包含节点数最多的，则称 是 的最大半连通子图。

给定一个有向图 ，请求出 的最大半连通子图拥有的节点数 ，以及不同的最大半连通子图的数目 。由于 可能比较大，仅要求输出 对 的余数。

程设老师最近要进行一项邪恶的实验，这个实验一共持续 天，第 天需要 个研究生来给他搬砖。研究生毕竟也是人，所以雇佣研究生是需要钱的，机智的程设老师已经联系好了 所大学，第 所大学共有 个研究生，同时雇佣这所大学的一个研究生需要 元钱。

一天下来给他搬砖的所有研究生都会进入濒死状态。濒死状态的研究生，毫无疑问，就不能再进行工作了。但是机智的老师早早联系好了 家医院，第 家医院医治一个濒死的研究生需要 天，并且需要 元钱。

在一个 行 列的网格地图中有一些高度不同的石柱，一些石柱上站着一些蜥蜴，你的任务是让尽量多的蜥蜴逃到边界外。

每行每列中相邻石柱的距离为 ，蜥蜴的跳跃距离是 ，即蜥蜴可以跳到平面曼哈顿距离不超过 的任何一个石柱上。

石柱都不稳定，每次当蜥蜴跳跃时，所离开的石柱高度减 （如果仍然落在地图内部，则到达的石柱高度不变），如果该石柱原来高度为 ，则蜥蜴离开后消失。以后其他蜥蜴不能落脚。

任何时刻不能有两只蜥蜴在同一个石柱上。

给一棵树，每个点有其初始颜色和权值，每次修改一个点的颜色或权值，查询路径上颜色与起点相同点权值的和或最大值。

受校门外的树这道经典问题的启发，A 君根据基本的离散数学的知识，抽象出 种运算维护集合 （初始为空）并最终输出 。现在，请你完成这道校门外的树之难度增强版 —— 校门外的区间。

种运算如下：

1. ；

高一结束了，作为 OIer 的生活过去一半了，NOI 也是一个多月之前的事了，在这期间一直想着，想要写些什么。一拖再拖，终于拖到了开学前的最后一夜。

魔法森林是一个 个节点 条边的无向图，节点标号为 ，边标号为 。初始时小 E 同学在号节点 ，隐士在节点 。

无向图中的每一条边 包含两个权值 与 。若身上携带的 A 型守护精灵个数不少于 ，且 B 型守护精灵个数不少于 ，这条边上的妖怪就发起攻击。

小 E 想要知道，要能够成功拜访到隐士，最少需要携带守护精灵的总个数。

对于字符串 的前 个字符构成的子串，既是它的后缀同时又是它的前缀，并且该后缀与该前缀不重叠，将这种字符串的数量记作 ，求