随着人类补完计划的成功，人类也制造出了它们所拥有的第一个同样也是唯一一个超级士兵——战争中凋敝的国力已经无法为再一次的人体改造提供足够的能源与人力。但是，就这唯一的超级士兵，在接下来的战争中，也给跳蚤国带去了巨大的损失。

在经历了漫长的僵持后，终于，长时间的战争带来的损伤让双方都难以接受了。于是，双方决定以王牌对王牌决斗的形式，来结束这场毫无意义的争斗。

那一天，是最强跳蚤与超级士兵第一次相遇同时也是最后一次相遇：他们带来了无愧于他们最强之名的旷世对决。最终，最强跳蚤的子弹贯穿了超级士兵的咽喉，而超级士兵在生命尽头时斩出的一刀也准确无误地击中了最强跳蚤唯一的弱点——脚踵。重伤的最强跳蚤在惊慌之中全力一跳，消失在了天空中，之后再也没有人见到过它的踪影。

这场决斗以平局的形式告终，而双方又都不肯进行让步，所以本该熄灭的战火又蔓延开来。然而，回到原点的战争中，失去了最强跳蚤的跳蚤国再一次落在了下风。

终于，战争的损耗让跳蚤国再也没有力量维持这一场轰轰烈烈的远征。在最后的最后，跳蚤国王决定最后尝试一次智取：他命令手下的工匠制作一个巨大的思考熊，并将几百名最精锐的跳蚤士兵藏身其中，接着他假装退兵，在人们将思考熊当做战利品带进城里后，里应外合夜袭 pion 吧，力求一击而中。

然而，现实往往没有那么简单。跳蚤国王希望可以选择一种最妥当的方案，来提高这最后一次努力的成功率，于是他要对计划的进行进行反复的模拟与推敲。

pion 吧中有 $n$ 个居住区，这些居住区被 $n-1$ 条双向道路连成了一个树形结构（即任意两个居住区之间有且只有一条简单路径）。每一条道路都有一个安全度 $w_i$（$w_i$ 可能为负数表示这条路非常危险）。跳蚤士兵经过一条路径的安全度为经过的所有道路的安全度之和。

在分析的过程中，跳蚤国王有一个序列 $A$ 表示可以进行接应的居住区编号，最开始序列 $A$ 为空。

接着跳蚤国王进行了 $m$ 次模拟操作，每一次操作都是一下三种事件之一：

1. 发现了一个新的接应点，它是编号为 $x$ 的居住区，跳蚤国王把它放在了序列 $A$ 的最后。
2. 序列末尾的接应点被人类发现并捣毁，即序列末尾的接应点被删除。
3. 跳蚤国王假设只有当前序列中第 $l$ 个到第 $r$ 个（按照插入时间从小到大编号）接应点可以使用且思考熊被人类放在了第 $x$ 号居住区。跳蚤士兵们需要选择一个可以使用的接应点并沿着唯一的那条简单路径赶到那儿接应跳蚤大军。跳蚤国王想要知道所有选择中最大的安全度是多少。

因为跳蚤国王想要模拟尽可能多的情况，所以运算量变得相当的大。于是他希望由你——不堪受辱刚刚从 pion 吧叛逃出来的人类，来帮他进行计算。

输入格式

第一行两个正整数 $n$ 和 $m$ 分别表示居住区的个数和操作个数。

接下来 $n-1$ 行每行三个整数 $u_i,v_i,w_i(1\le u_i,v_i\le n)$ 描述树上的一条边权为 $w_i$ 的连接点 $u_i$ 和 $v_i$ 的边。

接下来 $m$ 行，每行第一个整数 $t_i$ 描述操作种类：

1. 如果 $t_i=1$，那么接下来一个整数 $x_i$，表示加入的居住区编号。
2. 如果 $t_i=2$，那么表示删除最后一次加入的居住区。
3. 如果 $t_i=3$，那么接下来三个整数 $l_i,r_i,x_i$，表示一次询问。

因为一些原因，本题对第一种操作中的 $x_i$ 和第三种操作中的 $l_i,r_i,x_i$ 进行了加密，假设输入的数是 $\text{num}$，上一次询问的答案是 $\text{last}$（初始为0），那么解密方式如下：

1. 在读入 $x_i$ 的时候，$x_i$ 的实际值等于 $(\text{num}\text{xor}|\text{last}|)\text{mod}n+1$。
2. 在读入 $l_i,r_i$ 的时候，它们的实际值等于 $(\text{num}\text{xor}|\text{last}|)\text{mod}N+1$，其中 $N$ 为当前的数列长度。注意如果解密时出现了 $l_i>r_i$ 的情况，你需要自行交换 $l_i$ 和 $r_i$ 的值，保证比赛时的数据中不会出现这种情况。

其中 $\text{xor}$ 表示在二进制下逐位异或。

数据保证有 $0\le \text{num}\le 2\times {10}^9$。

输出格式

对每一次询问输出一行一个整数，表示答案。

因为这题输入输出数据较为庞大，请选手注意减少读入输出时使用的时间。

样例一

input

5 10
1 2 -269
2 3 27
3 4 -185
4 5 252
1 2
3 0 0 3
3 185 185 185
2
1 240
2
1 246
1 246
3 242 242 241
2

output

-185
-242
252

explanation

第一次询问时，序列为 $3$，答案是树上 $3$ 到 $4$ 的距离，即 $-185$。

第二次询问时，序列为 $3$，答案是树上 $3$ 到 $1$ 的距离，即 $-242$。

第三次询问时，序列为 $55$，答案是树上 $5$ 到 $4$ 的距离，即 $252$。

样例二

见样例数据下载，该数据满足 $n,m\le 1000$。

样例三

见样例数据下载，该数据满足 $n,m\le 100000$ 且不存在第二类操作。

样例四

见样例数据下载，该数据满足 $n,m\le 100000$ 且 $w_i\ge 0$。

样例五

见样例数据下载，该数据满足 $n,m\le 100000$。

限制与约定

由于一些原因，本题使用捆绑测试。每个子任务有若干个测试点，分为 $6$ 个子任务，你只有通过一个子任务的所有测试点才能得到这个子任务的分数。

对于所有数据，有 $0\le |w_i|\le 300$。

时间限制：$4\mathtt{\text{s}}$

空间限制：$300\mathtt{\text{MB}}$

下载

样例数据下载

后记

最终，跳蚤国王的计策成功了：他凭借着一条思考熊计，攻破了 pion 吧，结束了这场旷日持久的战争。

然而，出乎他的意料的是，pion 吧的管理层——吧主、小吧主甚至是视频小编、图片小编都在一夜之间失踪了——pion 吧这个曾经无比辉煌的大都市成为了无主之地，混乱不堪。

跳蚤国王计上心头，他化名成了“伏特跳蚤国王”，伪装成了人类并打入了他们内部，创建了一个名叫 Universal OJ 用户群的神秘组织，并利用他在 pion 吧当吧主时的管理经验与人脉关系，将 pion 吧最后残存的力量拉入他的组织并秘密地加以监视与控制。

多年之后的现在，人类的文明以 Universal OJ 用户群为中心，又一次达到了鼎盛，而原来强大的跳蚤帝国，却在那场战争后突然地从历史的舞台中消失了。人们都沉浸在了繁荣的经济与文化带来的高质量生活中，却很少有人依然记得多少年前的那一场战争以及那一场战争中真正的赢家...