WC '18 Finals S5 - Opening Weekend

View as PDF

Points: 25 (partial)
Time limit: 3.5s
Memory limit: 256M

Author:
Problem type
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 different cities, numbered from to in increasing order of their theatres' quality. There are roads running amongst these cities, the -th of which allows vehicles to drive in either direction between cities and . 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 -th road if its height is at most cm . 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 moviegoers who have been waiting anxiously to see the film, with the -th one living in city and driving a vehicle with a height of cm . 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 .

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 moviegoers will end up stopping at to watch the film.

In test cases worth of the points, and .
In test cases worth another 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, and .
lines follow, the -th of which consists of three space-separated integers, , , and , for .
lines follow, the -th of which consists of two space-separated integers, and , for .

Output Specification

Output lines, the -th of which should consist of a single integer, the city at which moviegoer will stop to watch the film, for .

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 to city and then remain there.
The second moviegoer will remain at city .
The third moviegoer will drive from city to city and then remain there.