바나나

상인 바이타자르는 비토시아에서 바나나를 파는 사람이다. 그는 자신의 밴을 몰고 장사한다. 매일 아침 전날 밤을 보낸 도시를 떠나 다른 도시로 간다. 그곳에서 하루 종일 맛있는 과일을 팔고, 마지막에는 그 도시에 머물러 밤을 보낸다. 평생 이렇게 산다...

비토시아에는 1번부터 $n$번까지 번호가 붙은 $n$개의 도시가 있고, 도시들은 양방향 도로로 연결되어 있다. 어떤 두 도시든 정확히 한 가지 방법으로 오갈 수 있으며, 그 사이에 다른 도시를 거쳐야 할 수도 있다. 도로마다 통행료가 정해져 있고, 지날 때마다 그 금액을 낸다. 통행료는 1부터 $10^{12}$ 사이의 정수 바이톨라르다. 도시마다 하루 동안 바나나를 팔아서 얻는 수익도 정해져 있다. 수익은 1부터 $10^{18}$ 사이의 정수다. 흥미롭게도 매일 새벽 가격 정보 하나가 바뀐다. 바뀌는 것은 도로 하나의 통행료이거나 도시 하나의 판매 수익이다.

첫날 밤 바이타자르는 1번 도시에서 잔다. 매일 그는 전날 머문 도시와 다른 도시 하나를 골라 그곳까지 간다(중간에 다른 도시를 지나도 된다). 그날의 총 수익이 가장 크도록 도시를 고른다. 이 최대 총 수익은 음수일 수도 있다. 최대 수익을 주는 도시가 여럿이면 번호가 가장 작은 도시를 고른다.

앞으로 $q$일 동안의 가격 변경 내역을 모두 알고 있다. 각 날 밤 바이타자르가 자는 도시를 구하라.

첫 줄에 정수 $n$과 $q$가 주어진다($2 \le n \le 100000$, $1 \le q \le 100000$). 다음 줄에는 $n$개의 정수 $z_1, z_2, ..., z_n$이 주어진다. $z_i$는 도시 $i$에서 바나나를 팔아 얻는 수익이다($1 \le z_i \le 10^{18}$). 이어지는 $n-1$개의 줄은 도로를 나타낸다. 각 줄에는 $a_i$, $b_i$, $c_i$가 주어지며, 도시 $a_i$와 $b_i$가 통행료 $c_i$인 도로로 연결되어 있다는 뜻이다($1 \le a_i, b_i \le n$, $1 \le c_i \le 10^{12}$).

그 다음 $q$개의 줄에 매일 새벽의 가격 변경이 주어진다. 각 줄은 다음 둘 중 하나다.

• 1 v d ($1 \le v \le n$, $1 \le d \le 10^{18}$): 그날 새벽부터 도시 $v$에서 바나나를 팔아 얻는 수익이 $d$가 된다.
• 2 a b d ($1 \le a, b \le n$, $1 \le d \le 10^{12}$): 그날 새벽부터 도시 $a$와 $b$를 잇는 도로의 통행료가 $d$가 된다.

$q$개의 정수를 한 줄에 공백으로 구분해 출력한다. $i$번째 정수는 $i$번째 변경이 적용된 뒤 바이타자르가 밤을 보내는 도시 번호다.