Hotel

Time Limit: 6000/3000MS (Java/Others) Memory Limit: 256000/128000KB (Java/Others)

Problem Description

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?

Input

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

Output

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.

Sample Input

4 3
1 2 3 4
1 2 
2 3
1 4
3 4 1 2 2
4 3 1 3 2
2 4 3 3 2

Sample Output

1
2
-1

Source

dut200901102

Manager

Information
Solved Number10
Submit Number21
Problem Tags
data structures
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel