给定一棵包含 $n$ 个节点的树。初始时，节点 $i$ 上写着整数 $i$。你需要处理 $q$ 次查询，查询分为以下两种类型：

• + a v x — 将节点 $a$ 到节点 $v$ 的简单路径上所有节点上的整数加上 $x$。
• ? a v — 计算节点 $a$ 到节点 $v$ 的简单路径上所有节点上的整数的异或和。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 10^5$)，分别表示顶点数和查询数。

接下来的 $n - 1$ 行，每行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n$)，表示树的边。

接下来的 $q$ 行，每行包含一个查询，格式为 + a v x ($1 \le a, v \le n, 1 \le x \le 10^4$) 或 ? a v ($1 \le a, v \le n$)。

输出格式

对于每种类型为 ? 的查询，在单独的一行中输出答案。

样例

输入格式 1

5 6
1 2
1 3
3 4
3 5
? 2 5
+ 1 4 1
? 2 5
+ 4 5 2
? 4 5
? 1 1

输出格式 1

5
1
6
2