一个简单的网络系统可以被描述成一棵无根树。每个节点为一个服务器。连接服务器与服务器的数据线则看做一条树边。两个服务器进行数据交互时，数据会经过连接这两个服务器的路径上的所有服务器（包括这两个服务器自身）。每个数据交互请求都有一个非负的重要度，越重要的请求显然需要得到越高的优先处理权。此外，如果在某一个时刻存在一条非常重要（可以看作重要度无穷大）、且数据量巨大的交互请求，则所有被该交互经过的服务器都会优先处理这条交互并阻塞，从而导致其他通过这些服务器的交互出现延迟。

现在，你作为一个网络系统的管理员，要监控整个系统的运行状态。系统的运行也很简单，在每一个时刻，只有可能出现下列二种事件中的一种：

• 在某两个服务器之间出现一条新的数据交互请求；
• 某个数据交互请求结束。

我们假设这些事件中的交互请求的数据量都足够小。你的任务是在每一个时刻的事件结束后，求出：如果突然出现一条非常重要、且数据量巨大的交互请求，那么因其造成延迟的数据交互请求的重要度之和最大可能是多少？

输入格式

输入的第一行包含二个正整数 $N,M$，分别表示服务器的个数、事件（时刻）的个数。

接下来 $N-1$ 行，每行两个整数 $u,v$，描述一条树边。$u$ 和 $v$ 是服务器的编号，服务器编号 $1,\dots ,n$。

接下来 $M$ 行，按发生时刻依次描述每一个事件；即第 $i$ 行（$i=1,2,3,\dots ,m$）描述时刻 $i$ 发生的事件。事件的描述有两种：

• + u v w：服务器 $u$ 和 $v$ 之间出现了一条重要度为 $w$ 的数据交互请求；
• - t：时刻 $t$ 出现的数据交互请求结束。

输出格式

输出 $M$ 行，每行一个整数，依次描述在每个事件后，如果突然出现一条非常重要、且数据量巨大的交互请求，那么因其造成延迟的数据交互请求的重要度之和的最大值。如果此时没有任何数据交互请求，输出 $0$。

样例一

input

5 6
1 2
2 4
4 3
2 5
+ 1 4 7
+ 5 5 4
- 1
+ 3 4 3
+ 1 1 6
- 2

output

7
11
4
7
10
9

限制与约定

对于 $30\mathrm{\%}$ 的数据，有$1\le N,M\le 100$。

另有 $30\mathrm{\%}$ 的数据，没有第二类事件，即所有请求都不会结束。

对于 $100\mathrm{\%}$ 的数据，有 $1\le N,M\le {10}^5$，所有的输入数据均为 int 范围内的非负整数。

保证输入合法。

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

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

下载

样例数据下载