Zadano je stablo sa \(n\) vrhova i \(q\) upita:

1. Odredi najveću moguću vrijednost izraza \(\lvert a_v - a_w \rvert\) gdje su \(v\) i \(w\) vrhovi u podstablu koje je određeno vrhom \(u\), a \(a_v\) i \(a_w\) vrijednosti pripadajućih vrhova.
2. Promijeni vrijednost vrha \(u\) u \(x\).

Vaš je zadatak ispisati odgovore na upite tipa 1. Za korijen stabla koristite vrh \(1\).

Ulazni podatci

U prvome retku nalaze se prirodni brojevi \(n\) (\(1 \leq n \leq 2 \cdot 10^5\)) i \(q\) (\(1 \leq q \leq 2 \cdot 10^5\)).

U drugome retku nalazi se \(n\) cijelih brojeva \(a_i\) (\(-10^9 \leq a_i \leq 10^9\)), početne vrijednosti vrhova.

Zatim slijedi \(n-1\) redaka \(u_i\) \(v_i\) (\(1 \leq u_i, v_i \leq n\)) koji predstavljaju neusmjeren brid između vrhova \(u_i\) i \(v_i\).

Zatim slijedi \(q\) redaka oblika \(1\) \(u\) ili \(2\) \(u\) \(x\), upiti iz zadatka (\(-10^9 \leq x \leq 10^9\)).

Izlazni podatci

Ispišite odgovore na upite tipa 1 redom kojim su zadani.

Podzadatci

Ulaz primjera 1

5 3
1 8 7 4 9
1 2
1 3
3 4
3 5
1 3
2 3 1
1 3

Izlaz primjera 1

5
8

Pojašnjenje primjera 1

U podstablu \(3\) (vrhovi \(3, 4, 5\)) rezultat \(5\) dobije se razlikom vrijednosti vrhova \(4\) i \(5\).

Ulaz primjera 2

7 4
5 6 -3 9 4 2 1
1 2
1 3
3 4
3 5
3 6
1 7
1 3
2 6 10
1 7
1 1

Izlaz primjera 2

12
0
13