题目描述

某个地区有 $N$ 座城市，编号为 $1$ 到 $N$。城市之间可以签订条约，表示双方愿意合作。

如果若干城市之间可以通过一条或多条条约相互连通，那么这些城市构成一个联盟。一个联盟的大小定义为其中包含的城市数量。

每条条约都有一个长度，表示起草这份条约所使用的页数。为了减少官僚主义，城市们有时会删除当前仍然生效的最长条约，也就是页数最多的条约。

此外，城市之间还会以联盟为单位进行躲避球比赛。一轮躲避球比赛规则如下：

• 每个联盟组成一支队伍。
• 各联盟两两配对进行比赛。
• 如果联盟数量为奇数，则有一支队伍会和一个大小为 $0$ 的空联盟比赛。
• 两个大小分别为 $A$ 和 $B$ 的联盟比赛，其不公平度为 $|A-B|$。
• 一轮比赛的总不公平度为所有比赛不公平度之和。

对于当前所有联盟，你需要通过最优配对，使这一轮比赛的总不公平度最小，并输出这个最小值。

操作说明

需要支持 $Q$ 个操作，操作共有三种：

• a u v p：在城市 $u$ 和城市 $v$ 之间添加一条页数为 $p$ 的条约。
• r：删除当前仍然生效的最长条约，即页数最大的条约。
• d：询问当前联盟进行一轮躲避球比赛时，最小可能的总不公平度。

对于每个 d 操作，都需要立即输出答案。

输入格式

第一行包含两个整数：

N Q

接下来 $Q$ 行，每行是以下三种格式之一：

a u v p
r
d

分别表示添加条约、删除最长条约、询问最小总不公平度。

输出格式

对于每个 d 操作，输出一行一个整数，表示当前最小可能的总不公平度。

数据范围

• $1 \le N \le 100000$。
• $1 \le Q \le 500000$。
• $1 \le p \le 10^9$。
• $1 \le u,v \le N$。
• 对于每个 a 操作，$u \ne 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

输出

3
1

样例解释

第一次询问时，城市 $1,2,3$ 全部属于同一个联盟。该联盟需要和大小为 $0$ 的空联盟比赛，不公平度为：

随后删除城市 $2$ 和城市 $3$ 之间的条约。此时一个联盟包含城市 $1,2$，另一个联盟包含城市 $3$，最优配对的不公平度为：

样例 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

输出

4
0
2

样例解释

第一次询问时，有一个大小为 $4$ 的联盟和两个大小为 $1$ 的联盟，最小总不公平度为 $4$。

第二次询问时，有两个大小为 $2$ 的联盟和两个大小为 $1$ 的联盟，最小总不公平度为 $0$。

第三次询问时，有三个大小为 $2$ 的联盟，需要有一个联盟与空联盟比赛，最小总不公平度为 $2$。