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