在2016年，佳媛姐姐刚刚学习了树，非常开心。现在他想解决这样一个问题：给定一颗有根树（根为 $1$），有以下两种操作：

1. 标记操作：对某个结点打上标记（在最开始，只有结点1有标记，其他结点均无标记，而且对于某个结点，可以打多次标记。）

2. 询问操作：询问某个结点最近的一个打了标记的祖先（这个结点本身也算自己的祖先）

你能帮帮她吗?

方伯伯正在做他的 OJ 。现在他在处理 OJ 上的用户排名问题。 OJ 上注册了 $n$ 个用户，编号为 $1$ ～ $n$ ，一开始他们按照编号排名。

方伯伯会按照心情对这些用户做以下四种操作，修改用户的排名和编号 ，共有 $m$ 次操作：

1. 操作格式为 1 x y ，意味着将编号为 $x$ 的用户编号改为 $y$ ，而排名不变，执行完该操作后需要输出该用户在队列中的位置，数据保证 $x$ 必然出现在队列中，同时， $y$ 是一个当前不在排名中的编号。

2. 操作格式为 2 x ，意味着将编号为 $x$ 的用户的排名提升到第一位，执行完该操作后需要输出执行该操作前编号为 $x$ 用户的排名。

3. 操作格式为 3 x ，意味着将编号为 $x$ 的用户的排名降到最后一位，执行完该操作后需要输出执行该操作前编号为 $x$ 用户的排名。

4. 操作格式为 4 k，意味着查询当前排名为 $k$ 的用户编号，执行完该操作后需要输出当前操作用户的编号。

对于 $100\%$ 的数据， $1 \leq n \leq 10^8,1 \leq m \leq 10^5$。

强制在线。

在 $2016$ 年，佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题，现在他在研究一个难题，需要你来帮助他。这个难题是这样子的：给出一个 $1$ 到 $n$ 的全排列，现在对这个全排列序列进行 $m$ 次局部排序，排序分为两种：

• $(0,l,r)$表示将区间 $[l,r]$ 的数字升序排序
• $(1,l,r)$表示将区间 $[l,r]$ 的数字降序排序
  最后询问第 $q$ 位置上的数字。

将要读二年级的小 Q 买了一款新型益智玩具——魔幻棋盘，它是一个 $N$ 行 $M$ 列的网格棋盘，每个格子中均有一个正整数。棋盘守护者在棋盘的第 $X$ 行第 $Y$ 列（行与列均从 $1$ 开始编号）并且始终不会移动。棋盘守护者会进行两种操作：

1. 询问：他会以自己所在位置为基础，向四周随机扩展出一块大小不定的矩形区域，向你询问这一区域内所有数的最大公约数是多少。

2. 修改：他会随意挑选棋盘上的一块矩形区域，将这一区域内的所有数同时加上一个给定的整数。

游戏说明书上附有这样一句话“聪明的小朋友，当你连续答对 $19930324$ 次询问后会得到一个惊喜噢！”。小 Q 十分想得到这个惊喜，于是每天都在玩这个玩具。但由于他粗心大意，经常算错数，难以达到这个目标。于是他来向你寻求帮助，希望你帮他写一个程序来回答棋盘守护者的询问，并保证 $100\%$ 的正确率。

为了简化问题，你的程序只需要完成棋盘守护者的 $T$ 次操作，并且问题保证任何时刻棋盘上的数字均为不超过 $2^{62} - 1$ 的正整数。

你的面前有 $n$ 个数排成一行，分别为 $a_1,a_2,...,a_n$ 。你打算在每相邻的两个 $a_i$c和 $a _ {i+1}$ 间都插入一个加号、减号或者乘号。那么一共有 $3^{n-1}$ 种可能的表达式。

你对所有可能的表达式的值的和非常感兴趣。但这毕竟太简单了，所以你还打算支持一个修改操作，可以修改某个 $a_i$ 的值。

你能够编写一个程序对每个修改都输出修改完之后所有可能表达式的和吗？注意，修改是永久的，也就是说每次修改都是在上一次修改的基础上进行，而不是在最初的表达式上进行。

现在有一棵二叉树，所有非叶子节点都有两个孩子。在每个叶子节点上有一个权值(有 $n$ 个叶子节点，满足这些权值为 $1...n$ 的一个排列)。可以任意交换每个非叶子节点的左右孩子。
要求进行一系列交换，使得最终所有叶子节点的权值按照前序遍历序写出来，逆序对个数最少。

Y901 高速公路是一条由 $N-1$ 段路以及 $N$ 个收费站组成的东西向的链，我们按照由西向东的顺序将收费站依次编号为 $1 \sim N$ ，从收费站 $i$ 行驶到 $i+1$ (或从 $i+1$ 行驶到 $i$ )需要收取 $V_i$ 的费用。高速路刚建成时所有的路段都是免费的。

政府部门根据实际情况，会不定期地对连续路段的收费标准进行调整，根据政策涨价或降价。

求对于给定的 $l,r(l < r)$ ，在第 $l$ 个到第 $r$ 个收费站里等概率随机取出两个不同的收费站 $a$ 和 $b$ ，那么从 $a$ 行驶到 $b$ 将期望花费多少费用呢?

给定一个长度为 $n$ 且初始值全为 $0$ 的序列。你需要支持以下两种操作：

• $Add\, L, R, h$ ：将序列 $[L, R]$ 内所有值小于 $h$ 的元素都赋为 $h$，此时不改变高度大于 $h$ 的元素值
• $Remove\, L, R, h$：将序列 $[L, R]$ 内所有值大于 $h$ 的元素都赋为 $h$ ，此时不改变高度小于 $h$ 的元素值

你需要输出进行 $k$ 次上述操作之后的序列。

给定一棵 $n$ 个节点的树，对于每个点都有两个权值 $w_i,c_i$ 。

存在 $m$ 个操作，分为4类。

• “CC x c”：将 $c_x$ 更改为 $c$ ；

• “CW x w”：将 $w_x$ 更改为 $w$ ；

• “QS x y”：对所有满足在 $x$ 到 $y$ 路径上且 $c_i = c_x = c_y$ 的节点 $i$，求 $\sum w_i$ ；

• “QM x y”：对所有满足在 $x$ 到 $y$ 路径上且 $c_i = c_x = c_y$ 的节点 $i$ ，求 $\max(w_i)$ ；

对于后两个操作，保证 $c_x = c_y$ 。

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