Secure, Contain, Protect
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

        Special Containment Procedures College(SCPC)是一所奇异的学院。
        在学院铺设网络时，The Administrator为了节省经费，在众多局域网节点和链路中选择了一棵依照建造经费生成的最小生成树的方案，共n个局域网节点，编号从1到n，同时The Administrator设定这个树形结构的根为1号局域网节点。所以，SCPC的局域网是一棵n个节点的有根树。
不同的链路可能有不同的带宽和版本，维护的花费和带宽有关。第i条链路的带宽为a_i，维护的花费也为a_i，版本编号为c_i，链接了u_i号局域网和v_i号局域网。
        现在，这里不仅有多次数据传输，还有多次链路维护。The Administrator想知道每次传输的最大速率（带宽）和每次维护需要的花费。我们都知道带宽决定了数据传输的速率，而且传输的最大带宽是由传输路径上的最小链路带宽决定的。而每次维护的方式，都是选择一个局域网节点，将以这个节点为根的子树上版本号在L_i到R_i之间的链路维护。由于SCPC的局域网是一棵有根树，每个节点的父节点是确定的，所以，以节点为根的子树也是唯一的。
        
        但事实是，SCPC的局域网也是收容物，其奇异之处在于，对于一次版本号在L_i到R_i之间的维护，其一次维护的总花费不是子树上这种链路的花费直接相加，而是这些链路原本的花费异或上后的和。例如，原本子树上版本号在 2 到 4 之间的链路花费分别为1, 2, 3,,则其总花费为。
        SCPC的目标就是维持常态，从而使群众避免陷入恐惧，所以The Administrator 决定每次声明选择维护的子树个根节点时，声明的不是真正的子树根节点，而真正的子树根节点与声明的节点和上一次询问的答案有关，以此来混淆群众视听（虽然不知道是不是真的能避免
陷入恐慌（’▽’））。
        The Administrator设上一次询问的答案为LastAns:
  • 如上次询问的是数据传输，则LastAns就是传输的构 大速率（带宽）。
  • 若上次询问的是链路维护，则LastAns就是维护的总花费（注意是异或后的和）。
        当这次询问的内容是链路维护时，设声明的子树根节点为x，维护的真正子树根节点编号就是，n为局域网节点数，表示除法取余数，A、B后文会给出。当第一次询问是链路维护，此时LastAns视为0。
       现The Administrator给你SCPC局域网的信息，并按顺序给出询问，TA想知道所有询问的答案。


 


输入描述:

第一行包括两个整数和，分别表示树的节点个数和询问的次数。
第二行输入两个整数A，，用于求出维护花费的询问中真正根节点U。
第3到第行（共n-1行），每行输入四个正整数，，，，代表节点u_i到节点v_i有一条边，该边的带宽为a_i，版本编号为c_i。


接下来q行，每行首先输入一个字符opt，代表这次询问的选择。
1、当opt为S时，表示询问的是链路维护的花费，而后给出三个正整数x，L_i，，代表声明的子树根节点（真正的子树根节点U求法见题面描述），版本号下界和版本号上界；
2、当opt为M时，表示询问的是数据传输的最大带宽（见描述），而后给出两个正整数u_i，，代表传输数据的两个节点。


输出描述:

对于每次询问，输出一行代表这次询问的答案。
示例1

输入

复制 
4 4 
1 1
2 1 6 3
2 3 9 3
2 4 5 3
S 4 3 3
M 3 4
S 1 2 3
S 4 2 3

输出

复制 
12
5
0
18

说明

第一次询问链路维护：U=((4+0)*1+1)\%4+1=2
第二次询问链路维护：U=((1+5)*1+1)\%4+1=4
第三次询问链路维护：U=((4+0)*1+1)\%4+1=2

示例2

输入

复制 
15 11
13 5
2 1 4 2
2 3 1 2
4 2 5 2
5 3 2 1
4 6 5 1
7 6 4 3
6 8 6 1
6 9 8 2
10 9 4 2
10 11 2 2
11 12 8 2
13 12 6 1
14 12 5 3
15 13 8 1
M 3 8
M 6 6
M 9 10
S 4 1 3
M 5 5
S 2 2 2
S 7 1 2
M 15 5
M 14 1
S 5 1 3
S 4 2 3

输出

复制 
1
0
4
0
0
30
0
1
2
0
0