An edge-weighted tree of $n$ nodes is given with each edge colored in some color. Each node of this tree can be blocked or unblocked, all nodes are unblocked initially.

A simple path is a path in a graph that does not have repeating nodes. The length of a path is defined as the sum of weights of all edges on the path.

A path is good when it is a simple path consisting of edges of the same color $c$, all edges of color $c$ are on this path, and every node on the path is unblocked.

You need to operate $2$ kinds of queries:

1. block a node,
2. unblock a node.

After each query, print the maximum length among all good paths. If there are no good paths, print $0$.

Input

The first line contains two integers $n$, $q$ ($1 \leq n,q \leq 2\cdot 10^5$) — the number of nodes and the number of queries.

Then $n-1$ lines follow, each containing four integers $u$, $v$, $w$ and $c$ ($1 \leq u,v,w,c \leq n$; $u \not = v$), denoting a weighted edge connecting node $u$ and node $v$ with weight $w$ and color $c$. It is guaranteed that these edges form a tree.

Then $q$ lines follow, each containing two integers $p$ and $x$ ($p = 0$ or $p = 1$, $1\leq x\leq n$), denoting a query:

1. if $p = 0$, block the node $x$. It's guaranteed that it's not blocked at this time;
2. if $p = 1$, unblock the node $x$. It's guaranteed that it's blocked at this time.

Output

For each query, print the maximum length of a good path. If there are no good paths, print $0$.

见题面 Input 部分

见题面 Output 部分