时间限制： 1.0 秒

空间限制： 512 MB

题目描述

Gold Ship 在玩一款太空即时战略游戏。游戏中有 $n$ 支舰队，每支舰队中可以包含若干飞船，而每个飞船有等级，是一个正整数。

游戏开始时，这些舰队都是空的，不包含任何飞船。现在她将要进行 $q$ 次操作，每个操作是下列六种之一：

• 造船：给出正整数 $x, v$，建造一艘等级为 $v$ 的飞船，加入到第 $x$ 支舰队中；
• 训练：给出正整数 $x, v$，对第 $x$ 支舰队进行训练，使它的所有飞船等级上升 $v$；
• 移动：给出正整数 $x, y$，将第 $x$ 支舰队里中位数等级的飞船移动到第 $y$ 支舰队中。如果第 $x$ 支舰队是空的，则这个操作不产生效果。如果第 $x$ 支舰队里中位数等级的飞船不止一个，则移动其中的任意一个；
• 查询：给出正整数 $x$，询问第 $x$ 支舰队中飞船等级的中位数。如果第 $x$ 支舰队是空的，则应当回答 $0$；
• 合并：给出正整数 $x, y$，将第 $x$ 支舰队的所有飞船转移到第 $y$ 支舰队中，第 $x$ 支舰队变为空的；
• 删除：给出正整数 $x, v$，将第 $x$ 支舰队中等级不超过 $v$ 的飞船删除。

现在你需要实现这部分游戏逻辑，接收这 $q$ 次操作信息进行模拟，并对所有查询操作给出回答。

对于一个含有 $k$ 艘飞船的舰队，飞船等级的中位数定义为将飞船的等级从小到大排列为一个长度为 $k$ 的序列后，位于第 $\lceil \frac k2 \rceil$ 个位置的数。例如 $1, 1, 2, 3, 4$ 的中位数是 $2$，而 $4, 6, 7, 10$ 的中位数是 $6$。

输入格式

从标准输入读入数据。

输入的第一行包含两个正整数 $n, q$。

接下来 $q$ 行依次描述 $q$ 次操作。每行的第一个整数描述操作类型，之后一个或两个整数是该操作的信息。具体格式如下：

• 1 x v：造船操作
• 2 x v：训练操作
• 3 x y：移动操作
• 4 x：查询操作
• 5 x y：合并操作
• 6 x v：删除操作

输出格式

输出到标准输出。

对于查询操作之外的五种操作，你不需要输出任何信息。对于每个查询操作，你需要输出一行，包含一个非负整数，即对该询问的回答。

3 12
1 1 4
1 1 4
1 2 1
1 2 3
2 2 2
3 2 1
3 3 2
4 1
1 3 3
5 1 3
6 3 3
4 3

4
4

样例 1 解释

经过前 4 次操作，三支舰队中包含的飞船等级为 $4, 4, 1, 3,$

第 5 次操作后变为 $4, 4, 3, 5,$

第 6 次操作后变为 $3, 4, 4, 5,$

第 7 次操作没有效果

第 8 次操作的回答是 $4$

第 9 次操作后变为 $3, 4, 4, 5, 3$

第 10 次操作后变为 $5, 3, 3, 4, 4$

第 11 次操作后变为 $5, 4, 4$

第 12 次操作的回答是 $4$

子任务

所有测试点满足 $1 \le n, q \le 400000$，所有操作中出现的参数 $x, y$ 满足 $1 \le x, y \le n$，参数 $v$ 满足 $1 \le v \le 10^7$。保证移动和合并操作中 $x \neq y$。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

• 子任务 1（20 分）：$n,q\le 2000$；
• 子任务 2（35 分）：无训练与合并操作；
• 子任务 3（45 分）：无特殊条件