D. Master of Data Structure
time limit per test
6 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Professor Elephant is a master of data structure. Recently, he invented a perfect data structure to maintain information on a tree. He is very proud of this invention, so he prepared this problem for you.

You are given a tree with $$$n$$$ nodes. The tree nodes are numbered from $$$1$$$ to $$$n$$$. The $$$i$$$-th node has an integer value $$$w_i$$$.

Initially, $$$w_i=0$$$ for all $$$i\in [1,n]$$$.

Let's denote $$$p(u,v)$$$ as all nodes $$$x$$$ on the shortest path from the $$$u$$$-th node to the $$$v$$$-th node(include $$$u$$$ and $$$v$$$). There will be $$$m$$$ events of $$$7$$$ kinds below:

  • 1 u v k ($$$1\leq u,v\leq n,1\leq k\leq 10^5$$$), for all nodes $$$x\in p(u,v)$$$, change $$$w_x$$$ to $$$w_x+k$$$.
  • 2 u v k ($$$1\leq u,v\leq n,1\leq k\leq 10^8$$$), for all nodes $$$x\in p(u,v)$$$, change $$$w_x$$$ to $$$w_x\oplus k$$$, where "$$$\oplus$$$" denotes the bitwise XOR operation.
  • 3 u v k ($$$1\leq u,v\leq n,1\leq k\leq 10^8$$$), for all nodes $$$x\in p(u,v)$$$, change $$$w_x$$$ to $$$w_x-k$$$. Note that if $$$w_x \lt k$$$, ignore such $$$x$$$.
  • 4 u v ($$$1\leq u,v\leq n$$$), ask for the sum of $$$w_x$$$ where $$$x\in p(u,v)$$$.
  • 5 u v ($$$1\leq u,v\leq n$$$), ask for the bitwise XOR sum of $$$w_x$$$ where $$$x\in p(u,v)$$$.
  • 6 u v ($$$1\leq u,v\leq n$$$), ask for $$$\max\{w_x|x\in p(u,v)\}-\min\{w_x|x\in p(u,v)\}$$$.
  • 7 u v k ($$$1\leq u,v\leq n,1\leq k\leq 10^8$$$), ask for $$$\min\{|w_x-k||x\in p(u,v)\}$$$.

Please write a program to support these events efficiently.

Input

The first line of the input contains an integer $$$T(1\leq T\leq 5)$$$, denoting the number of test cases.

In each test case, there are two integers $$$n,m(1\leq n\leq 500000,1\leq m\leq 2000)$$$ in the first line, denoting the number of nodes and events.

For the next $$$n-1$$$ lines, each line contains two integers $$$u$$$ and $$$v$$$, denoting a bidirectional edge between vertex $$$u$$$ and $$$v$$$.

For the next $$$m$$$ lines, each line describes an event.

Output

For each query event, print a single line containing an integer, denoting the answer.

Example
Input
1
5 8
5 2
5 1
2 4
2 3
1 4 4 5
3 4 4 1
2 3 1 4
6 3 5
4 2 5
5 1 3
6 5 4
7 1 4 2
Output
0
8
0
0
2