Highway

Canada has N cities, numbered 1 through N, and N - 1 highways, numbered 1 through N - 1. Every highway connects two cities and can be traveled in both directions. This highway network is designed so that any two cities are reachable from one another by transferring between several highways. In other words, the N cities and N - 1 highways form a tree structure.

You have been appointed as the director of the congestion information center, and you must manage congestion information for this highway network.

This facility manages, for each of the N - 1 highways, the travel time data from the starting city to the ending city. For example, if city 1 and city 3, city 3 and city 4, and city 2 and city 3 are connected by highways as in the figure below, then for each of (i, j) = (1, 3), (3, 1), (3, 4), (4, 3), (2, 3), (3, 2), the facility manages the "travel time from city i to city j" (note that the travel time of a highway is not necessarily the same in the upward and downward directions).

In addition, this facility does the following two things.

First, "congestion information" arrives at the facility from time to time. One piece of congestion information is given by three positive integers r, s, t. This means that "the upward travel time of highway r is s and the downward travel time is t." Here, upward for a highway refers to the direction from the city with the smaller number to the city with the larger number among the starting and ending cities of that highway, and downward refers to the opposite direction. The facility updates its data according to this congestion information.

Also, "inquiry" calls sometimes come to this facility. One inquiry is given by two positive integers x, y. At this time, based on the current data managed by the facility, you must calculate and answer the "travel time from city x to city y."

Given a sequence of "congestion information" and "inquiries" (collectively called queries) during a single day in chronological order, write a program that outputs the answer for each inquiry. However, before the first congestion information arrives, the travel time of all N - 1 highways is 1 in both directions.

Read the following input from standard input.

• The first line contains the integers N and M separated by a space.

• The following N - 1 lines each describe one highway. The i-th of these lines contains two integers pi, qi (1 ≤ pi < qi ≤ N) separated by a space, meaning that highway i connects city pi and city qi.

• The following M lines each describe one query (congestion information or inquiry), and one of the following is written:

  • Congestion information: the character 'I' and the integers r (1 ≤ r ≤ N - 1), s (1 ≤ s ≤ 1,000), t (1 ≤ t ≤ 1,000). Each is given separated by a space.
  • Inquiry: the character 'Q' and two distinct integers x (1 ≤ x ≤ N), y (1 ≤ y ≤ N). Each is given separated by a space.

Write the following data to standard output.

• The number of lines of data to output is the number of occurrences of the character 'Q' in the input. The i-th line contains one integer representing the answer to the i-th inquiry.

• 2 ≤ N ≤ 100,000 (the number of cities)
• 1 ≤ M ≤ 100,000 (the sum of the number of congestion information and the number of inquiries)