Network Delay Queries

M Corporation is a large multinational company with numerous departments located worldwide. In order to facilitate efficient collaboration among its n departments, the company has built a communication network. The network consists of n routers, each corresponding to a department, and n-1 high-speed fiber cables connecting them, guaranteeing a unique path between any two routers.

The data transfer delay across a fiber optic cable is negligible compared to the processing delay at the routers. The communication delay between any two routers is determined by the maximum data exchange delay among all routers on the path between them.

You are tasked with writing a program to monitor the network status. Initially, you are given the network structure (the connections between routers) and the initial data exchange delay times \(t_i\) for each router. Then, you are required to process q operations. Each operation is one of the following:

1. Update the data exchange delay of a specific router (due to hardware upgrades or failures).
2. Query: For two given routers a and v, determine the \(k\text{-th}\) largest delay among all routers on the simple path connecting a and v. (Note: the 1st largest delay is the maximum delay on that path.)

All formulas are given in \(\LaTeX\) format.

inputFormat

The first line contains two integers \(n\) and \(q\) --- the number of routers and the number of operations.

The second line contains \(n\) integers \(t_1, t_2, \ldots, t_n\) representing the initial data exchange delay times for each router.

The next \(n-1\) lines each contain two integers \(u\) and \(v\), indicating that there is a high-speed fiber cable connecting router \(u\) and router \(v\). It is guaranteed that these edges form a tree.

The following \(q\) lines describe the operations. Each line is in one of the following two formats:

• U x d: Update the delay time of router \(x\) to \(d\).
• Q a v k: Query the \(k\text{-th}\) largest delay among all routers on the simple path from router \(a\) to router \(v\).

You may assume that in each query, the value \(k\) is valid (i.e. the path contains at least \(k\) routers).

outputFormat

For each query operation (lines that begin with Q), output a single integer --- the \(k\text{-th}\) largest delay on the path between the two specified routers.

sample

5 5
10 20 30 40 50
1 2
1 3
3 4
3 5
Q 2 4 2
U 3 25
Q 2 4 2
Q 5 2 3
U 1 60

30
25
20