题目背景

Python / Java（很）可能无法通过本题。不建议不使用 C/C++。

题目描述

这是一道交互题。我们利用交互来让你强制在线回答询问。

有 $N$ 个点，编号从 $1$ 到 $N$，你需要解决如下 $Q$ 个询问：

• $\texttt{a u v p}$，在 $u$ 和 $v$ 之间添加长度为 $p$ 的无向边。

• $\texttt{r}$，删除当前图中最长的无向边。

• $\texttt{d}$，把当前图中连通块两两配对（如果连通块数量为奇数，那就选择一个连通块和大小为 $0$ 的连通块配对），记为 $(A_i,B_i)$。

  设有 $k$ 个连通块，令连通块 $A$ 的点数为 $|A|$，最小化 $\displaystyle \sum_{1\le i\le k}||A_i|-|B_i||$。只需要输出最小化后的这个值。

输入格式

第一行给定两个整数 $N,Q$。

接下来 $Q$ 行查询，每行格式即题目描述三者之一。

输出格式

对于每条类型为 $\texttt{d}$ 的查询，程序必须在处理后续查询之前立即输出答案。此外，你需要在每次输出答案后立即刷新输出缓冲区。

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

3
1

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

提示

【样例解释】

注意以下解释只按顺序解释类型为 $\texttt{d}$ 的查询。

• 对于样例 $1$，第一次查询，连通块为 $(1,2,3)$，答案为 $3$，第二次查询，连通块为 $(1,2)$ 和 $(3)$，答案为 $1$。

• 对于样例 $2$，在第一次查询，有一个大小为 $4$ 的连通块和两个大小为 $1$ 的连通块，总不公平分数为 $4$；在第二次查询中，有两个大小为 $2$ 的连通块和两个大小为 $1$ 的连通块，答案为 $0$；在第三次查询，有三个大小为 $2$ 的联盟，答案为 $2$。

【数据规模与约定】

对于所有数据，满足：

$1 \leq N \leq 100000,1 \leq Q \leq 500000,1 \leq p \leq 10^{9},1 \leq u \leq N,1 \leq v \leq N$。

对于类型 $\texttt{a}$ 的查询，$u \neq v$，添加无向边时，$u$ 和 $v$ 之间不存在无向边，且所有 $p$ 均唯一。

详细子任务附加限制及分值如下表所示：

子任务编号	分值	附加限制
$1$	$9$	$N \le 10,Q \le 20$
$2$	$10$	$N \le 2000,Q\le 4000$
$3$	$6$	类型 $\texttt{d}$ 的查询不超过 $10$ 次
$4$	$17$	类型 $\texttt{a}$ 的查询，满足 $u+1=v$
$5$	$14$	满足随着边的建立，$p$ 递增
$6$	$26$	满足随着边的建立，$p$ 递减
$7$	$18$	无附加限制