Postal Reform

Flatland is going through a season of reforms. Recently the roads were reformed so that every city can be reached from any other city, and there is exactly one simple path between any two cities. The wizards were also reformed, so each city has exactly one wizard. Now the postal system is being reformed.

The newly founded postal agency "Ex-Fedya" offers a unique service called the collective parcel. This service lets you send parcels to the residents of all cities on some path, at the price of a regular parcel. Surprisingly, only the wizards of Flatland have started using it, and they send each other magic cacti in large numbers.

The agency has run into an unexpected problem. All wizards live in towers, and they do not build stairs to them. On top of that, they change the height of their towers from time to time. So to deliver a parcel to a wizard who lives in a tower of height $h$, the courier must carry at least $h$ meters of rope.

You are in charge of logistics. Given the tower heights and their changes, you must find the minimum length of rope that must be issued to a courier who delivers parcels between cities $i$ and $j$.

The first line contains $n$, the number of cities in Flatland ($1 \le n \le 50000$). The second line contains $n$ positive integers, none exceeding $10^5$, the tower heights in the cities. The next $n-1$ lines each contain two integers $u_i$ and $v_i$, describing the $i$-th road ($1 \le u_i, v_i \le n$, $u_i \ne v_i$). The next line contains $k$, the number of queries ($1 \le k \le 100000$). Each of the next $k$ lines is one of the following:

• A notice from the wizard in city $i$ that the height of his tower is now $h$, in the form $!$ $i$ $h$ ($1 \le i \le n$, $1 \le h \le 10^5$).
• A request from the courier for rope to deliver parcels to every city on the path from $i$ to $j$, inclusive, in the form $?$ $i$ $j$ ($1 \le i, j \le n$).

For each delivery query, print the minimum length of rope that must be issued to the courier.