Page not loading? Try clicking here.
Placeholder

#8577

Meeting Alignment 2s 1024MB

Problems

Jeong-ol is working an office job and has been instructed to sort N meetings.

Every meeting is represented by two natural numbers: a start time and an end time.

For example, a 3 10 meeting is a meeting that starts at 3 o'clock and ends at 10 o'clock. (The duration will be 7 hours.)

Jeong-ol wants to sort these meetings,

1st Priority: Meeting duration

2nd Priority: Meeting start time in ascending order.

In other words, the meeting with the shortest duration should come first,

and among meetings with the same duration, the one that starts earlier should come first.

Help Jeong-ol and output the sorting results.


Input

The first line contains N. ( 1 ≤ N ≤ 500,000 )

Over the next N lines, the start time S and end time E of each meeting are given.

( 1 ≤ S ≤ E ≤ 109 )

However, among the input meetings, there are no cases where meetings with the same S and E appear multiple times.

Since the volume of input and output is large, it is recommended to use fast I/O. The following are ways to use fast I/O in major languages.

  • C++: If using cin and cout, add std::cin.tie(0); std::ios::sync_with_stdio(false); to the first line of the main function, and output '\n' instead of endl for new lines. Note that in this case, C I/O functions including scanf cannot be used.

    • scanf/printf are fast enough, so no special processing is required.

  • Java: Use BufferedReader and BufferedWriter instead of Scanner and System.out.println.

  • Python3, PyPy3: Use sys.stdin.readline().rstrip() instead of input().


Output

In the sorted result, let's output the "input order" of each meeting in order.

"Input order" indicates the order in which it was entered.

For example, the "input order" of the first entered meeting will be 1, the next will be 2, ... and the last will be N.


Example 

7
3 5
1 3
7 10
2 8
1 7
8 8
2 4
6
2
7
1
3
5
4


Source

againalgo

You must sign in to write code.