26630번 - Banany 다국어

Kupiec Bajtazar jest sprzedawcą bananów w Bitocji. Handel prowadzi ze swojej furgonetki. Każdego dnia rankiem wyjeżdża z miasta, w którym nocował, jedzie do innego miasta, tam cały dzień prowadzi sprzedaż smakowitych owoców i ostatecznie pozostaje w tym mieście i nocuje w nim. I tak całe życie. . .

Bitocja składa się z n miast, ponumerowanych liczbami całkowitymi od 1 do n, połączonych dwukierunkowymi drogami. Układ dróg pozwala na przejazd pomiędzy dwoma dowolnymi miastami na dokładnie jeden sposób, choć być może trzeba w tym celu przejechać przez inne miejscowości. Przejazd każdą drogą wymaga uiszczenia opłaty drogowej, zależnej od drogi. Opłata ta jest liczbą całkowitą z przedziału od 1 do 1012 bajtolarów. Ponadto, dla każdego miasta znany jest zysk, który można osiągnąć, sprzedając w nim przez cały dzień banany – dla każdego miasta jest to liczba z przedziału od 1 do 10¹⁸ bajtolarów. Co ciekawe, przed świtem każdego dnia jedna z tych cen (albo wysokość opłaty drogowej na jednym połączeniu drogowym, albo zysk wynikający ze sprzedaży bananów w jednym mieście) ulega zmianie.

Nocą przed pierwszym dniem Bajtazar spał w mieście numer 1. Każdego dnia chciałby pojechać (być może przejeżdżając po drodze przez inne miasta) do takiej, innej niż poprzednio, miejscowości, by zmaksymalizować łączny zysk tego dnia. Może się zdarzyć, że ten maksymalny łączny zysk będzie ujemny. Jeśli istnieje wiele miejscowości przynoszących dokładnie taki sam zysk, Bajtazar wybierze miasto o najniższym numerze.

Znamy opis wszystkich zmian przed każdym z najbliższych d dni. W której miejscowości będzie spał Bajtazar każdej z następnych d nocy?

Pierwszy wiersz zawiera dwie liczby całkowite n, q (2 ≤ n ≤ 100 000, 1 ≤ q ≤ 100 000) – odpowiednio liczbę miast w Bajtocji oraz liczbę dni, podczas których śledzimy poczynania Bajtazara. Następny wiersz wejścia zawiera ciąg n liczb całkowitych z₁, z₂, . . . , z_n (1 ≤ z_i ≤ 10¹⁸); z_i to liczba bajtolarów, które Bajtazar może zarobić, sprzedając banany w mieście i. Kolejnych n−1 wierszy opisuje połączenia drogowe w Bajtocji. Każdy z tych wierszy jest postaci a_i b_i c_i (1 ≤ a_i, b_i ≤ n, 1 ≤ c_i ≤ 10¹²) i oznacza, że miasta a_i oraz b_i są połączone drogą o początkowej opłacie drogowej równej c_i bajtolarów.

Potem następuje q wierszy opisujących zmiany cen przed świtem każdego dnia; i-ty spośród tych wierszy jest jednej z postaci:

• 1 v_i d_i (1 ≤ v_i ≤ n, 1 ≤ d_i ≤ 10¹⁸): oznacza, że od świtu i-tego dnia zysk ze sprzedaży bananów w mieście v_i wynosić będzie d_i;
• 2 a_i b_i d_i (1 ≤ a_i, b_i ≤ n, 1 ≤ d_i ≤ 10¹²): oznacza, że od świtu i-tego dnia koszt przejazdu drogą łączącą miasta a_i oraz b_i wynosić będzie d_i.

Wypisz pojedynczy wiersz złożony z q liczb całkowitych pooddzielanych pojedynczymi odstępami; i-ta z tych liczb powinna być równa numerowi miasta, w którym będzie nocował Bajtazar po i-tym dniu.