Postal Reform
In Flatland, a series of reforms is taking place. Recently, a road reform was implemented, ensuring that from any city in the country, there is exactly one route to reach any other city. Additionally, a reform of the wizards was completed, leaving exactly one wizard in each city. Now, the postal system is undergoing reform.
The newly established postal agency, "Ex-Fedya," offers a unique service called the collective parcel. This service allows parcels to be sent to residents of all cities along a specific route at the cost of a regular parcel. Interestingly, only the wizards of Flatland have started using this service, sending each other magical cacti in large quantities. The agency encountered an unexpected issue: all wizards reside in towers, which not only lack stairs but also vary in height over time. Therefore, to deliver a parcel to a wizard living in a tower of height h, the courier needs at least h meters of rope.
You are responsible for managing the logistics department. Based on the available data about the tower heights and their changes, you need to determine the minimum length of rope required for a courier delivering parcels between cities i and j.
Input
The first line of the input file contains the number n - the number of cities in Flatland (1 ≤ n ≤ 50000). The second line contains n positive numbers, each not exceeding 10^5 - the heights of the towers in the cities. The next n-1 lines contain two numbers u_i and v_i - the description of the i-th road, 1 ≤ u_i, v_i ≤ n, u_i ≠ v_i. The next line contains the number k - the number of queries (1 ≤ k ≤ 100000). In the following k lines, the queries are described in the following format:
A message from a wizard in city i stating that the height of his tower has become h, is in the format ! i h, 1 ≤ i ≤ n, 1 ≤ h ≤ 10^5.
A query from a courier about issuing a rope for delivering parcels to all cities on the path from i to j inclusive is in the format ? i j, 1 ≤ i, j ≤ n.
Output
For each parcel delivery query, output the minimum length of rope that needs to be given to the courier.