有 $n$ 个商店，每个商店都有一个特殊商品，每个人在任何时间都可以买。第一天可能没有进货，有若干次询问，而之后的每天，都有一次进货和若干次询问，每次进货都是某个商店进了某个编号的货，每次询问都是询问在编号为 $l$ 到 $r$ 的商店中，在 $d$ 天内进的货的编号异或 $x$ 的最大值。

可持久化线段树，是一种可以进行可持久化操作的线段树，具有优越的时间复杂度。

小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$ 。

超级计算机中的任务用三元组 $(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$ 秒正在运行的任务优先级之和。

强制在线。

给定一个含有 $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$ 。

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