B - Scoreboard of a Programming Contest Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君は、プログラミングコンテストの順位表を作成する担当者です。

このコンテストには N 人の参加者がおり、各参加者には 1 から N までの番号が付けられています。参加者 i のレーティングは A_i です。

コンテストでは、各参加者がスコアを獲得しました。参加者 i の獲得スコアは B_i です。コンテストの得点方式の性質上、獲得スコアは必ず自分のレーティング以上となります。すなわち、すべての i (1 \leq i \leq N) について B_i \geq A_i が成り立ちます。

順位表は以下のルールで作成されます。2人の参加者を比較するとき、以下の基準を優先度の高い順に適用し、上位(順位の数字が小さい方)を決定します:

  1. 獲得スコアが高い参加者を上位とする。
  2. 獲得スコアが同じ場合は、レーティングが高い参加者を上位とする。
  3. 獲得スコアもレーティングも同じ場合は、参加者番号が小さい参加者を上位とする。

参加者番号はすべて異なるため、上記のルールによりすべての参加者の順位は一意に定まります。

高橋君の代わりに、各参加者の番号を順位が高い方から順に出力するプログラムを作成してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • A_i \leq B_i \leq 10^9 (1 \leq i \leq N)
  • 入力はすべて整数

入力

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

1 行目には、参加者の人数を表す整数 N が与えられる。続く N 行のうち i 行目には、参加者 i のレーティング A_i と獲得スコア B_i が、スペース区切りで与えられる。

出力

N 行にわたって、順位が高い方から順に参加者の番号を出力せよ。i 行目には、i 位の参加者の番号を出力せよ。


入力例 1

3
100 200
150 200
120 300

出力例 1

3
2
1

入力例 2

5
1000 1500
800 1500
1200 1500
500 2000
900 1000

出力例 2

4
3
1
2
5

入力例 3

10
50 300
200 300
200 250
100 400
150 300
300 300
80 200
400 400
150 150
250 300

出力例 3

8
4
6
10
2
5
1
3
7
9

Score : 300 pts

Problem Statement

Takahashi is in charge of creating the standings for a programming contest.

There are N participants in this contest, and each participant is assigned a number from 1 to N. The rating of participant i is A_i.

In the contest, each participant earned a score. The score earned by participant i is B_i. Due to the nature of the contest's scoring system, the earned score is always at least as large as one's own rating. That is, B_i \geq A_i holds for all i (1 \leq i \leq N).

The standings are created according to the following rules. When comparing two participants, the following criteria are applied in order of priority to determine who ranks higher (i.e., has a smaller rank number):

  1. The participant with a higher earned score ranks higher.
  2. If the earned scores are the same, the participant with a higher rating ranks higher.
  3. If both the earned score and the rating are the same, the participant with the smaller participant number ranks higher.

Since all participant numbers are distinct, the above rules uniquely determine the rank of every participant.

On behalf of Takahashi, write a program that outputs each participant's number in order from the highest-ranked to the lowest-ranked.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • A_i \leq B_i \leq 10^9 (1 \leq i \leq N)
  • All inputs are integers

Input

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

The first line contains an integer N representing the number of participants. In the following N lines, the i-th line contains the rating A_i and the earned score B_i of participant i, separated by a space.

Output

Over N lines, output the participant numbers in order from the highest-ranked to the lowest-ranked. On the i-th line, output the participant number of the participant ranked i-th.


Sample Input 1

3
100 200
150 200
120 300

Sample Output 1

3
2
1

Sample Input 2

5
1000 1500
800 1500
1200 1500
500 2000
900 1000

Sample Output 2

4
3
1
2
5

Sample Input 3

10
50 300
200 300
200 250
100 400
150 300
300 300
80 200
400 400
150 150
250 300

Sample Output 3

8
4
6
10
2
5
1
3
7
9