At UTS, there are ~N~ classrooms numbered from ~1~ to ~N~, connected by ~N-1~ hallways such that it is possible to get from any classroom to another. The ~i^{th}~ hallway connects classroom ~u_i~ and ~v_i~ and can be travelled both ways. On the last day of school, the student council and volunteers (who begin in classroom ~1~) will deliver candygrams to every student in the school.

The distance between two classrooms is defined as the least number of hallways one can take to get from one to the other. The cost of delivering a candygram to any student is defined as the student's distance to classroom ~1~, and the candygram delivery team would like to keep track of the total cost of delivering a candygram to every student. Before school starts, every classroom will have ~0~ students, but people will begin entering and leaving classrooms throughout the day.

For unspecified reasons, the student council has the power to dig secret tunnels between classrooms (the tunnel still contributes ~1~ unit of distance to a path that takes it). To make the delivery process easier, they plan to dig one tunnel connecting two classrooms, but they do not know which pair of classrooms is best! Thus, they have asked you to consider ~Q~ events of two types:

1. U x k - The number of students in classroom ~x~ changes by ~k~. Note that ~k~ can be negative, in which case the number of students decreases. It is guaranteed that the number of students in any classroom will always be in the inclusive range ~[0,1000]~.

2. Q a b - The student council wants to know the total cost of delivering candygrams to every student if they were to dig a secret tunnel connecting classroom ~a~ and ~b~. Note that the tunnel is not actually dug out and it is not considered in subsequent queries.

Can you write a program to help the student council in their questionable endeavours?

Constraints

~2 \le N,Q \le 2 \times 10^5~
~1 \le u_i, v_i \le N~
~1 \le x, a, b \le N~, ~a \ne b~
~|k| \le 1000~

It is possible to travel between any two classrooms via the hallways.

The number of students in any classroom will always be in the inclusive range ~[0,1000]~.

Subtask 1 [10%]

~2 \le N,Q \le 1000~

Subtask 2 [90%]

No additional constraints.

Input Specification

The first line of input contains two integers, ~N~ and ~Q~, the number of classrooms, and the number of events.

The next ~N-1~ lines of input each contain two integers, ~u_i~ and ~v_i~, indicating that there is a bidirectional hallway connecting classroom ~u_i~ and classroom ~v_i~. It is guaranteed to be possible to travel between any two classrooms using these hallways.

The final ~Q~ lines of input contain the events in order, as described in the problem statement.

Output Specification

For each query Q event, output one line containing one integer, the total cost of delivering candygrams to every student if a secret tunnel is dug between classroom ~a~ and ~b~.

Sample Input

7 5
1 2
3 1
2 4
4 6
5 4
6 7
U 5 2
Q 1 4
U 7 3
U 5 -1
Q 6 3

Sample Output

4
12

Explanation for Sample

For the first query Q event, the ~2~ students in classroom ~5~ would each be a distance of ~2~ from classroom ~1~ if a secret tunnel is dug between classroom ~1~ and classroom ~4~. The shortest path would be ~5 \to 4 \to 1~. Thus, the total cost is ~2 \times 2 = 4~.

For the second query Q event, there are ~3~ students in classroom ~7~ and now only ~1~ student in classroom ~5~. The ~3~ students in classroom ~7~ would each be a distance of ~3~ from classroom ~1~ if a secret tunnel is built between classroom ~6~ and classroom ~3~. The shortest path would be ~7 \to 6 \to 3 \to 1~. The cost to deliver a candygram to the student in classroom ~5~ would be ~3~, with the shortest path being ~5 \to 4 \to 2 \to 1~. Thus, the total cost is ~3 \times 3 + 1 \times 3 = 12~.