Bajtazar the merchant sells bananas in Bitocja. He conducts his business from his van. Every morning, he leaves the city where he spent the night, travels to a different city, spends the whole day selling delicious fruits there, and finally stays in that city for the night. And so it goes for his whole life...

Bitocja consists of $n$ cities, numbered with integers from $1$ to $n$, connected by bidirectional roads. The road network allows travel between any two cities in exactly one way, although it may be necessary to pass through other towns to do so. Traveling along each road requires paying a toll, which depends on the road. This fee is an integer in the range from $1$ to $10^{12}$ bajtolars. Furthermore, for each city, the profit that can be earned by selling bananas there for the whole day is known – for each city, this is a number in the range from $1$ to $10^{18}$ bajtolars. Interestingly, before dawn each day, one of these values (either the toll on one road connection or the profit from selling bananas in one city) changes.

On the night before the first day, Bajtazar slept in city number $1$. Each day, he would like to travel (perhaps passing through other cities along the way) to a city, different from the previous one, that maximizes his total profit for that day. It may happen that this maximum total profit is negative. If there are multiple cities yielding exactly the same profit, Bajtazar will choose the city with the lowest number.

We know the description of all changes before each of the next $q$ days. In which city will Bajtazar sleep each of the next $q$ nights?

Input

The first line contains two integers $n, q$ ($2 \le n \le 100\,000$, $1 \le q \le 100\,000$) – the number of cities in Bitocja and the number of days during which we track Bajtazar's actions, respectively. The next line of input contains a sequence of $n$ integers $z_1, z_2, \dots, z_n$ ($1 \le z_i \le 10^{18}$); $z_i$ is the number of bajtolars that Bajtazar can earn by selling bananas in city $i$. The next $n-1$ lines describe the road connections in Bitocja. Each of these lines is of the form $a_i \ b_i \ c_i$ ($1 \le a_i, b_i \le n$, $1 \le c_i \le 10^{12}$) and means that cities $a_i$ and $b_i$ are connected by a road with an initial toll equal to $c_i$ bajtolars.

Then there are $q$ lines describing the price changes before dawn each day; the $i$-th of these lines is of one of the following forms:

• $1 \ v_i \ d_i$ ($1 \le v_i \le n$, $1 \le d_i \le 10^{18}$): means that from the dawn of the $i$-th day, the profit from selling bananas in city $v_i$ will be $d_i$.
• $2 \ a_i \ b_i \ d_i$ ($1 \le a_i, b_i \le n$, $1 \le d_i \le 10^{12}$): means that from the dawn of the $i$-th day, the cost of traveling the road connecting cities $a_i$ and $b_i$ will be $d_i$.

Output

Print a single line consisting of $q$ integers separated by single spaces; the $i$-th of these numbers should be equal to the number of the city where Bajtazar will sleep after the $i$-th day.

Examples

Input 1

4 4
10 20 30 50
1 2 5
2 3 7
2 4 57
1 3 28
1 1 25
2 3 2 1
2 2 4 13

Output 1

3 1 3 4