Shared opening hours: hints, no solution

Two clinics publish their opening hours for the week as lists of [start, end) pairs of minutes. Within each list the periods are sorted by start and never overlap, though one may begin exactly when the previous one ends.

Return every period during which both clinics are open. Produce one [start, end) pair for each pair of one period from the first list and one from the second whose overlap lasts at least one minute, and list the results in ascending order. Overlaps are never merged: a period that overlaps two adjacent periods of the other clinic gives two separate entries. If the clinics are never open together, return an empty list.

Examples

Input

a = [[60, 200], [300, 400]], b = [[100, 150], [300, 350]]

Output

[[100, 150], [300, 350]]

Note

The first clinic opens 60 to 200 and the second 100 to 150, so they share 100 to 150; the later periods share 300 to 350.

Input

a = [[0, 10]], b = [[10, 20]]

Output

[]

Note

The periods only touch at minute 10, so no time is shared.

Input

a = [[0, 10], [10, 20], [20, 30]], b = [[5, 25]]

Output

[[5, 10], [10, 20], [20, 25]]

Note

The second clinic period spans two of the first clinic periods and gives two entries.

Constraints

• 0 <= a.length, b.length <= 64000
• Each list is sorted by start, has no overlapping periods, and 0 <= start < end <= 1000000
• Periods in one list may touch end to start

Hint 1: a nudge

For a period from one clinic and a period from the other, when do they share time, and what is that shared period? Try a few pairs from the sample by hand.

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