Time Limit: 6000/3000MS (Java/Others) Memory Limit: 256000/128000KB (Java/Others)
There is a huge country consist of N cities. Each pair of citys are connected by only one path.
Each city has a hotel, and because of the regional differences, they have different stars. As you know five-star hotel is the best now, but in that country, you will meet 10000-star hotel.
There are also M businessmen located at different cities.
For ith businessman, we know where he live, and the target-city where he always buy commodity. when he travel from the live-city to the target-city, he will select some city to stay overnight.
The hotel he overnight should have the P stars where ai ≤ P ≤ bi.
As long as this businessman reach a city whose city's star meet the constraint he would stay one night, otherwise he will select passing.
Now we wonder for each businessman, when he travel from the live-city to the target-city, which city will be the kth overnight place?
There are multiple test cases.
The first line contains two integers N, M.
The next line contains N integers Si indicating the star of hotel in ith city.
The next N - 1 lines each line contains two integer a, b indicating there is a road between city a and city b.
The last M lines each lines contains five integers si, ti, ai, bi, ki to describe the ith businessman.
1 ≤ N, M ≤ 100000
1 ≤ Si ≤ 100000
1 ≤ a, b ≤ N
1 ≤ si, ti ≤ N, 1 ≤ ai ≤ bi ≤ 100000
For each test case, output M lines.
Each line contains one integer indicating the answer for ith businessman.
If there is no city meet the demand, please output -1.
1 2 3 4
3 4 1 2 2
4 3 1 3 2
2 4 3 3 2