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:

• \(1 \ k \ v\) – ponderele nodului \(k\) devine egal cu \(v\)
• \(2 \ a \ b\) – să se afișeze ponderele minim al unui nod de pe drumul simplu de la nodul \(a\) la nodul \(b\).
• \(3 \ k\) – 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 \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