ストーリー

???「Reはもちろん「レ点」って意味だよ」

ゆ～さんは漢文ドリルを進めています。まだ始めたばかりのため、今日の内容は漢文の読む順番についてです。

しかし、そのドリルに書かれている漢文はおおよそ人間用とは思えないほど長かったため、ゆ～さんは漢文の返り点を入力すると読む順番が出力されるプログラムが欲しくなりました。

そして、あなたにその仕事を依頼しました。恐らく、機械にやらせるにしてもなかなか面倒な部類の仕事ですが...

問題文

$N$ 個の文字があり、それぞれ 文字 $1,\dots,N$ と番号が割り振られています。

文字 $i$ には $A_i,B_i$ の数字が割り振られており、 $N$ 個の文字が下記のルールに従った順番でちょうど一回ずつ読まれます。

• $A_i=1$ である時、文字 $i+1$ の次に読む
• $B_i=2$ である時、$j>i$ かつ $B_j=1$ である最小の $j$ である 文字 $j$ の次に読む
• 上記に該当しない場合、小さい番号の文字を先に読む

制約より、文字の読む順番は一意に定まり、それはすべての文字をちょうど一度ずつ読むものであることが保証されます。

$k=1,\dots,N$ において、 $k$ 番目に読まれる 文字の番号を $N$ 行で答えてください。

制約が複雑である点に注意してください。

入力

$N$
$A_1\ B_1$
$A_2\ B_2$
$\vdots$
$A_N\ B_N$

制約

• $2\le N\le 2\times10^5$
• $A_i\in $ { $0,1$ }
• $B_i\in $ { $0,1,2$ }
• $A_N=0$
• $B_N\neq 2$
• $1$ 以上 $N$ 以下のすべての $i$ について、$B_1,B_2,\dots,B_i$ のうち $1$ と同値であるものの個数を $D$、$2$ と同値であるものの個数を $E$ をすると
  • $D\le E$
  • $E-D \le 1$
• $B_1,B_2,\dots,B_N$ のうち $1$ と同値であるものの個数と $2$ と同値であるものの個数は等しい
• $A_i=1$ ならば $B_{i+1}\neq 1$
• $A_i=1$ ならば $B_i\neq 2$
• $B_i = 2$ ならば $B_{i+1} = 0$
• 入力はすべて整数

出力

$N$ 行出力してください。$i$ 行目には $i$ 番目に読む文字の番号を出力してください。

サンプル

3
0 0
1 0
0 0

1
3
2

5
0 0
1 0
0 2
0 0
0 1

1
4
5
3
2

10
0 2
1 0
1 0
0 0
1 1
0 2
0 0
1 0
0 0
0 1

4
3
2
7
9
8
10
6
5
1