哇!你在帮助火箭队方面做得非常出色,他们成功地捕获了巴什派来的所有神奇宝贝。喵喵是火箭队的一员,已经掌握了人类语言,现在也想成为编程大师。如果巴什能够回答他的问题,他同意释放神奇宝贝。
最初,Meowth 为 Bash 提供了一棵包含 n 个节点的加权树和一个序列 a1, a2..., an,它是 1, 2, ..., n 的排列。现在,Mewoth 进行以下形式之一的 q 查询:
- 1 l r v:表示 Bash 应该报告 $$\sum_{i=l}^{r} dist(a_i, v)$$,其中 dist(a, b) 是给定树中从节点 a 到节点 b 的最短路径的长度。
- 2 x:表示 Bash 应该按给定顺序交换 ax 和 ax + 1。这个新序列用于以后的查询。
帮助 Bash 回答问题!
输入
第一行包含两个整数 n 和 q (1 ≤ n ≤ 2·105, 1 ≤ q ≤ 2·105) - 分别是树中的节点数和查询数。
下一行包含 n 个空格分隔的整数 - 序列 a1, a2, ..., an 是 1, 2, ..., n 的排列。
接下来的 n - 1 行中的每一行都包含三个空格分隔的整数 u、v 和 w,表示节点 u 和权重为 w 的节点 v 之间存在无向边(1 ≤ u,v ≤ n,u ≠ v,1 ≤ w ≤ 106)。保证给定的图是一棵树。
每个查询由两行组成。第一行包含单个整数 t,指示查询的类型。下一行包含查询的描述:
- t = 1:第二行包含三个整数 a、b 和 c (1 ≤ a, b, c < 230),可以使用以下给出的公式生成 l、r 和 v: $$l = (ans_{i-1} \bmod 2^{30}) \oplus a$$, $$r = ( ans_{i-1} \bmod 2^{30} ) \oplus b$$, $$v = (ans_{i-1} \bmod 2^{30}) \oplus c$$。
- t = 2:第二行包含单个整数 a (1 ≤ a < 230),使用它可以使用下面给出的公式生成 x:$$x = (ans_{i-1} \bmod 2^{30}) \oplus a$$。
ansi 是第 i 个查询的答案,假设 ans0 = 0。如果第 i 个查询的类型为 2,则 ansi = ansi - 1。可以保证:
- 对于类型 1 的每个查询:1 ≤ l ≤ r ≤ n,1 ≤ v ≤ n,
- 对于类型 2 的每个查询:1 ≤ x ≤ n - 1。
$$\bigcirc$$ 运算表示按位异或。
输出
对于类型 1 的每个查询,在单独的行中输出一个整数,表示查询的答案。
示例
输入 #1
5 5 4 5 1 3 2 4 2 4 1 3 9 4 1 4 4 5 2 1 1 5 4 1 22 20 20 2 38 2 39 1 36 38 38
输出 #1
23 37 28
注意
在示例中,实际查询如下:
- 1 1 5 4
- 1 1 3 3
- 2 3
- 2 2
- 1 1 3 3