Inaho was thinking of a tree problem, when he came up with this rather beautiful problem!

Given a tree originally rooted at \(1\) containing \(N\) nodes each with a value \(v_i\) and an arbitrary value \(K\), support \(Q\) of following operations:

`1 R`

Reroot the tree so that node \(R\) is the root.`2 a b`

Print the highest common ancestor of nodes \(a\) and \(b\).`3 a b`

Print the sum of all nodes' \(v_i\) on the path from \(a\) to \(b\), inclusive.`4 a b`

Print the product of all nodes' \(v_i\) on the path from \(a\) to \(b\), inclusive, modulo \(10^9+7\).`5 a b`

Print the minimum of all nodes' \(v_i\) on the path from \(a\) to \(b\), inclusive.`6 a b`

Print the maximum of all nodes' \(v_i\) on the path from \(a\) to \(b\), inclusive.`7 a b`

Print the greatest common divisor of all nodes' \(v_i\) on the path from \(a\) to \(b\), inclusive.`8 a b`

Print the bitwise AND of all nodes' \(v_i\) on the path from \(a\) to \(b\), inclusive.`9 a b`

Print the bitwise OR of all nodes' \(v_i\) on the path from \(a\) to \(b\), inclusive.`10 a b`

Print the bitwise XOR of all nodes' \(v_i\) on the path from \(a\) to \(b\), inclusive.`11 a b`

Print the number of nodes whose \(v_i > K\) on the path from \(a\) to \(b\), inclusive.`12 a b`

Print the number of nodes whose \(v_i < K\) on the path from \(a\) to \(b\), inclusive.`13 a b`

Print the value \(v_i\) that minimizes \(v_i - K\), and \(v_i > K\) of all nodes on the path from \(a\) to \(b\), inclusive. Print \(K\) if there is no such node where \(v_i > K\).`14 a b`

Print the value \(v_i\) that minimizes \(K - v_i\), and \(v_i < K\) of all nodes on the path from \(a\) to \(b\), inclusive. Print \(K\) if there is no such node where \(v_i < K\).

It is guaranteed \(1 \le a, b, R \le N\).

#### Input Specification

The first line will contain three space-separated integers, \(N, Q, K\ (1 \le N, Q \le 10^5, 1 \le K \le 1\ 000)\), the number of nodes, the number of operations, and the arbitrary value \(K\), respectively.

The second line will contain \(N\) space-separated integers, \(v_1, v_2, \ldots, v_N\ (1 \le v_i \le 1\ 000)\), the values of each node.

The next \(N-1\) lines will each contain two space-separated integers, \(a, b\ (1 \le a, b \le N)\), indicating that nodes \(a\) and \(b\) are connected by an edge. It is guaranteed the entire tree is connected.

The next \(Q\) lines will each contain a valid operation as defined above.

#### Output Specification

For each operation that requires something to be outputted (everything except operation \(1\)), print the answer on its own line.

#### Sample Input

```
6 15 3
4 10 2 2 5 1
1 2
1 3
3 4
3 5
3 6
2 1 2
1 3
2 1 2
3 2 5
4 4 1
5 1 6
6 3 5
7 2 3
8 3 4
9 5 3
10 6 2
11 2 6
12 3 1
13 4 5
14 1 2
```

#### Sample Output

```
1
3
21
16
1
5
2
2
7
13
2
1
5
3
```

## Comments