测试数据来自 system/1973

背景

居庸关长城。
昨天晚上我们9人狂欢，一路玩得腿脚酸痛；结果老班规定21:00到宾馆，我们弄了个23:10，然后被D到次日凌晨，两条腿基本上是废了……
于是在翻过长城之巅后，我自然地成了断后人员，即使是前面离我最近的一群也隔开了十几米山路。
这天气真是热，路上竟连个卖水的地方都没有。我用力揩了一把汗。
“你好，又见面了。”很明显是棂淡淡的问候。
我正诧异，回头一瞥，又惊奇地发现本来走在队伍前列的X和Monitor也在身边。棂解释道：“我正在追杀拉尔法，顺便把他们两个叫上了。”
棂的气色好了很多，看来前不久的那一次只是硬伤，没什么大碍。我问：“你是如何追到这个地方的？”
棂轻轻一笑，道：“你会不知道？自从你推导出拉尔法第二阈值的计算式后，拉尔法一直想找机会报复你。”
一阵异样的冷风从我身后吹来，但我身上的热气仿佛更重了，唯独脖子根发凉。
于是我回头……
X：“没想到啊没想到，你今天竟然会自己送上门来？”
棂：“你应该知道，在这个海拔上，你的第二阈值低于我们任何一个人的攻击力。”
拉尔法从嘴角流出一丝阴险的笑，说：“以前是你们打不死我，现在让你们打也打不着！黑洞术！”
我看到了时空扭曲在天空中造成的一颗颗“黑洞”，“黑洞”仿佛会呼吸似的，悬浮在空中一伸一缩，拉尔法就站在其中之一的边上。难道拉尔法也掌握了升维技术？
Monitor：“UFC光束！”
哈，Monitor的必中光束！
一道光束刺向拉尔法，但瞬间被“黑洞”吞噬，又从另一颗“黑洞”里射出，又打入另一颗“黑洞”……最终打到了战场外面，消失了。
我大吃一惊，Monitor的UFC光束可是向来必中的，这一次竟然打偏了？！
然而棂用内部数据传输系统告诉我，Monitor这一下只是试探。
Monitor掣出金鞭：“看来此阵不过如此。必杀技——劈空爆炎！”
霎时间，拉尔法背后爆出了一道火十字，它把拉尔法困在中央。有一些火苗虽然被“黑洞”吞噬，但穿过若干“黑洞”后，又回到了火十字上。看起来Monitor似乎已经摸透了这些“黑洞”，我不禁感叹道：“太神了！”
拉尔法：“算你还有点本事，不过这次是你自寻死路了。”
一阵阴风呼啸而过，“黑洞”开始剧烈地变化起来。整个火十字被“黑洞”吞噬，又被另一个“黑洞”吐出，径直朝我们打来。
X：“危险！”，随即擎出宝刀，“必杀技——白烈风震！”
身边的风开始变得像刀刃一样锋利。X和Monitor的必杀技撞到一起，掀起一股强冲击波，把我掀倒在地。我感到喉咙里有东西发咸。
冲击波过后，拉尔法毫发未损，棂也如脚下的长城般岿然不动。没人察觉到棂早已使用了固气盾。
棂用一贯沉稳的口气说：“你以为稍微玩一玩四维空间就能打赢我们？”
拉尔法：“放马过来吧，今天我要让你粉身碎骨！”
棂催动符咒，说：“你太天真了。闪电风暴！”
刹那间，所有“黑洞”，或者说一小块一小块的四维空间都被棂的符咒凝固了。
我能看出来拉尔法显然没做准备。

描述

