Dynamic Banana Trading on a Tree

Bajtazar is a merchant who travels between cities on a tree structure to trade bananas. There are n cities connected by n-1 roads; every road has an associated toll fee and every city has a profit value. The profit obtained when starting from city s and ending at city t is computed as

$$ \textstyle z_t - \sum_{e \in \mathrm{Path}(s,t)}w(e)$$

Note that only the destination city gives profit (z_t), while all intermediate tolls are subtracted. Initially, Bajtazar is at city 1. Over the course of q days, either a road's toll fee or a city's profit changes. After each day’s update, starting from the current city s, Bajtazar must choose a destination city (different from s) that maximizes his profit. In the event of a tie, he chooses the city with the smallest index. After his journey on that day, his new starting city for the next day becomes the destination city just chosen.

Your task is to process the updates and, for each day, output the index of the chosen destination city.

Input constraints: The tree is connected. You may assume that n and q are small enough (for instance, ≤ 1000) so that a simple DFS from the current city on each day is sufficient.

Note on formulas: All formulas in the problem statement are in LaTeX format.

inputFormat

The first line contains two integers n and q, the number of cities and the number of days, respectively.

The second line contains n integers: z1, z2, ..., zn, where zi is the profit for city i.

The next n - 1 lines each contain three integers u v w indicating that there is an undirected road between cities u and v with toll fee w.

The following q lines each describe a day's update. Each update is in one of the following two formats:

• 1 u v new_w — The toll fee on the road between cities u and v is updated to new_w.
• 2 p new_z — The profit of city p is updated to new_z.

After performing the update, from the current starting city s, select the destination city t (t \neq s) that maximizes the profit:

$$ \textstyle z_t - \sum_{e \in \mathrm{Path}(s,t)}w(e)$$

If there is a tie, choose the city with the smallest index. Then, print the index of the chosen city and set s = t for the next day.

outputFormat

For each day, output on a separate line the index of the destination city chosen after processing that day’s update.

sample

3 3
10 5 7
1 2 3
1 3 4
2 1 20
1 1 3 1
2 2 10

3
1
2

</p>