B - レギュラーメンバーの選抜 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

高橋君はサッカーチームの監督をしています。チームには N 人の選手がおり、各選手には 1 から N までの背番号がちょうど 1 つずつ付けられています。高橋君はこの中から K 人をレギュラーメンバーとして選抜しなければなりません。

各選手 i (1 \leq i \leq N) には、練習での評価点 A_i と、直近の試合での評価点 B_i の 2 つのパラメータがあります。選手 i の「総合評価」は A_i + B_i として算出されます。

高橋君は、以下のルールに従って N 人の選手に 1 位から N 位までの順位を付けます。

  • 総合評価が大きい選手ほど上位（順位の値が小さい）とする。
  • 総合評価が等しい選手同士では、背番号が小さい選手ほど上位とする。

背番号は選手ごとに異なるため、このルールによりすべての選手の順位は一意に定まります。

こうして付けられた順位が 1 位から K 位までの K 人をレギュラーメンバーとして選びます。

レギュラーメンバーに選ばれた K 人の背番号を小さい順に出力してください。

制約

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

入力

N K
A_1 B_1
A_2 B_2
\vdots
A_N B_N
  • 1 行目には、選手の人数を表す整数 N と、レギュラーメンバーの人数を表す整数 K が、空白区切りで与えられる。
  • 1 + i 行目 (1 \leq i \leq N) には、選手 i の練習での評価点 A_i と直近の試合での評価点 B_i が空白区切りで与えられる。

出力

レギュラーメンバーに選ばれた K 人の背番号を小さい順に、1 行に 1 つずつ出力せよ。

入力例 1

5 3
10 20
30 10
20 20
15 25
25 15

出力例 1

2
3
4

入力例 2

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

出力例 2

1
2
3

入力例 3

10 4
50 60
80 30
45 55
70 40
60 50
90 20
30 80
100 10
55 45
65 35

出力例 3

1
2
4
5

入力例 4

20 7
500 300
100 900
350 350
700 200
450 550
600 400
250 750
800 100
150 850
400 500
550 450
300 600
650 250
200 800
750 150
50 950
900 50
1000 1
1 1000
500 500

出力例 4

2
5
6
7
9
18
19

入力例 5

1 1
1 1

出力例 5

1

Score : 300 pts

Problem Statement

Takahashi is the manager of a soccer team. The team has N players, and each player is assigned exactly one jersey number from 1 to N. Takahashi must select K players from among them as regular members.

Each player i (1 \leq i \leq N) has two parameters: a practice evaluation score A_i and a recent match evaluation score B_i. The "overall evaluation" of player i is calculated as A_i + B_i.

Takahashi ranks all N players from rank 1 to rank N according to the following rules:

  • A player with a higher overall evaluation is ranked higher (i.e., has a smaller rank value).
  • Among players with equal overall evaluations, the player with the smaller jersey number is ranked higher.

Since jersey numbers are distinct for each player, these rules uniquely determine the rank of every player.

The K players ranked from 1st to Kth are selected as regular members.

Output the jersey numbers of the K players selected as regular members in ascending order.

Constraints

  • 1 \leq K \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq B_i \leq 10^9 (1 \leq i \leq N)
  • All input values are integers.

Input

N K
A_1 B_1
A_2 B_2
\vdots
A_N B_N
  • The first line contains an integer N representing the number of players and an integer K representing the number of regular members, separated by a space.
  • The (1 + i)-th line (1 \leq i \leq N) contains player i's practice evaluation score A_i and recent match evaluation score B_i, separated by a space.

Output

Output the jersey numbers of the K players selected as regular members in ascending order, one per line.

Sample Input 1

5 3
10 20
30 10
20 20
15 25
25 15

Sample Output 1

2
3
4

Sample Input 2

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

Sample Output 2

1
2
3

Sample Input 3

10 4
50 60
80 30
45 55
70 40
60 50
90 20
30 80
100 10
55 45
65 35

Sample Output 3

1
2
4
5

Sample Input 4

20 7
500 300
100 900
350 350
700 200
450 550
600 400
250 750
800 100
150 850
400 500
550 450
300 600
650 250
200 800
750 150
50 950
900 50
1000 1
1 1000
500 500

Sample Output 4

2
5
6
7
9
18
19

Sample Input 5

1 1
1 1

Sample Output 5

1