447. Class Timings

0

Medium

In a primary school , Alice is a Teacher who decides the classes timings in the form of intervals [Start Time , End Time].

He has Given an array of intervals where intervals[i] = [starti, endi]. He has to arrange these Intervals such that no two class Timings overlap each other which means merge all overlapping intervals and return the non-overlapping intervals . In Order to help him you have to print the non overlapping class intervals

He has Given an array of intervals where intervals[i] = [starti, endi]. He has to arrange these Intervals such that no two class Timings overlap each other which means merge all overlapping intervals and return the non-overlapping intervals . In Order to help him you have to print the non overlapping class intervals

Input Format

First Line contains an Integer N (Number of Intervals)

Next N Lines contains class intervals in the form of Start time and End time.

Next N Lines contains class intervals in the form of Start time and End time.

Output Format

Print Each Non-overlapping intervals in a New Line.

Example

Input

4
1 3
2 6
8 10
15 18

Output

1 6
8 10
15 18

Constraints

1<= N <= 10

1 <= start[i] , end[i] <= 10

^{4}1 <= start[i] , end[i] <= 10

^{4}for each ith intervalLoading...

View Submissions

Console