Yasya 在森林里散步,无意中发现了一棵有 $$$n$$$ 个顶点的树。树是一个无环的连通无向图。
在树旁边,女孩发现了一份古老的手稿,上面写着$$$m$$$的疑问。查询可以有两种类型。
第一种类型的查询由整数 $$$y$$$ 描述。树中每条边的权重由该边的权重与整数 $$$y$$$ 的按位异或替换。
第二种类型由顶点$$$v$$$和整数$$$x$$$描述。 Yasya 选择一个顶点 $$$u$$$ ($$$1 \le u \le n$$$, $$$u \neq v$$$) 并在树中绘制一条从 $$$v$$$ 到 $$$u$$$ 的双向权重 $$$x$$$ 边。
然后 Yasya 在结果图中找到一个简单的循环,并计算其中所有边的按位异或。她想要选择一个顶点 $$$u$$$ 使得计算值最大。该计算值将是查询的答案。可以证明这样的循环存在并且在给定约束下是唯一的(与 $$$u$$$ 的选择无关)。如果 $$$v$$$ 和 $$$u$$$ 之间已经存在边,则简单的循环是路径 $$$v \to u \to v$$$。
请注意,第二种类型的查询是在心理上执行的,这意味着树在其之后不会发生任何变化。
帮助 Yasya 回答所有问题。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$, $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 2 \cdot 10^5$$$) — 树中的顶点数和查询数。
每个测试用例接下来的 $$$n - 1$$$ 行包含三个整数 $$$v$$$、$$$u$$$、$$$w$$$ ($$$1 \le v, u \le n$$$, $$$1 \le w \le 10^9$$$) — 树中某些边的末端及其权重。
保证给定的边集形成一棵树。
每个测试用例接下来的 $$$m$$$ 行描述了查询:
- ^ $$$y$$$ ($$$1 \le y \le 10^9$$$) — 第一类型查询的参数;
- ? $$$v$$$ $$$x$$$ ($$$1 \le v \le n$$$, $$$1 \le x \le 10^9$$$) — 第二种类型查询的参数。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。 $$$m$$$ 也能保证同样的效果。
输出
对于每个测试用例,输出第二类型查询的答案。
示例
输入 #1
2 3 7 1 2 1 3 1 8 ^ 5 ? 2 9 ^ 1 ? 1 10 ^ 6 ? 3 1 ? 2 9 5 6 1 2 777 3 2 2812 4 1 16 5 3 1000000000 ^ 4 ? 3 123 ? 5 1000000000 ^ 1000000000 ? 1 908070 ? 2 1
输出 #1
13 15 11 10 1000000127 2812 999756331 999999756
输入 #2
3 8 4 8 6 3 6 3 4 2 5 4 7 6 2 7 1 10 4 1 4 5 1 2 ^ 4 ^ 7 ? 7 8 ? 4 10 5 6 3 1 4 2 3 9 4 3 6 5 2 10 ? 5 7 ^ 1 ^ 8 ? 4 10 ? 1 9 ? 3 6 4 2 2 1 4 4 3 5 2 3 4 ^ 13 ? 1 10
输出 #2
14 13 13 8 11 11 10