Free gaps: hints, no solution

A clinic is open from minute open to minute close, and its appointments are given as [start, end) pairs of minutes in no particular order. Appointments may overlap, and some may begin before opening or run past closing.

Return every free gap inside opening hours as a [start, end) pair: a stretch of at least one minute, within [open, close), in which no appointment is running. List the gaps in ascending order. Two gaps never touch, because touching stretches are one gap. If the clinic is fully booked, return an empty list.

Examples

Input

open = 540, close = 1020, appointments = [[600, 660], [630, 700], [900, 960]]

Output

[[540, 600], [700, 900], [960, 1020]]

Note

Minutes 600 to 700 are booked, so the free gaps are before 600, from 700 to 900 and from 960 to closing.

Input

open = 540, close = 1020, appointments = [[500, 1100]]

Output

[]

Note

One appointment covers the whole day, so nothing is free.

Input

open = 540, close = 1020, appointments = []

Output

[[540, 1020]]

Note

With no appointments the whole opening period is one gap.

Constraints

• 0 <= open < close <= 10000000
• 0 <= appointments.length <= 80000
• 0 <= start < end <= 10000000; appointments may overlap or lie outside opening hours

Hint 1: a nudge

Walk through the day in time order and keep track of how far the busy time has reached. When do you see a hole between where it has reached and the next appointment start?

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