A boy named List who is perfect in English. Now he wants to travel and he is making a plan. But the cost of traveling between two cities always changes. Now he wants to know how many different kinds of continuous same cost he has to pay for traveling between  two cities. Can you help him? (He is so lazy to do this by himself.)

There are multiple cases.

The first line contains two positive numbers N and M(N (N<=40000) where N is the amount of cities and M (M<=50000)) is the amount of operations.Then N-1 lines where each line have 3 integers a  b and c, representing that there is a bidirectionoal road between city a and city b, and the cost is c.(a != b and c <= 100000).

Then there are M lines of operation. For example, "Change a b c" means changing all the costs of the road which are passed by him when he travels from city a to city b to c. "Query a b" means he wants you to tell him how many different kinds of continuous same cost he has to pay traveling from city a to city b.(if a == b, the cost is 0).



He insure you that there is exactly one route between every two different cities and there is no circle.

For each query, output the answer as expected in a separate line.

9 3
1 2 2
2 3 1
1 7 2
1 4 2
3 5 2
3 6 1
5 8 2
5 9 3
Q 1 8
C 2 6 3
Q 1 6 · \n
 · · \n
 · · \n
 · · \n
 · · \n
 · · \n
 · · \n
 · · \n
 · · \n
 · · \n
 · · · \n
 · · \n

3
2 \n
 \n