DZY开始有 $n$ 个点，现在他对这 $n$ 个点进行了 $m$ 次操作，对于第 $i$ 个操作（从 $1$ 开始编号）有可能的三种情况：

1. Add a b： 表示在 $a$ 与 $b$ 之间连了一条长度为 $i$ 的边（注意，$i$是操作编号）。保证 $1\le a,b\le n$。
2. Delete k： 表示删除了当前图中边权最大的k条边。保证 $k$ 一定不会比当前图中边的条数多。
3. Return： 表示撤销第 $i-1$ 次操作。保证第 $1$ 次操作不是 Return 且第 $i-1$ 次不是 Return 操作。

请你在每次操作后告诉DZY当前图的最小生成树边权和。如果最小生成树不存在则输出 $0$。

输入格式

第一行两个正整数 $n,m$。表示有 $n$ 个点 $m$ 个操作。 接下来 $m$ 行每行描述一个操作。

输出格式

对于每一个操作输出一行一个整数表示当前最小生成树边权和。

样例一

input

2 2
Add 1 2
Return

output

1
0

样例二

input

5 10
Add 2 1
Add 3 2
Add 4 2
Add 5 2
Add 2 3
Return
Delete 1
Add 2 3
Add 5 2
Return

output

0
0
0
10
10
10
0
0
15
0

样例三

见样例数据下载

限制与约定

时间限制：$1\mathtt{\text{s}}$

空间限制：$64\mathtt{\text{MB}}$

下载

样例数据下载