atcoder#ABC212F. [ABC212F] Greedy Takahashi
[ABC212F] Greedy Takahashi
Score : points
Problem Statement
There are cities numbered through , and buses that go between these cities. The -th bus departs from City at time and arrive at City at time .
Takahashi will travel between these cities. When he is in City at time , he will do the following.
- If there is a bus that departs from City not earlier than time , take the bus that departs the earliest among those buses to get to another city.
- If there is no such bus, do nothing and stay in City .
Takahashi repeats doing the above until there is no bus to take. It is guaranteed that all buses depart at different times, so the bus to take is always uniquely determined. Additionally, the time needed to change buses is negligible.
Here is your task: process queries, the -th of which is as follows.
- If Takahashi begins his travel in City at time , in which city or on which bus will he be at time ?
Constraints
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
Output
Print lines. The -th line should contain the response to the -th query as follows.
- If Takashi is on some bus at time , print two integers representing the city from which the bus departs and the city at which the bus arrives, in this order, with a space between them.
- Otherwise, that is, if Takahashi is in some city at time , print an integer representing that city.
3 2 3
1 2 1 3
2 3 3 5
1 1 5
2 2 3
1 3 2
2 3
2
3
In the first query, Takahashi will travel as follows.
- Start in City at time .
- Take the bus that departs from City at time and arrives at City at time .
- Take the bus that departs from City at time and arrives at City at time .
- Since no bus departs from City at time or later, stay in City (forever).
At time , he will be on the bus that departs from City and arrives at City . Thus, as specified in the Output section, we should print and with a space between them.
8 10 10
4 3 329982133 872113932
6 8 101082040 756263297
4 7 515073851 793074419
8 7 899017043 941751547
5 7 295510441 597348810
7 2 688716395 890599546
6 1 414221915 748470452
6 4 810915860 904512496
3 1 497469654 973509612
4 1 307142272 872178157
374358788 4 509276232
243448834 6 585993193
156350864 4 682491610
131643541 8 836902943
152874385 6 495945159
382276121 1 481368090
552433623 2 884584430
580376205 2 639442239
108790644 7 879874292
883275610 1 994982498
4
6 1
4 1
8
6 1
1
2
2
7 2
1