Serve by urgency: hints, no solution

An emergency dispatch desk answers one call per minute. Call i arrives at minute arrivals[i] and has an urgency urgency[i]; a bigger number means more urgent. Calls are numbered from 0 in the order given, and that list is not sorted by arrival time.

The desk starts at minute 0. At each minute it looks at the calls that have arrived at that minute or earlier and are still waiting, and serves exactly one: the most urgent one, and among equally urgent calls the one that arrived earlier, and if they still tie, the one with the smaller number. If nobody is waiting, the minute passes with no service. Return the call numbers in the order they are served.

Examples

Input

arrivals = [0, 0, 1, 2], urgency = [3, 5, 9, 1]

Output

[1, 2, 0, 3]

Note

Minute 0 serves call 1, minute 1 serves the new urgent call 2, then calls 0 and 3.

Input

arrivals = [5, 5, 5], urgency = [2, 2, 2]

Output

[0, 1, 2]

Note

Everything ties, so the smaller call number goes first.

Constraints

• 0 <= number of calls <= 76000
• 0 <= arrivals[i] <= 100000
• 1 <= urgency[i] <= 1000

Hint 1: a nudge

At any minute, which calls are even eligible to be served, and how would you keep the best of them close at hand as new calls show up?

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