Vasya has moved from his hometown and misses his old friends very much. Unfortunately, Vasya rents a small apartment and only one friend can come to visit him at a time. Each friend told Vasya two numbers A and B - from what day to what day he can come to visit.
Each friend arrives and leaves at noon. Each friend can come to Vasya only once and stay with him for a few days. Vasya would like the total number of days when one of his friends is visiting him to be maximum. Help him determine the dates & nbsp; of arrival for each of his friends so that they do not overlap (it is possible that on one day one of the friends leaves and the other leaves) and the total time when Vasya has someone from friends, was the maximum.
Input data format
The first line contains an integer N (1 ≤ N ≤ 100000) - the number of Vasya's friends. The next N lines contain two integers A
i and B
i > (both numbers from 1 to 10
9) - possible arrival time of the i-th friend.
Output data format
Print N pairs of numbers L
i and R
i - the numbers of the days on which the i-th friend will arrive and leave, respectively (A
i ≤ L
i ≤ R
i ≤ B
i). If you don't need to invite the i-th friend, print a pair of numbers -1 -1. If there are several correct answers, print any of them.
Examples
| # |
Input |
Output |
| 1 |
3
1 2
24
3 5
| 1 2
34
5 5 |
| 2 |
3
23
14
3 5
| -1 -1
14
5 5 |