A simple network system can be described as an unrooted tree. Each node is a server, and the data lines connecting servers are treated as tree edges. When two servers exchange data, the data passes through all servers on the path connecting these two servers (including the two servers themselves). Each data exchange request has a non-negative importance value; naturally, more important requests require higher priority. Furthermore, if at any moment there exists a very important (effectively infinite importance) and massive data exchange request, all servers on the path of this request will prioritize processing it and become blocked, causing delays for other requests passing through these servers.

As the network system administrator, you need to monitor the system's operational status. The system's operation is simple: at each moment, only one of the following two types of events can occur:

• A new data exchange request appears between two servers.
• A data exchange request ends.

We assume that the data volume of these exchange requests is sufficiently small. Your task is to determine, after each event, the maximum possible sum of importance values of the data exchange requests that would be delayed if a very important and massive data exchange request were to suddenly occur.

Input

The first line contains two positive integers $N$ and $M$, representing the number of servers and the number of events (moments), respectively.

The next $N - 1$ lines each contain two integers $u, v$, describing a tree edge. $u$ and $v$ are server identifiers, with server IDs ranging from $1$ to $N$.

The next $M$ lines describe each event in chronological order; that is, the $i$-th line ($i=1, 2, 3, \dots, M$) describes the event occurring at moment $i$. The events are described in two ways:

• + u v w: A data exchange request with importance $w$ appears between server $u$ and server $v$.
• - t: The data exchange request that appeared at moment $t$ ends.

Output

Output $M$ lines, each containing an integer, describing the maximum sum of importance values of the delayed data exchange requests if a very important and massive data exchange request were to suddenly occur after each event. If there are no data exchange requests at that moment, output $0$.

Constraints

For $30\%$ of the data, $1 \leq N, M \leq 100$.

For another $30\%$ of the data, there are no type-two events (i.e., no requests end).

For $100\%$ of the data, $1 \leq N, M \leq 10^5$, and all input values are non-negative integers within the range of int.

It is guaranteed that the input is valid.

Examples

Input 1

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 1

7
11
4
7
10
9