一个区域包含 $N$ 个城市，编号从 $1$ 到 $N$。这些城市可以建立条约，表示它们之间愿意合作。

联盟是一组城市，其中每个城市通过一条或多条条约与组内的其他所有城市相连。联盟的大小是指属于该联盟的城市数量。

每份条约都有一个长度，代表起草该条约所用的页数。为了减少官僚作风，城市偶尔会移除最长的有效条约（即页数最多的那份）。

除了行政事务外，城市之间还会进行联盟间的躲避球比赛。躲避球比赛遵循以下规则： 每个联盟组成一个队伍。 联盟两两配对进行比赛。 如果联盟总数为奇数，则其中一个队伍将与一个大小为 $0$ 的空联盟进行比赛。 大小为 $A$ 和 $B$ 的两个联盟之间的比赛，其不公平度得分为 $|A - B|$。 * 一轮比赛的总不公平度得分是所有场次不公平度得分之和。

你必须通过最优地配对联盟，确定可能的最小总不公平度得分。

查询

你必须支持 $Q$ 个以下类型的查询： a: 在城市 $u$ 和 $v$ 之间添加一份 $p$ 页的条约。 r: 移除最长的条约（即页数最多的那份）。所有条约的页数都是唯一的。 * d: 根据当前的联盟情况，计算躲避球比赛的最小总不公平度得分。

d 类型的查询必须在请求时立即回答，在处理任何后续查询之前。

输入格式

你的程序将针对每个测试用例运行一次。程序应按以下格式从标准输入读取数据：

• 第 1 行：$N$ $Q$
• 接下来的 $Q$ 行，每行采用以下格式之一：
  • a u v p
  • r
  • d

对应于不同的查询操作。

输出格式

对于每个 d 类型的查询，程序应立即做出响应，并在处理任何额外查询之前立即刷新输出。这可以通过以下方式之一完成： C++: std::cout << std::endl; Python: print("", flush=True)

这两者都会在输出中添加一个换行符。

数据范围

• $1 \le N \le 100000$
• $1 \le Q \le 500000$
• $1 \le p \le 10^9$
• $1 \le u \le N$
• $1 \le v \le N$
• 对于每个 a 类型查询，$u \neq v$
• 每当在 $u$ 和 $v$ 之间添加条约时，此前 $u$ 和 $v$ 之间没有有效的条约
• 所有页数 $p$ 都是唯一的

子任务

1. (9 分) $N \le 10, Q \le 20$
2. (10 分) $N \le 2000, Q \le 4000$
3. (6 分) 最多有 10 个 d 查询
4. (17 分) 对于每个 a 查询，$u + 1 = v$
5. (14 分) 条约按页数递增的顺序创建
6. (26 分) 条约按页数递减的顺序创建
7. (18 分) 无额外限制

样例

样例输入 1

3 5
a 1 2 1
a 2 3 2
d
r
d

样例输出 1

3
1

说明 1

当进行第一轮躲避球比赛时，城市 1、2 和 3 都在同一个联盟中。因此，它们与一个空联盟比赛，不公平度得分为 $|0 - 3| = 3$。然后，城市 2 和城市 3 之间的条约被移除。此时，躲避球比赛在城市 1 和城市 2 组成的联盟与城市 3 组成的联盟之间进行。这给出的不公平度得分为 $|2 - 1| = 1$。

样例输入 2

6 10
a 2 3 10
a 1 2 5
a 3 4 8
d
r
d
a 4 5 1
a 3 6 7
r
d

样例输出 2

4
0
2

说明 2

对于第一轮躲避球比赛，有一个大小为 4 的联盟和两个大小为 1 的联盟。这给出的总不公平度得分为 4。

对于第二轮躲避球比赛，有两个大小为 2 的联盟和两个大小为 1 的联盟，总不公平度得分为 0。

对于第三轮躲避球比赛，有三个大小为 2 的联盟，总不公平度得分为 2。