Path Queries II

Source: CSES

Version: Phuoc Hung OJ Extended

Problem

You are given a tree with a value on every vertex. Support point updates and queries asking for the maximum vertex value on the path between two vertices.

Input

The first line contains $n$ and $q$. The second line contains the $n$ initial vertex values. The next $n-1$ lines contain the tree edges. Each of the following $q$ lines is one of:

• 1 s x: set the value of vertex $s$ to $x$.
• 2 a b: query the maximum value on the path from $a$ to $b$.

Output

For each operation of type 2, print the maximum value on the requested path.

Subtasks

Subtask 1 (20%)

• The tree size and number of operations are at most 20.
• All other conditions are the same as Subtask 3.

Subtask 2 (30%)

• The tree size and number of operations are at most 2000.
• All other conditions are the same as Subtask 3.

Subtask 3 (50%)

• $1\le n,q\le2\cdot10^5$.
• $1\le v_i,x\le10^9$.

Example

Input

1 11
142
1 1 816
2 1 1
1 1 696
1 1 902
2 1 1
1 1 791
1 1 73
2 1 1
1 1 361
1 1 711
2 1 1

Output

816
902
73
711

Explanation

Every queried path contains only vertex 1, so the answer is its value at that moment.