背景

在成功地解决了石板的问题之后,Kanari国王得到了一个神秘的圆盘形装置。正在他不懂觉厉的时候,突然一名士兵气喘吁吁地跑了过来,大喊:“防线已经崩溃了!X国的外星人要打进来了!”(好不容易想到的设定不接着用太可惜了)这时,国王手中的圆盘发出了光芒……

描述

Katharon国有\inline n个城市,编号为\inline 1\sim n。出于勤俭节约,不铺张浪费的考虑,城市间只连有\inline n-1条道路,使得可以从一个城市出发沿着道路走到另一座城市。

现在X国的飞船降落在了某个城市,并把它改造成了自己的据点。X国占领其他国家的一贯做法是,在据点里造一堆工厂生产战斗机器人,然后沿着被侵略国的道路运送到其他城市。X国的司令向来不走回头路,而且崇尚团结与绝对的公平,因此运送战斗机器人时,会先选择一个终点,再在从据点到终点的路径上选择一个起点,然后把机器人均匀分配到起点到终点路径上的每个城市。同时,为了重新分配机器人,X国的司令还会下令,按照与运送机器人相同的方法选择起点和终点,然后翻转这条路径上城市的机器人的数量。比如,选定的路径上的城市的机器人数依次为\inline 1,2,3,4,5,翻转之后就变成了\inline 5,4,3,2,1

Kanari国王手中的圆盘上浮现出了Katharon国的地图。不仅如此,上面还标出了X国据点在\inline r号城市,并显示出了X国司令刚刚下达的指令。“太好了!”国王欢呼。“我们能第一时间掌握敌人的布局,就一定能击退X国的侵略者!”

但是还有一个问题没有解决。圆盘上只显示了指令,却没有标出每个城市的机器人数量,这让国王很是头疼。于是他找到了你,想让你帮忙设计一个程序来回答国王的询问。国王只关心某两个点之间路径上的城市的机器人和、最大值以及最小值,以便确定兵力部署、攻击要点和敌方的薄弱点。

X国司令的指令和Kanari国王的询问如下:

  1. Increase x y w
    运送一批机器人到从\inline x\inline y的路径上的城市,并分配给每个城市\inline w个机器人;
  2. Sum x y
    询问从\inline x\inline y的路径上的城市的机器人数量之和;
  3. Major x y
    询问从\inline x\inline y的路径上的城市的机器人数量的最大值;
  4. Minor x y
    询问从\inline x\inline y的路径上的城市的机器人数量的最小值;
  5. Invert x y
    翻转从\inline x\inline y的路径上的城市的机器人数量。

对于X国司令的指令,保证给定的\inline x\inline y满足上文所述的要求。对于Kanari国王的询问,保证给定的\inline x\inline y满足上述要求。

输入格式

第一行有三个整数\inline n\inline m\inline r,分别表示树的节点数、指令和询问总数,以及X国的据点。

接下来\inline n-1行,每行两个整数\inline x\inline y,表示Katharon国的一条道路。

接下来\inline m行,每行描述一个指令或询问,格式见题目描述。

输出格式

对于每个询问操作,输出所求的值。

样例输入

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

样例输出

0
0
6
3
19

样例解释

初始权值为\inline \{0,0,0,0,0\}

在第二次操作后,权值变为\inline \{0,0,3,3,3\}

在第五次操作后,权值变为\inline \{3,0,0,3,3\}

在第七次操作后,权值变为\inline \{5,2,2,5,5\}

数据范围与约定

对于所有数据,满足\inline 1\leq n,m\leq 50000,且对于运送操作,\inline 1\leq w\leq 1000