Chase in the Distant Kingdom

In a distant kingdom with n cities, the cities are connected by roads forming a tree. Initially, each city i has a defense value val_i. Sometimes the guardian RapiD changes the defense values along the unique path between two given cities to a specified value.

Moreover, the kingdom has a capital, which can change arbitrarily. When the capital changes to some city r, we consider the tree rooted at r. For a query on a given city u, we are interested in finding the minimum defense value among all cities in the subtree of u (i.e. all cities for which the unique path to r goes through u).

You are given the initial defense values and the roads between the cities. Then, you are given a sequence of queries of two types:

1. Update Query: 1 u v c
   Update the defense value of every city on the unique path between u and v to the value c (i.e. perform: for every city x on the path, set val_x = c).
2. Subtree Query: 2 r u
   Consider the tree rooted at city r (i.e. treat r as the capital). In this re-rooted tree, find the minimum defense value among all cities in the subtree of u (including u itself).

Note: The tree is undirected, and since it is a tree there is exactly one simple path between any two nodes. When handling a subtree query, you should first rebuild the tree’s parent-child hierarchy with the new capital r, and then compute the answer based on the subtree of u in this re-rooted tree.

Input constraints are such that a simple DFS/BFS solution will pass in all cases.

inputFormat

The first line contains two space-separated integers n and q -- the number of cities and the number of queries.

The second line contains n space-separated integers val₁, val₂, ..., val_n representing the initial defense values of the cities.

Each of the next n-1 lines contains two integers u and v indicating that there is a road between city u and city v (the tree edge).

Then q lines follow, each representing a query in one of the following two formats:

• 1 u v c : Update the defense values on the unique path between city u and city v to c.
• 2 r u : With the capital set to city r, output the minimum defense value in the subtree of city u (in the tree rooted at r).

outputFormat

For each query of type 2, output a single integer representing the minimum defense value in the specified subtree on a new line.

sample

5 5
5 4 3 2 1
1 2
2 3
3 4
3 5
2 1 3
1 4 5 10
2 3 3
1 1 2 0
2 2 2

1
4
0