Description

Company M is a very large multinational with branches or departments in many countries. To let the $n$ departments distributed around the world work together, the company built a communication network that connects the entire company.

The network consists of $n$ routers and $n-1$ high-speed fiber-optic cables. Each department has a dedicated router; all machines in the department’s local area network connect to this router, and then communicate with other departments through this communication subnet. The network structure guarantees that between any two routers there exists a direct or indirect path for communication.

The fiber-optic cables transmit data so fast that the latency on the cables can be ignored. However, due to router aging, exchanging data on the routers introduces significant delay. The communication delay between two routers is determined by the maximum exchange delay among all routers on the communication path between the two routers.

As an intern in Company M’s network division, you are asked to write a simple program to monitor the company’s network status. The program must be able to update the network status at any time (changes in routers’ data exchange delay), and, upon queries, report the delay of the $k$-th largest-delay router on the path between two routers.

Task: Your program reads from the input file the connectivity of the $n$ routers and $n-1$ fiber-optic cables, the initial data exchange delay $t_i$ of each router, and $q$ queries (or state changes). Process the $q$ queries in order; each is one of:

1. Due to an upgrade or a new fault, a router’s data exchange delay changes.
2. Query the delay of the $k$-th largest-delay router on the path between routers $a$ and $b$.

Input Format

The first line contains two integers $n$ and $q$, the total number of routers and the total number of queries.

The second line contains $n$ integers; the $i$-th number is the initial data exchange delay $t_i$ of router $i$.

The next $n-1$ lines each contain two integers $x$ and $y$, indicating there is a fiber-optic cable connecting router $x$ and router $y$.

Then follow $q$ lines, each containing three integers $k, a, b$.

If $k=0$, router $a$ changes state: its data exchange delay changes from $t_a$ to $b$.

If $k>0$, query the $k$-th largest delay among all routers on the path from $a$ to $b$ (including $a$ and $b$). Note that $a$ can be equal to $b$; in this case, the path contains only one router.

Output Format

For each query of the second type (i.e., $k>0$), output one line containing a single integer, the corresponding delay. If the routers on the path are fewer than $k$, output invalid request!.

5 5
5 1 2 3 4
3 1
2 1
4 3
5 3
2 4 5
0 1 2
2 2 3
2 1 4
3 3 5

3
2
2
invalid request!

Hint

Constraints
For $100\%$ of the testdata, $1 \le n, q \le 80000$, $0 \le k \le n$, and at any time the delay of any router is less than $10^8$.

Translated by ChatGPT 5