Syötteenä annetaan puu, jonka jokaisessa solmussa on jokin luku. Tehtäväsi on vastata seuraavanlaisiin kyselyihin: Jos järjestetään polulla solmusta u solmuun v olevat luvut pienimmästä suurimpaan, mikä on järjestyksessä k:s luku?

Syöte

Ensimmäisellä rivillä on kaksi lukua n ja q, puun solmujen määrä ja kyselyiden määrä. Seuraavalla rivillä on luvut a_1, \ldots, a_n, puun solmuissa olevat luvut. Sen jälkeen tulee n-1 riviä, joilla on luvut u_i, v_i, joka tarkoittaa että puussa on kaari solmujen u_i ja v_i välillä. Sen jälkeen tulee q riviä, joilla on luvut u_i, v_i, k_i eli kysytään mikä on k:s luku jos luvut polulla u_i:sta v_i:hin järjestetään.

Tuloste

Tulosta jokaiseen kyselyyn vastaus.

Rajat

• 1 \le n \le 5 \cdot 10^5
• 1 \le q \le 5 \cdot 10^5
• 1 \le a_i \le 5 \cdot 10^5

Esimerkki

Syöte:

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

Tuloste:

2
8
9
105
7