题目描述

题目译自 PA 2017 Runda 5 Banany

Bajtazar 是一名商人，他每天会从自己所在的城市出发，到另一个城市去贩卖香蕉。每条道路都会有一定的过路费，而作为终点的城市能获得一定收益（注意：途经点没有收益）。而每过一天，就会有一条道路的费用发生变化，或者某个城市的收益发生变化。Bajtazar 想知道当他每一天醒来后，以哪个城市作为终点获得的利润最大，而次日他会从该城市继续出发。

有 $n$ 个城市，由 $n - 1$ 条道路连接，且互相都能到达。第 $i$ 个城市有一个收益 $z_i$ ，每条边有一个费用 $w$ 。

如果从 $s$ 到 $t$ 做生意，获得的利润是

一共有 $q$ 天。

最初 Bajtazar 在 1 号城市。他每天经历了费用的变动后会前往下一个城市。他会选择获得利润最大的，如有多个相同则选择编号最小的，但他不能呆在原来的城市不走。

输入格式

第一行输入两个整数 $n$ ， $q$ 。

第二行输入 $n$ 个整数表示受益 $z_1 , z_2 , \dots , z_n$ 。

接下来 $n - 1$ 行输入边权与费用 $u\ v\ w$ 。

接下来 $q$ 行，有两种输入。

1. 输入 $1\ i\ z_i$ 表示将原本 $i$ 城市的费用替换。
2. 输入 $2\ u\ v\ w$ 表示将原本连接 $(u, v)$ 两城市的边上的费用替换。

输出格式

对于每行变化，总共输出 $q$ 组答案。表示经历变化之后， Bajtazar 的下一个目标。

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

3 1 3 4

数据范围与提示

$n, q \le 10^5$, $1 \le z_i \le 10^{18}$, $1 \le w \le 10^{12}$