“闪电风暴”是棂为了弥补远距离杀伤力不足的缺陷，利用由光电子效应理论支撑的符咒电子的空间灵活性，新创的远距离大面积攻击术。由于其具有巨大的有效攻击空间和不错的攻击力，因此可以实现远距离群攻和覆盖打击。“闪电风暴”由符咒催动，使用者用咒语和法力交换符咒的威力。
在刚才Monitor进攻的过程中，棂已经发现这n个“黑洞”虽然看似多变，也即通道很多，但拉尔法的四维技术也就是半瓶子醋，所以棂很轻易地在发动符咒的同时借符咒的威力钳制住了大部分通道，同时封锁了大量四维空间，只剩下n个四维空间和n-1条能量比较高的通道还勉强可以传送拉尔法自己。
随后棂在符咒的协同下对“黑洞术”发动攻击。棂、符咒和拉尔法分别在三个四维空间上，其中棂和拉尔法的位置不同。为了简化问题，我们的定义**“路”**的概念：符咒和拉尔法之间有一条经过若干条通道的**“路”**（不能重复走某条通道，即使是从不同的方向）。若棂在某一位置对拉尔法展开进攻，他需要向符咒和拉尔法之间的**“路”**传输攻击能量。这些攻击能量必须不小于棂到那条**“路”**所经过的所有通道中传输能量最大的通道的传输能量值。
当这些攻击能量被传输到**“路”**上时，符咒被激活，并释放大小为**“路”**上所有通道中传输能量最大的通道的传输能量值。棂这次攻击的攻击力，就是棂的攻击能量和符咒释放的能量的总和。
拉尔法的活动空间已经很狭小了，要想躲开这样的攻击想必要费很大力气吧。

格式

输入格式

第一行为两个整数n和position，代表初始状态已展开成四维空间的总数和符咒所处的四维空间的编号。
接下来n-1行，每行有三个整数a，b，c，代表从编号为a的四维空间到编号为b的四维空间有一条通路。
接下来一行，有一个整数q，代表所有事件的总数。
接下来q行，每行一开始有一串字符。若字符为Query，则该行还有两个整数a、b，意为询问当棂在编号为a的四维空间、拉尔法在编号为b的四维空间时，棂**传输最小攻击能量**的情况下所能造成的攻击力；若字符为Add，则该行还有两个整数a、b，意为拉尔法困兽犹斗，销减了大量法力展开了一个新的四维空间，这个新空间和a有一条通道，传送能量为b；若字符为Change，则该行还有一个整数a，意为棂为了更好地完成攻击，把符咒的位置转移到编号为a的四维空间。

输出格式

对于每一个Query操作，输出一行一个整数，表示这个Query操作的答案。

样例1

样例输入1

4 1
1 2 1
1 3 1
2 4 1
5
Query 3 4
Add 3 5
Query 3 5
Change 5
Query 1 4

样例输出1

2
5
5

限制

输入数据保证程序执行过程中总点数不超过n+tot。
* 对20%的数据，无Change操作，无Add操作，1≤n+tot≤1000，Query数量≤1000
* 对40%的数据，无Change操作，无Add操作，1≤n+tot≤100000，Query数量≤100000
* 对60%的数据，无Change操作，有Add操作，1≤n+tot≤100000，Query数量≤100000
* 对80%的数据，Change操作≤50，无Add操作，Query数量≤10000
* 对100%的数据，Change操作≤50，有Add操作，Query数量≤100000
* 对110%的数据，Change操作≤100000，有Add操作，Query数量≤100000

提示

先运行mspaint；
Query 3 4：拉尔法在4号空间，**“路”**是4->2->1，**“路”**上传送能量最高的通道是(4,2)或(2,1)，其权值为1；棂在3号空间，到**“路”**所经过的所有通道中传送能量最高的通道是(3,1)，其权值为1；所以对这一组询问，应该输出1+1=2；
Add 3 5：加入一个新的点，编号是4+1=5，与它相连的点为a=3，通道(3,5)的权值是b=5；
Query 3 5：拉尔法在5号空间，**“路”**是5->3->1，**“路”**上传送能量最高的通道是(5,3)，其权值为5；**棂在3号空间，到“路”不需经过任何通道，其权值视为0**；所以对这一组询问，应该输出5+0=5；
Change 5：把当前符咒所在的位置修改为5号结点；
Query 1 4：拉尔法在4号空间，**“路”**是4->2->1->3->5，**“路”**上传送能量最高的通道是(3,5)，其权值为5；**棂在1号空间，到“路”不需经过任何通道，其权值视为0**；所以对这一组询问，应该输出5+0=5；
【后记】
* 终于，拉尔法慌不择路，逃到了棂所在的四维空间。
棂：“做个了断吧。必杀技——紫电穿风刺！”
棂出剑，集电，电弧杀伤，干扰，刺杀。
紫电穿风刺的攻击力已经远远超过了拉尔法的第二阈值。
电光驱散了拉尔法仅存的淡淡阴气。
…………
关于拉尔法的一切，终于结束了。
不过似乎又要迟到。“等会儿我啊！”