某个国家有 $n$ 个城市，这 $n$ 个点之间的边构成一棵树。

现求一条边长度和不超过 $S$ 的路径（两端都是城市，可以只为一个城市），使得所有城市到这条路径的距离的最大值最小，并输出这个最小值。

小Z有一片森林，含有 $N$ 个节点，每个节点上都有一个非负整数作为权值。初始的时候，森林中有 $M$ 条边。

小Z希望执行 $T$ 个操作，操作有两类：

• Q x y k 查询点 $x$ 到点 $y$ 路径上所有的权值中，第 $k$ 小的权值是多少。此操作保证点 $x$ 和点 $y$ 连通，同时这两个节点的路径上至少有 $k$ 个点。

• L x y 在点 $x$ 和点 $y$ 之间连接一条边。保证完成此操作后，仍然是一片森林。

强制在线。

对于所有的数据 $n,m,T \leq 8 \times 10^4$ 。

$n$ 个布丁摆成一行，每个布丁最开始都有一个颜色 $c_i$ ，进行 $m$ 次操作。

操作格式：

• 1 c d ：将所有的 $c$ 颜色替换为$d$

• 2 ：查询当前布丁序列一共有多少段颜色。例如颜色分别为 $1,2,2,1$ 的四个布丁一共有3段颜色。

游戏一开始，Lostmonkey 在地上沿着一条直线摆上 $n$ 个装置，每个装置设定初始弹力系数 $K_i$ ，当绵羊达到第 $i$ 个装置时，它会往后弹 $K_i$ 步，达到第 $i+K_i$ 个装置，若不存在第 $i+K_i$ 个装置，则绵羊被弹飞。

存在两种操作：

• 查询在第 $i$ 个装置起步时，再经多少次会被弹飞。

• 修改第 $i$ 个装置的弹力系数为 $K’$ 。

保证任何时候，任何装置弹力系数均为正整数。

有一个 $a \times b$ 的整数组成的矩阵，现请你从中找出一个 $n\times n$ 的正方形区域，使得该区域所有数中的最大值和最小值的差最小，输出这个最小的差值。

超级计算机中的任务用三元组 $(S_i,E_i,P_i)$ 描述， $(S_i,E_i,P_i)$ 表示任务运行区间为 $[S_i,E_i]$ ,其优先级为 $P_i$ 。

给出 $n$ 个任务。随后给出 $m$ 个询问，第 $X_i$ 秒正在运行的任务中，优先级最小的 $K_i$ 个任务的优先级之和是多少。特别的，如果 $K_i$ 大于第 $X_i$ 秒正在运行的任务总数，则直接回答第 $X_i$ 秒正在运行的任务优先级之和。

强制在线。

辉辉热衷于洞穴勘测。

辉辉有一台监测仪器可以实时将通道的每一次改变状况，并在辉辉手边的终端机上显示：

Connect u v代表监测到洞穴u和洞穴v之间出现了一条通道，Destroy u v代表监测到洞穴u和洞穴v之间的通道被毁。Query u v，代表向监测仪询问此时洞穴u和洞穴v是否连通。

保证无论通道怎么改变，任意时刻任意两个洞穴之间至多只有一条路径。

已知在第一条指令显示之前，洞穴群中没有任何通道存在。

给定一个含有 $n$ 个数的序列 ${a_n}$ ，回答询问或执行操作：

• Q i j k （$1\leq i\leq j\leq n, 1\leq k\leq j-i+1$）表示询问$a[i],a[i+1]……a[j]$中第 $k$ 小的数。

• C i t ($1 \leq i \leq n,0\leq t \leq 10^{9}$)表示把 $a[i]$ 改变成为 $t$ 。

定义一棵树上最长的路径为树的直径。树的直径可能不唯一。

给定的一棵 $n$ 个结点的树，求其直径的长度，以及有多少条边满足所有的直径都经过该边。

给一个数列 ${a_n}$ ，每次询问区间 $[l,r]$ 内有没有一个数出现次数超过一半。如果有，输出这个数，如果没有，输出 $0$ 。

美食节共有 $n$ 种不同的菜品，每个同学都点了一份在这 $n$ 个菜品中的菜。总共有 $m$ 个厨师来制作这些菜品。厨师们会按照要求的顺序进行制作，并且每次只能制作一人份。第 $j$ 个厨师制作第 $i$ 种菜品的时间记为 $t _ {i,j}$ 。每个同学的等待时间为所有厨师开始做菜起，到自己那份菜品完成为止的时间总长度。总等待时间为所有同学的等待时间之和。

已知共有 $n$ 种菜品，第 $i$ 种菜品需要做 $p_i$ 份，共有 $m$ 个厨师。请计算出最小的总等待时间是多少。

给定 $n$ 个结点的数据值 $V_i$ ，权值 $P_i$ ，访问频度 $T_i(T_i \geq 0)$ 。对于 $\forall i,j \in V$ 且 $i \neq j$ ，有 $V_i \neq V_j, P_i \neq P_j$ 。

现令这 $n$ 个点组成一颗二叉树，且满足 $\forall , i \in V$ ，若 $p$ 为 $i$ 的左子节点， $q$ 为 $i$ 的右子节点，则 $V_p < V_i < V_q$ 且 $P_i < P_p,; P_i < P_q$ 。可以证明，这样的二叉树是唯一的。点$i$ 在树中的深度 $D_i$ 定义为它到根的距离加 $1$ 。定义结点 $i$ 的访问代价 $E_i = T_i \times D_i$ 。可以修改每个点的权值为任意实数，其代价均为给定的正整数 $K$ ，但需保证任两点权值仍互不相同。

现求上文所述二叉树中，其 $\sum^n _ {i = 1}{E_i} + \sum K$ 的最小值。

lxhgww 最近迷上了一款游戏，在游戏里，他拥有 $n$ 个装备（ $n \le 1000000$ ），每种装备都有 $2$ 个属性，这些属性的值用 $[1,10000]$ 之间的数表示。当他使用某种装备时，他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。

游戏进行到最后， lxhgww 遇到了终极 boss ，这个终极 boss 很奇怪，攻击他的装备所使用的属性值必须从 $1$ 开始连续递增地攻击，才能对 boss 产生伤害。现在lxhgww想知道他最多能连续攻击 boss 多少次？

秋之国共有 $n$ 个人，分别编号为 $1,2,…,n$ ，一开始每个人都投了一票，范围 $[1,n]$ ，表示支持对应编号的人当总统。共有 $m$ 次预选，每次选取编号 $[l_i,r_i]$ 内的选民展开小规模预选，在该区间内获得超过区间大小一半的票的人获胜，如果没有人获胜，则由小 C 钦定一位候选者获得此次预选的胜利（获胜者可以不在该区间内），每次预选的结果需要公布出来，并且每次会有 $k_i$ 个人决定将票改投向该次预选的获胜者。全部预选结束后，公布最后成为总统的候选人，没有候选人的话输出 $-1$ 。

有一个 $n$ 行 $m$ 列的黑白棋盘，你每次可以交换两个相邻格子（相邻是指有公共边或公共顶点）中的棋子，最终达到目标状态。要求第 $i$ 行第 $j$ 列的格子只能参与 $m _ {i,j}$ 次交换。

输出仅一行，为最小交换总次数。如果无解，输出 $-1$ 。