CSES - Kyselyt II
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Annettuna on puu, jossa on nn solmua. Jokaisella solmulla on tietty arvo. Tehtäväsi on vastata joukkoon kyselyitä seuraavaa muotoa:

  1. ilmoita pienin ja suurin arvo polulla solmujen aa ja bb välillä
  2. muuta solmun ss arvoksi xx

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua nn ja qq: solmujen määrä ja kyselyiden määrä. Solmut on numeroitu 1,2,,n1,2,\ldots,n.

Seuraavalla rivillä on nn kokonaislukua x1,x2,,xnx_1,x_2,\ldots,x_n: solmujen arvot.

Seuraavaksi syötteessä on n1n-1 riviä, jotka kuvaavat puun. Jokaisella rivillä on kaksi lukua aa ja bb. Tämä tarkoittaa, että solmujen aa ja bb välillä on kaari.

Lopuksi syötteessä on qq riviä, jotka kuvaavat kyselyt. Jokainen kysely on muotoa "11 aa bb" tai muotoa "22 ss xx".

Tuloste

Ilmoita vastaus jokaiseen kyselyyn muotoa 1.

Rajat

  • 1n,q1051 \le n,q \le 10^5
  • 1x,xi1091 \le x,x_i \le 10^9
  • 1a,b,sn1 \le a,b,s \le n

Esimerkki

Syöte:

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

Tuloste:

1 8
4 8