Cerința

Se dă un arbore cu \(N\) noduri cu rădăcina în nodul \(1\), unde fiecare nod are o pondere asociată întreagă \(V_i\). Să se proceseze \(Q\) evenimente de următoarele \(3\) tipuri:

• \(1 \ k \ v\) – ponderea nodului \(k\) devine egală cu \(v\)
• \(2 \ a \ b\) – să se afișeze ponderea minimă al unui nod de pe drumul elementar de la nodul \(a\) la nodul \(b\).
• \(3 \ k\) – să se afișeze ponderea minimă al unui nod din subarborele cu rădăcina în nodul \(k\).

Date de intrare

Pe prima linie se vor afla numerele naturale nenule \(N\) și \(Q\), reprezentând numărul de noduri ale arborelui, respectiv numărul de evenimente care trebuie procesate.

Pe a doua linie se vor afla \(N\) numere întregi, separate prin spații, reprezentând ponderile nodului \(i\).

Pe fiecare dintre următoarele \(N-1\) linii se va afla câte o pereche de numere naturale \(a\) și \(b\), separate prin spații, reprezentând o muchie de la nodul \(a\) la nodul \(b\).

Pe fiecare dintre următoarele \(Q\) linii, se va afla câte un eveniment, în formatul de mai sus, numerele fiind separate prin spații.

Date de ieșire

Pentru fiecare eveniment de tip \(2\) sau \(3\), se va afișa pe câte o linie răspunsul evenimentului respectiv.

Restricții și precizări

• \(1 \leq N, Q \leq 200 \ 000\)
• \(1 \leq a_i, b_i, k_i \leq N\)
• \(-1 \ 000 \ 000 \ 000 \leq V_i, v_i \leq 1 \ 000 \ 000 \ 000\)
• Se recomandă folosirea fastio.

Exemplu 1:

Intrare

5 4
3 1 4 2 5
1 2
1 3
3 4
3 5
2 2 5
3 3
1 3 0
2 2 5

Ieșire

1
2
0

Exemplu 2:

Intrare

10 6
10 20 30 40 50 60 70 80 90 100
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
2 8 10
3 2
1 4 15
2 8 10
3 2
2 6 7

Ieșire

20
20
15
15
30