C - シード番号の割り当て 解説 /

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

配点 : 300 点

問題文

あるゲーム大会に N 人の参加者が集まりました。参加者には 1 から N までの番号が付けられています。

大会では予選が行われ、参加者 i (1 \le i \le N) の前半戦のスコアは A_i 点、後半戦のスコアは B_i 点でした。前半戦と後半戦の合計スコア (A_i + B_i) が K 点以上である参加者が本戦に進出します。

本戦に進出する参加者には、以下の優先順位に従って 1 から順に重複なくシード番号 (1, 2, \dots) が割り当てられます。

  1. 合計スコアが大きい参加者を優先する。
  2. 合計スコアが同じ参加者が複数いる場合、参加者番号が小さい参加者を優先する。

すべての参加者 i (1 \le i \le N) について、割り当てられたシード番号を求めてください。ただし、本戦に進出しなかった参加者にはシード番号が割り当てられないため、代わりに -1 を出力してください。

制約

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

入力

入力は以下の形式で標準入力から与えられる。

N K
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

出力は N 行からなる。

i 行目 (1 \le i \le N) には、参加者 i に割り当てられたシード番号を出力してください。ただし、シード番号が割り当てられなかった場合は -1 を出力してください。

入力例 1

4 100
40 60
50 60
30 50
70 30

出力例 1

2
1
-1
3

入力例 2

3 150
50 60
40 40
70 70

出力例 2

-1
-1
-1

入力例 3

8 50
10 20
25 25
30 40
0 50
60 10
15 25
45 45
20 30

出力例 3

-1
4
2
5
3
-1
1
6

入力例 4

12 1000
500 500
300 800
1000 0
250 750
100 200
600 600
0 999
400 650
550 550
500 500
800 300
100 800

出力例 4

6
2
7
8
-1
1
-1
5
3
9
4
-1

入力例 5

1 2000000000
1000000000 1000000000

出力例 5

1

Score : 300 pts

Problem Statement

N participants gathered for a gaming tournament. The participants are numbered 1 through N.

A preliminary round was held in the tournament; participant i (1 \le i \le N) scored A_i points in the first half and B_i points in the second half. Participants whose total score of the first and second halves (A_i + B_i) is at least K points advance to the main tournament.

Each participant advancing to the main tournament is assigned a distinct seed number (1, 2, \dots) starting from 1 according to the following priority:

  1. Participants with a higher total score have higher priority.
  2. If multiple participants have the same total score, the participant with the smaller participant number has higher priority.

For all participants i (1 \le i \le N), find the assigned seed number. However, if a participant did not advance to the main tournament, they are not assigned a seed number, so output -1 instead.

Constraints

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

Input

The input is given from Standard Input in the following format:

N K
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

The output consists of N lines.

The i-th line (1 \le i \le N) should contain the seed number assigned to participant i. However, if no seed number was assigned, output -1 instead.

Sample Input 1

4 100
40 60
50 60
30 50
70 30

Sample Output 1

2
1
-1
3

Sample Input 2

3 150
50 60
40 40
70 70

Sample Output 2

-1
-1
-1

Sample Input 3

8 50
10 20
25 25
30 40
0 50
60 10
15 25
45 45
20 30

Sample Output 3

-1
4
2
5
3
-1
1
6

Sample Input 4

12 1000
500 500
300 800
1000 0
250 750
100 200
600 600
0 999
400 650
550 550
500 500
800 300
100 800

Sample Output 4

6
2
7
8
-1
1
-1
5
3
9
4
-1

Sample Input 5

1 2000000000
1000000000 1000000000

Sample Output 5

1