- Time limit: 1.00 s
- Memory limit: 512 MB
You are given a tree that contains n nodes. Each node has a value. Your task is to process following queries:
- find the minimum and maximum value on a path between nodes a and b
- update the value of node s to x
Input
The first input line has two integers n and q: the number of nodes and the number of queries. The nodes are numbered 1,2,\ldots,n.
The next line contains n integers x_1,x_2,\ldots,x_n: the values of the nodes.
Then, there are n-1 lines that describe the tree. Each line contains two integers a and b. This means that there is an edge between nodes a and b.
Finally, there are q lines that describe the queries. Each query is either "1 a b" or "2 s x".
Output
Print the answer to each query of type 1.
Constraints
- 1 \le n,q \le 10^5
- 1 \le x,x_i \le 10^9
- 1 \le a,b,s \le n
Example
Input:
5 3 4 8 1 5 4 1 2 1 3 3 4 3 5 1 2 5 2 3 7 1 2 5
Output:
1 8 4 8