香蕉商人 Bajtazar 在 Bitocja 从事香蕉贸易。他每天早上从前一天晚上住宿的城市出发，前往另一个城市，在那里卖一整天香蕉，最后留在该城市过夜。生活就这样日复一日地继续。

Bitocja 由 $n$ 个城市组成，编号为 $1$ 到 $n$，城市之间由双向道路连接。道路布局保证任意两个城市之间有且仅有一条路径，尽管可能需要经过其他城市。每条道路的通行都需要支付一定的过路费，费用取决于道路，是一个 $1$ 到 $10^{12}$ 之间的整数。此外，每个城市都有一个已知的利润值，即在该城市卖一整天香蕉所能获得的利润，该值是 $1$ 到 $10^{18}$ 之间的整数。有趣的是，每天黎明前，其中一个价格（要么是某条道路的过路费，要么是某个城市的香蕉销售利润）会发生变化。

在第一天之前的晚上，Bajtazar 住在城市 $1$。他每天都想前往一个与前一天不同的城市，以最大化当天的总利润（即：在该城市卖香蕉的利润减去前往该城市的路径上的总过路费）。这个最大总利润可能是负数。如果存在多个能带来相同最大利润的城市，Bajtazar 会选择编号最小的城市。

我们已知接下来 $d$ 天内每天发生的所有变化。请问在接下来的 $d$ 个夜晚，Bajtazar 分别会住在哪个城市？

输入格式

第一行包含两个整数 $n, q$ ($2 \le n \le 100\,000, 1 \le q \le 100\,000$)，分别表示 Bitocja 的城市数量和我们追踪 Bajtazar 行踪的天数。 输入下一行包含 $n$ 个整数 $z_1, z_2, \dots, z_n$ ($1 \le z_i \le 10^{18}$)，其中 $z_i$ 表示 Bajtazar 在城市 $i$ 卖香蕉能获得的利润。 接下来的 $n-1$ 行描述了 Bitocja 的道路连接。每行格式为 $a_i, b_i, c_i$ ($1 \le a_i, b_i \le n, 1 \le c_i \le 10^{12}$)，表示城市 $a_i$ 和 $b_i$ 之间有一条初始过路费为 $c_i$ 的道路。

随后有 $q$ 行，描述了每天黎明前的价格变化；第 $i$ 行属于以下两种格式之一： $1 \ v_i \ d_i$ ($1 \le v_i \le n, 1 \le d_i \le 10^{18}$)：表示从第 $i$ 天黎明开始，在城市 $v_i$ 卖香蕉的利润变为 $d_i$。 $2 \ a_i \ b_i \ d_i$ ($1 \le a_i, b_i \le n, 1 \le d_i \le 10^{12}$)：表示从第 $i$ 天黎明开始，连接城市 $a_i$ 和 $b_i$ 的道路通行费变为 $d_i$。

输出格式

输出一行，包含 $q$ 个整数，用空格隔开；第 $i$ 个整数表示 Bajtazar 在第 $i$ 天后过夜的城市编号。

样例

输入 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

输出 1

3 1 3 4