Tree Subtree Maximum Queries

You are given a tree with N nodes. Each node is assigned an initial integer value. The tree is rooted at node 1. You need to process Q queries. There are two types of queries:

• Update Operation (Type 1): Given a node x and an integer k, update the value of node x to k.
• Query Operation (Type 2): Given a node x, output the maximum value in the subtree of x (i.e. including x and all its descendants in the rooted tree).

Note: After each update, the tree's subtree maximum values need to be recalculated. The answer to a query is defined as:

\(\max_{y \in \text{subtree}(x)} value_y\)

You are required to process the queries and print the result for each query of type 2 on a new line.

inputFormat

The input is given from stdin as follows:

1. An integer N representing the number of nodes in the tree.
2. N space-separated integers representing the initial values of nodes 1 through N respectively.
3. N-1 lines follow, each containing two integers u and v which indicate there is an undirected edge between node u and node v.
4. An integer Q representing the number of queries.
5. Q lines follow, each describing a query. A query can be either:
• If the query begins with 1: It is of the form: 1 x k, meaning update the value of node x to k.
• If the query begins with 2: It is of the form: 2 x, meaning output the maximum value in the subtree rooted at node x.

outputFormat

For each query of type 2, output a single line containing the maximum value in the specified subtree.

## sample

5
5 3 8 6 1
1 2
1 3
3 4
3 5
4
2 3
1 3 10
2 1
1 1 2

8
10

</p>