C. A National Pandemic
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Nowadays, the Kingdom of Dreamgrid is suffering from a national pandemic. Fortunately, president Baobao is working effectively with the Center for Disease Control (CDC) and they are trying their best to make everything under control.

As the chief of CDC, you are required to update the situation simultaneously and answer queries from president Baobao himself and reporters from News agencies in the world.

Specifically, let's consider the country as a map of $$$n$$$ nodes, denoting cities. Due to the severe pandemic, most roads and highways are closed except $$$n-1$$$ roads, which keep the country connected. We also define $$$F(x)$$$ for each city $$$x$$$ as the severity of the local disease situation. Now you need to deal with three kinds of events/queries:

  1. Another outbreak happens in city $$$x$$$ with the severity value of $$$w$$$. For each city $$$y$$$, $$$F(y)$$$ will be increased by $$$w-\mathit{dist}(x,y)$$$, where $$$\mathit{dist}(x,y)$$$ is the number of edges on the path from $$$x$$$ to $$$y$$$.
  2. Update $$$F(x)$$$ of city $$$x$$$ to $$$\min(F(x),0)$$$, which means the situation in city $$$x$$$ has been improved with the effort of the government and medical faculties.
  3. Query for the severity value $$$F(x)$$$ of city $$$x$$$.

Every city's severity value $$$F$$$ is $$$0$$$ initially. Also, $$$F(x)$$$ can be negative in some moment and we don't have to adjust it.

Input

There are multiple test cases. The first line of the input contains an integer $$$T$$$ $$$(1 \leq T \leq 5)$$$ indicating the number of test cases.

For each test case, the first line contains two integers $$$n,m$$$ $$$(1 \leq n,m \leq 5 \times 10^4)$$$, representing the number of cities and the number of events and queries. The following $$$n-1$$$ lines describe all paths in the country, each of which contains two integers $$$x,y$$$ $$$(1 \leq x,y \leq n)$$$, representing a road between city $$$x$$$ and $$$y$$$. The following $$$m$$$ lines describe all events, each starting with an integer $$$\mathit{opt}$$$ $$$(1 \leq \mathit{opt} \leq 3)$$$, and if $$$\mathit{opt}$$$ is

  1. there will be two integers $$$x,w$$$ $$$(1 \leq x \leq n,0 \leq w \leq 10000)$$$ in the same line. This refers to Event 1 in the description above.
  2. there will an integer $$$x$$$ $$$(1 \leq x \leq n)$$$ in the same line. This refers to event 2.
  3. there will an integer $$$x$$$ $$$(1 \leq x \leq n)$$$ in the same line. This refers to the query you need to reply.
Output

Output an integer for each query in one line.

Example
Input
1
5 6
1 2
1 3
2 4
2 5
1 1 5
3 4
2 1
1 2 7
3 3
3 1
Output
3
9
6