Median of the open board: hints, no solution

A ticket board starts empty. Events arrive as a list of integers. A positive value v opens a ticket with urgency v. A negative value -v closes one currently open ticket whose urgency is v; the input guarantees that such a ticket exists at that moment. Tickets with equal urgency are interchangeable.

After an event, the median urgency of the open tickets is the middle value when they are sorted; with an even count it is the lower of the two middle values, and with no open tickets it is -1. To keep the answer short, report only after events whose 1-based position is a multiple of step. Return those medians in order. The board can see thousands of events, so each event must cost about logarithmic time, not a full re-sort.

Examples

Input

events = [5, 1, 9, -1, -5], step = 1

Output

[5, 1, 5, 5, 9]

Note

Open 5, 1, 9 gives medians 5, 1, 5 (lower of 1 and 5 for two tickets, then 5 of three); closing 1 leaves 5 and 9, median 5; closing 5 leaves 9.

Input

events = [4, 4, 6, -4, 2, -6], step = 2

Output

[4, 4, 2]

Note

Only events 2, 4 and 6 are reported: the boards then hold {4, 4}, {4, 6} and {2, 4}, whose lower medians are 4, 4 and 2.

Constraints

• 1 <= number of events <= 3500 and 1 <= step <= 3500
• 1 <= number of events <= 40000 and 1 <= step <= 40000
• Every closing event names an urgency that is open
• About logarithmic work per event is expected

Hint 1: a nudge

If the open tickets were sorted, which position would hold the answer? What changes in that sorted order when one ticket is added or removed?

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