题目描述

$1$ から $N$ までの番号がついた $N$ 問のクイズがあり，あなたはこれらを使ったゲームに参加します．

このゲームでは，あなたはクイズに $1$ 問ずつ回答していきます． クイズに回答する順番は自由に選ぶことができます． クイズ $i$ に回答すると $P_i$ % の確率で正解します． 正解した場合，あなたは $S_i$ 点を獲得し，（まだ未回答のクイズがあるなら）次のクイズの回答へと移ります． 正解しなかった場合，即座にゲームが終了し，残りのクイズに回答することができなくなります．

あなたは，獲得する得点の合計の期待値を最大化したいです． 目的を達成するための戦略（＝クイズに回答する順番）を求めてください． なお，各クイズに正解するか否かの確率は互いにすべて独立であるものとします．

输入格式

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

$N$ $S_1$ $P_1$ $S_2$ $P_2$ $\vdots$ $S_N$ $P_N$

输出格式

答えを以下の形式で出力せよ．

$x_1$ $x_2$ $\cdots$ $x_N$

ここで $x_i$ は，最初の ($i-1$) 問を正解した場合に $i$ 番目に回答するクイズの番号を表す． 解が複数存在する場合，どれを出力しても正解とみなされる．

2
1000 10
300 50

2 1

6
1 0
1 20
1 40
1 60
1 80
1 100

6 5 4 3 2 1

9
88994950 78
405248480 35
561113280 28
22802150 2
946582650 25
201425280 52
669650 41
128877450 71
1396050 25

1 5 8 2 3 6 4 7 9

提示

制約

• $1\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ S_i\ \leq\ 10^9$
• $0\ \leq\ P_i\ \leq\ 100$
• 入力される値はすべて整数である

Sample Explanation 1

クイズ $1,2$ の順で回答した場合，獲得する得点の合計の期待値は $115$ になります． クイズ $2,1$ の順で回答した場合，獲得する得点の合計の期待値は $200$ になります． よって，クイズ $2,1$ の順で回答するのが最適な戦略です．