Question

The Concert Hall's Booking Conflicts

A concert hall has received N booking requests, each specifying a start time and an end time. Two bookings that share any overlapping time (including if one ends exactly when another begins) must be merged into a single combined booking block that spans their entire combined range.

Given all N booking requests, merge every group of overlapping (or touching) bookings into combined blocks, and report the resulting non-overlapping booking blocks, sorted by start time.

Input

The first line contains a single integer KaTeX can only parse string typed expression — the number of booking requests. If KaTeX can only parse string typed expression, there are no bookings.

Each of the next KaTeX can only parse string typed expression lines contains two integers, the start and end time of a booking.

Output

Print a single integer KaTeX can only parse string typed expression on the first line — the number of resulting merged booking blocks.

Then print KaTeX can only parse string typed expression lines, each containing the start and end time of a merged block, sorted by start time.

Example

Example 1:
Input

Output

Explanation
The bookings KaTeX can only parse string typed expression and KaTeX can only parse string typed expression overlap (both cover time 2 to 3), so they merge into KaTeX can only parse string typed expression. The other two bookings don't overlap with anything, so they remain separate.

Example 2:
Input

1

5 10

Output

1

5 10

Explanation
A single booking has nothing to merge with, so it is reported as-is.

Example 3:
Input

Output

1

1 6

Explanation
Each booking touches the next one exactly at its boundary (booking 1 ends at time 4, booking 2 starts at time 4), which counts as overlapping, so all three merge into a single block KaTeX can only parse string typed expression.

Online

Explore Newton School

Recent Questions

Most Solved Questions

Least Solved Questions