ランチ

お昼に食べるお弁当を作るために、お店で食べ物を買いました。お店では、食べ物を入れるのに細長い袋しかもらえなかったので、すべての食べ物を縦に積んで袋に入れる必要があります。袋が倒れにくいように、できるだけ重い物を下にして詰めたいのですが、食べ物の中にはやわらかい物もあって、上に重い物を乗せるとつぶれてしまいます。

そこで、食べ物の情報を入力とし、全ての食べ物がつぶれず、かつ全体の重心が最も低くなるような積み方を出力するプログラムを作成してください。それぞれの食べ物ごとに、名前 f、重さ w、上に載せて耐えられる重さ s が指定されます。 「全ての食べ物がつぶれない」というのは、下から順に、（f₁、f₂、... 、f_n）と n 個の食べ物を積んだ時、すべての f について、

s_fi ≥ w_fi+1 + w_fi+2 + ... + w_fn

であることを意味します。また、全体の重心 G は、

G = (1 × w_f1 + 2 × w_f2 + ... + n × w_fn) / (w_f1 + w_f2+ ... +w_fn)

とします。ただし、解はちょうど1つだけ存在するものとします。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されます。各データセットは以下の形式で与えられます。

n
f1 w1 s1
f2 w2 s2
:
fn wn sn

１行目に食べ物の個数 n (1 ≤ n ≤ 10)、続く n 行に i 番目の食べ物の名前 f_i (20 文字以内の半角英文字列)、重さ w_i (1 ≤ w_i ≤ 1000)、耐えられる重さ s_i (1 ≤ s_i ≤ 1000) が空白区切りで与えられます。

データセットの数は 20 を超えません。

Output

データセットごとに、次の形式で食べ物の名前を下から積み上げる順に出力します。

1 行目: 1 番下の食べ物の名前（半角英文字列）
2 行目: 下から2 番目の食べ物の名前
：
n 行目: 1 番上の食べ物の名前

Sample Input

4
sandwich 80 120
apple 50 200
cheese 20 40
cake 100 100
9
onigiri 80 300
onigiri 80 300
anpan 70 280
mikan 50 80
kanzume 100 500
chocolate 50 350
cookie 30 80
purin 40 400
cracker 40 160
0

Output for the Sample Input

apple
cake
sandwich
cheese
kanzume
purin
chocolate
onigiri
onigiri
anpan
mikan
cracker
cookie