Tree Point Weight Update and Query

You are given a tree with \(n\) nodes (numbered from 1 to \(n\)) and \(n-1\) edges. Each edge has a weight of 1 and each node initially has a point weight of 0. You need to process \(m\) operations of the following two types:

• Q x: Query the current point weight of node \(x\).
• M x d w: For all nodes whose distance from node \(x\) is at most \(d\), add the value \(w\) to their point weight.

The distance between two nodes is defined as the sum of the weights of the edges on the unique path between them. Note that all edge weights are 1, so the distance is simply the number of edges between the nodes.

Input Format: The first line contains two integers \(n\) and \(m\). The next \(n-1\) lines each contain two integers \(u\) and \(v\) denoting an edge between nodes \(u\) and \(v\). Then \(m\) lines follow, each describing an operation in one of the two formats above.

Output Format: For each query operation, output the current point weight of the specified node on a new line.

inputFormat

The input begins with a line of two integers \(n\) and \(m\) (number of nodes and number of operations respectively).

This is followed by \(n-1\) lines, each with two integers \(u\) and \(v\) indicating an edge between nodes \(u\) and \(v\).

Then, \(m\) lines follow. Each line is either in the format Q x (query the point weight of node \(x\)) or M x d w (update all nodes with distance \(\le d\) from node \(x\) by adding \(w\) to their point weight).

outputFormat

For each query operation, output the point weight of the requested node on a separate line.

sample

5 5
1 2
1 3
2 4
2 5
M 2 1 10
Q 1
Q 3
M 1 2 5
Q 5

10
0
15