Earliest arrival: hints, no solution

A rail network has n stations numbered from 0 to n - 1. Each row of trips is one scheduled train: [from, to, depart, arrive], a one-way ride that leaves station from at minute depart and reaches station to at minute arrive, with depart strictly less than arrive.

A traveller starts at station origin at minute ready, and query is [origin, destination, ready]. They may board a train only if they are already at its departure station at or before its departure minute, so a transfer where a train arrives at exactly the minute the next one leaves is allowed. Waiting at a station is free.

Return the earliest minute at which the traveller can be at the destination. If origin equals destination, return ready. If the destination cannot be reached, return -1.

Examples

Input

n = 4, trips = [[0, 1, 10, 20], [1, 2, 25, 40], [1, 2, 15, 18], [0, 2, 5, 50]], query = [0, 2, 0]

Output

40

Note

Ride 0 to 1 (arrive 20), then the 25 departure to station 2 arriving at 40. The 15 departure is missed and the direct train arrives at 50.

Input

n = 4, trips = [[0, 1, 10, 20], [1, 2, 25, 40], [1, 2, 15, 18], [0, 2, 5, 50]], query = [0, 2, 11]

Output

-1

Note

Both trains out of station 0 leave before minute 11, so the traveller can never board one.

Input

n = 4, trips = [[0, 1, 10, 20]], query = [3, 3, 7]

Output

7

Note

The traveller is already at the destination, so the answer is the ready minute.

Constraints

• 1 <= n <= 45001
• 0 <= trips.length <= 45000
• 0 <= depart < arrive <= 1000000
• query holds valid stations and a ready minute in the same range

Hint 1: a nudge

If you know the earliest minute you can be at each station so far, what does a train leaving one of those stations at a later minute tell you about the station it reaches?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing