Katharon Robot Deployment

Katharon country has \(n\) cities numbered from \(1\) to \(n\) connected by \(n-1\) roads forming a tree. One city is occupied by country X and turned into a base at city \(r\). From the base, the commander issues commands to deliver battle robots along a non‐repeating path in the tree. In such a command the commander first chooses an endpoint and then a starting point along the unique path from the base \(r\) to that endpoint, and then distributes a specified number of robots evenly (i.e. the same amount to each city on the path).

Moreover, to reallocate robots, the commander can also instruct to invert the robot counts on a valid path: the sequence of numbers on the cities of the chosen subpath (which is a contiguous segment on the unique path from \(r\)) will be reversed (i.e. if the counts are \(a_1,a_2,\dots,a_k\), they become \(a_k,a_{k-1},\dots,a_1\)).

The king of Kanari has obtained a disk showing the map and the recent command but not the number of robots in each city. He therefore asks you to answer queries regarding the sum, maximum, and minimum numbers of robots on the unique path between any two queried cities.

The commands are as follows:

1. Increase x y w: Increase the number of robots by \(w\) in every city on the unique path from \(x\) to \(y\). For these commands, it is guaranteed that \(x\) and \(y\) lie on a valid path (i.e. one is an ancestor of the other in the tree rooted at \(r\)).
2. Sum x y: Query the total number of robots on the unique path between \(x\) and \(y\). (For queries, \(x\) and \(y\) may be arbitrary.)
3. Major x y: Query the maximum number of robots on the unique path between \(x\) and \(y\).
4. Minor x y: Query the minimum number of robots on the unique path between \(x\) and \(y\).
5. Invert x y: Reverse the robot counts on the unique path from \(x\) to \(y\). It is guaranteed that \(x\) and \(y\) lie on a valid path (i.e. one is an ancestor of the other).

Input Format:

The first line contains three integers \(n\), \(r\) and \(q\): the number of cities, the base city, and the number of commands, respectively. The next \(n-1\) lines each contain two integers \(u\) and \(v\) representing a road between cities \(u\) and \(v\). Then \(q\) lines follow with one command per line, formatted as described above.

Output Format:

For each query command (Sum, Major, or Minor), output a single line containing the answer.

inputFormat

The input begins with a line containing three integers \(n\), \(r\), and \(q\). The following \(n-1\) lines each contain two integers \(u\) and \(v\) indicating a road between cities \(u\) and \(v\). This is followed by \(q\) lines of commands. The commands are in one of the following formats:

• Increase x y w
• Sum x y
• Major x y
• Minor x y
• Invert x y

For the Increase and Invert commands, it is guaranteed that \(x\) and \(y\) are on a valid path from the base \(r\) (i.e. one is an ancestor of the other). For the query commands (Sum, Major, Minor), \(x\) and \(y\) are arbitrary.

outputFormat

For each query command (Sum, Major, and Minor), output one line with the result of the query.

sample

5 1 6
1 2
1 3
2 4
2 5
Increase 1 2 5
Sum 4 5
Major 1 5
Minor 1 5
Invert 1 2
Sum 1 5

5
5
0
10

</p>