F. Fast Tree Queries
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a tree consisting of $$$n$$$ nodes. Initially, node $$$i$$$ has the integer $$$i$$$ written on it. You need to process $$$q$$$ queries of two types:

  • + a v x — add $$$x$$$ to all integers written on a simple path from node $$$a$$$ to node $$$v$$$.
  • ? a v — calculate the xor of all integers written on a simple path from node $$$a$$$ to node $$$v$$$.
Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 10^5$$$) — the number of vertices and queries.

Each of the next $$$n - 1$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$) — edges of the tree.

Each of the next $$$q$$$ lines contains queries in the format "+ a v x" ($$$1 \le a, v \le n$$$, $$$1 \le x \le 10^4$$$) or "? a v" ($$$1 \le a, v \le n$$$).

Output

For each query of the second type, print the answer in a separate line.

Example
Input
5 6
1 2
1 3
3 4
3 5
? 2 5
+ 1 4 1
? 2 5
+ 4 5 2
? 4 5
? 1 1
Output
5
1
6
2