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