Top open tickets: hints, no solution

A dispatch board receives a stream of ticket events. Each event is a pair [id, urgency]. When urgency is positive, ticket id is opened with that urgency, where a bigger number means more urgent. When urgency is 0, ticket id is closed.

A ticket id is opened at most once, and a close event always names a ticket that is open at that moment. After all events have been applied, return the ids of the k most urgent tickets that are still open, ordered from most urgent to least urgent; when two open tickets have the same urgency the smaller id comes first. If fewer than k tickets are open, return all of them.

Examples

Input

events = [[1, 5], [2, 9], [3, 4], [2, 0]], k = 2

Output

[1, 3]

Note

Ticket 2 is closed, leaving tickets 1 (urgency 5) and 3 (urgency 4).

Input

events = [[7, 3], [8, 3], [9, 3]], k = 2

Output

[7, 8]

Note

All three tie on urgency, so the two smallest ids are returned.

Constraints

• 0 <= number of events <= 100000
• 1 <= id <= 100000 and every id is opened at most once
• 1 <= urgency <= 1000 when opening
• 1 <= k <= 70000

Hint 1: a nudge

Once the whole stream has been read, which tickets are even candidates, and how many of them do you actually need to keep track of at a time?

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