Binary Tree Queries

You are given a tree with n nodes numbered from 1 to n. Each node has an initial value. The tree is provided as n-1 edges connecting the nodes. You will be asked to perform q queries of the following two types:

• Update Query: 1 u x – update the value of node u to x.
• Maximum Query: 2 u v – find the maximum value along the unique path from node u to node v.

Note: The tree is rooted at node 1. The path between any two nodes is unique. For each query of type 2, print the answer on a new line.

The latex formulas used in this problem are as follows:

• The number of nodes: \(n\).
• The number of queries: \(q\).
• The update query changes the value of node \(u\) to \(x\): \( value[u] = x \).
• The maximum query returns \( \max_{w \in path(u, v)} value[w] \).

inputFormat

The input is given from stdin with the following format:

 n q
 v1 v2 ... vn
 u1 v1
 u2 v2
 ... (n-1 edges)
 query1
 query2
 ...
 queryq

Where:

• The first line contains two integers n and q — the number of nodes and the number of queries.
• The second line contains n integers representing the initial values of the nodes.
• The next n-1 lines each contain two integers representing an edge between nodes.
• The following q lines each represent a query in one of the two formats:
  • 1 u x: update the node u to value x.
  • 2 u v: output the maximum value along the path from node u to node v.

outputFormat

For each query of type 2, print the maximum value found along the unique path between the given nodes. Each answer should be output on a new line to stdout.

## sample

7 5
1 2 3 4 5 6 7
1 2
1 3
2 4
2 5
3 6
3 7
2 4 5
1 4 10
2 4 5
2 6 7
2 1 7

5
10
7
7

</p>