Woburn Challenge 2018-19 Finals Round - Senior Division

At last, the time has come for months of hard work to finally pay off — the cows' and monkeys' production is hitting the big screen this weekend!

It will be playing at movie theatres in ~N~ ~(2 \le N \le 400\,000)~ different cities, numbered from ~1~ to ~N~ in increasing order of their theatres' quality. There are ~N-1~ roads running amongst these cities, the ~i~-th of which allows vehicles to drive in either direction between cities ~A_i~ and ~B_i~ ~(1 \le A_i, B_i \le N, A_i \ne B_i)~. However, each road also passes through a tunnel which imposes a limit on the heights of vehicles which may drive along it — in particular, a vehicle may only travel along the ~i~-th road if its height is at most ~L_i~ cm ~(1 \le L_i \le 10^9)~. It's possible for a 1 cm-high vehicle (if such a thing exists) to travel from any city to any other city by following a sequence of roads.

There are ~K~ ~(1 \le K \le 400\,000)~ moviegoers who have been waiting anxiously to see the film, with the ~i~-th one living in city ~C_i~ ~(1 \le C_i \le N)~ and driving a vehicle with a height of ~H_i~ cm ~(1 \le H_i \le 10^9)~. However, they won't necessarily settle for watching the film in their own cities — they're prepared to drive wherever it takes to get the best possible movie-watching experience! However, they're also not great at planning ahead, so each moviegoer will follow this simple procedure:

1. They'll consider both their current city and all cities they can directly reach from that city (by driving along a single road whose tunnel their vehicle can fit through), and find the one with the highest-quality movie theatre (the largest city number).
2. If that largest-numbered city is their current city, they'll stop to watch the film there.
3. Otherwise, they'll drive to that largest-numbered city, and repeat the procedure from step 1.

The Head Monkey and Bo Vine want to make sure that each theatre has enough seats available for its screening — nobody should be left out from witnessing their masterpiece! In order to help estimate audience sizes, determine which city each of the ~K~ moviegoers will end up stopping at to watch the film.

Subtasks

In test cases worth ~5/34~ of the points, ~N \le 2\,000~ and ~K \le 2\,000~.
In test cases worth another ~12/34~ of the points, each city has at most two roads directly adjacent to it.

Input Specification

The first line of input consists of two space-separated integers, ~N~ and ~K~.
~N-1~ lines follow, the ~i~-th of which consists of three space-separated integers, ~A_i~, ~B_i~, and ~L_i~, for ~i = 1 \dots (N-1)~.
~K~ lines follow, the ~i~-th of which consists of two space-separated integers, ~C_i~ and ~H_i~, for ~i = 1 \dots K~.

Output Specification

Output ~K~ lines, the ~i~-th of which should consist of a single integer, the city at which moviegoer ~i~ will stop to watch the film, for ~i = 1 \dots K~.

Sample Input

3 3
1 2 10
3 1 5
1 4
2 1
1 10

Sample Output

3
2
2

Sample Explanation

The first moviegoer will drive from city ~1~ to city ~3~ and then remain there.
The second moviegoer will remain at city ~2~.
The third moviegoer will drive from city ~1~ to city ~2~ and then remain there.