CSES - TCR Contest - Tree Queries
  • 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:

  1. find the minimum and maximum value on a path between nodes a and b
  2. 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