Cerința

Se dă un arbore cu $N$ noduri înrădăcinat în nodul $1$, unde fiecare nod are un pondere asociat întreg $V_i$. Să se proceseze $Q$ evenimente de următoarele $3$ tipuri:

• $1kv$ – ponderele nodului $k$ devine egal cu $v$
• $2ab$ – să se afișeze ponderele minim al unui nod de pe drumul simplu de la nodul $a$ la nodul $b$.
• $3k$ – să se afișeze ponderele minim al unui nod din subarborele înrădăcinat î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 ponderele 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\le N,Q\le 200000$
• $1\le a_i,b_i,k_i\le N$
• $-1000000000\le V_i,v_i\le 1000000000$
• 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