問題文

予選を勝ち抜いてきた N 人の参加者が 1 つの部屋で M 問の問題が出題されるコンテストに参加しています。

このコンテストでは全ての問題を正解した参加者から部屋の出口に歩いて行き、部屋の外に出ることができます。

i 番目の参加者 (1\le i\le N) の予選の順位は i 位であり、問題を 1 問解くのに S_i 秒かかり、出口まで歩くのに E_i 秒かかります。

複数の参加者が同時に出口にたどり着いた場合、予選順位が高い方の参加者から順に部屋から出ます。

部屋から出る順番に参加者の番号を出力してください。

制約

• 2\le N\le 100
• 1\le M\le 10^9
• 1\le S_i,E_i\le 10^9
• 入力される値は全て整数

入力例 1

3 6
3 10
4 2
10 100

出力例 1

2 1 3

• 1 番目の参加者はコンテスト開始から出口にたどり着くまでに 3\times 6 + 10 = 28 秒かかります。
• 2 番目の参加者はコンテスト開始から出口にたどり着くまでに 4\times 6 + 2 = 26 秒かかります。
• 3 番目の参加者はコンテスト開始から出口にたどり着くまでに 10\times 6 + 100 = 160 秒かかります。

したがって、2 番目の参加者、1 番目の参加者、3 番目の参加者の順に部屋から出ていきます。

入力例 2

4 100
1 1000000000
100 100
100 100
100 100

出力例 2

2 3 4 1

複数の参加者が同時に出口にたどり着いた場合、予選順位が高い方の参加者から順に部屋から出ることに注意してください。

入力例 3

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

出力例 3

2 1 6 5 3 4