G. Not An SQRT Problem
time limit per test
1.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a tree of size $$$n$$$ rooted at node $$$1$$$. At first, values of all nodes are equal to $$$0$$$.

Process $$$q$$$ queries of four types:

  • "1 x v": add $$$v$$$ to all nodes in the subtree rooted at node $$$x$$$;
  • "2 x v": add $$$v$$$ to all child nodes of node $$$x$$$. It is guaranteed that $$$x$$$ has at least one child node;
  • "3 x": query the maximum value in the subtree rooted at node $$$x$$$;
  • "4 x": query the maximum value among all child nodes of node $$$x$$$. It is guaranteed that $$$x$$$ has at least one child node;
Input

The first line contains two space-separated integers $$$n$$$ and $$$q$$$ $$$(2 \leq n,q \leq 3 \cdot 10^5)$$$, representing the number of nodes in the tree.

The following $$$n-1$$$ lines describe the edges of the tree. Each line contains two space-separated integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$), indicating an edge between nodes $$$u_i$$$ and $$$v_i$$$. It is guaranteed that the input data represents a tree.

The next $$$q$$$ lines describe the operations:

  • "1 x v": add $$$v$$$ ($$$-10^9 \le v \le 10^9$$$) to all nodes in the subtree rooted at node $$$x$$$ ($$$1 \le x \le n$$$);
  • "2 x v": add $$$v$$$ ($$$-10^9 \le v \le 10^9$$$) to all children of node $$$x$$$ ($$$1 \le x \le n$$$). It is guaranteed that $$$x$$$ has at least one child node;
  • "3 x": query the maximum value in the subtree rooted at node $$$x$$$ ($$$1 \le x \le n$$$);
  • "4 x": query the maximum value among all children of node $$$x(1 \le x \le n)$$$. It is guaranteed that $$$x$$$ has at least one child node.
Output

For each query of type $$$3$$$ or $$$4$$$, output the corresponding maximum value. Each result should be on a new line.

Example
Input
5 10
1 2
1 3
2 4
2 5
3 1
1 1 1
1 2 2
2 1 -5
3 2
4 1
3 1
2 2 -3
4 1
3 1
Output
0
3
-2
3
-2
1