Problem J: The Incubator

サラリーマンの朝は早い。エリートコースを進み一流企業に入社して新人という肩書きからも卒業する頃、僕に下った辞令は未開の惑星における営業活動だった。辺鄙な土地での不便な生活を強いられているが、一応は左遷でなく栄転であり、その証拠に給料もぐんと上がっている - こんな場所では金なんて使いようもないのだけど。近年僕たちが直面している宇宙規模のエネルギー不足に対応するため、特定の生物種の個体から莫大なエネルギーを生成するテクノロジーが開発された。その特定の生物種というのが、この辺鄙な惑星の固有種なのだ。この生物が絶滅しないように保護しつつ、適度にエネルギーを回収していくのが僕の仕事だ。

エネルギーの回収は、いくつかのステップからなる。まずは、エネルギーの回収に使用する個体を選別する。個体によって得られるエネルギーの量は大きく異なるのだ。次に、選別された見込みのある個体に、インキュベーションという特別な処理を行う。インキュベートされた個体は膨大なエネルギーの源となる何かをを絶えず蓄えたり吐き出したりするので、個体にできるだけ多くのエネルギーの源となる何かが蓄えられている瞬間を狙って、円環の理に導く。するとお待ちかねのエネルギーが手に入る、という仕組みだ。

エリートサラリーマンに課せられるノルマは厳しい。しかし、僕にとって数十万のインキュベートされた個体を管理するのは朝飯前だ。今日は月末なので本社に月報を提出しなければならないが、今月はとても良い個体に遭遇したこともあって、過去最高の成績になりそうだ。

と喜んでいたのも束の間、最後の最後でひどいミスをやらかしてしまった。SQL文を打ち間違えて、今月の成果を記録しているデータベースのテーブル 1 つをまるごとふっ飛ばしてしまったのだ。あれがなければ、今月の成果は全く無しということになってしまう。降格、左遷、あるいは解雇もありえるかもしれない。

最後の頼みの綱は、作業のたびにこまめにつけていたログファイルだ。僕はいつも、個体をインキュベートするたびに一意な整数の番号を振り、インキュベートされた個体たちの番号を 1 つの配列に保存している。僕の営業活動は、次のような行動からなる。

1. 個体をインキュベートし、その個体に番号 x を割り当て、その個体の番号を配列の末尾に追加する。
2. 配列の n 番目の番号が示す個体を円環の理に導く。
3. 番号 x の個体を円環の理に導く。
4. 残念ながら僕は最大 lim 体の個体しか管理できない。個体をインキュベートしたとき、もしインキュベート済みの個体が lim を超えたならば、昔にインキュベートした個体から順に lim 以下になるまで円環の理に導く。

僕はこれら 4 つの営業活動を行うたびに、欠かさずログファイルに記入している。しかし、4 の活動だけはログファイルに一切記入していない。そうしても特に曖昧なところは残らないためだ。

いつも僕は、個体の番号の配列の操作を愚直に行なっている。しかし今度ばかりは、愚直に操作しながらログファイルを走査していては間に合いそうにない。月報の提出期限は 5 時間後に迫っている。

そこで、君たちにお願いがあるんだ。ログファイルから僕の営業活動を再現するプログラムを書いてほしい。もし書いてくれたら、お礼に君たちの願い事を何でも 1 つ叶えてあげよう。何だって構わない。どんな願いことだって叶えてあげられるよ。

Input

入力は複数のケースからなる。 各ケースは以下のフォーマットで与えられる。

ここには入力のフォーマットを書く。
q lim
query0  x0
.
.
.
queryq-1 xq-1

query_i が0の時、インキュベートした個体に x_i の番号を割り当てたことを表す。
query_i が1の時、配列の x_i 番目の番号が示す個体を円環の理に導く。
query_i が2の時、その時点で配列に含まれている中で　x_i　番目の個体の番号を出力する
query_i が3の時、番号が x_i の個体を円環の理に導く。
q = 0 かつ lim = 0の時入力の終わりを表す。

lim は32bit signed integerで表すことができる正の整数である。
すべてのクエリーについて、x_i は0以上の整数で32bit signed integerで表すことができる。
0のクエリーについて、x_i　は32bit signed integerの範囲に収まる非負整数で表される。
1,2のクエリーについて、x_i の値は1以上の整数である。また存在しない配列の番号が指定されることはない
3のクエリーについて、存在しない個体番号が入力に含まれることはない。
また一度消去された個体の番号が値が同じテストケース内で、別の個体に割り当てられることはない。

ジャッジデータは次の2つのうち少なくとも片方を満たす。
1 ≤ q ≤ 400,000 かつテストケースの数が5個以下
1 ≤ q ≤ 10,000 かつテストケースの数は50個以下

Output

入力のクエリーが2の場合、x番目の個体番号を出力する
各ケースの最後には"end"を出力する

Sample input

22 5
0 0
0 1
0 2
0 3
0 4
2 1
2 2
2 3
2 4
2 5
0 5
2 1
0 6
2 2
3 3
2 2
2 2
1 2
2 2
2 1
2 2
2 3
30 5
0 383594529
1 1
0 868094164
0 708344471
0 4102559
0 944076771
0 320398558
1 1
0 949521499
0 1035499529
0 585547493
0 915496840
0 721553343
0 405934659
0 814301872
1 1
2 3
0 919753364
1 1
0 69231610
2 2
0 373477673
0 842917649
0 961543702
0 907959899
2 1
2 2
2 3
2 4
2 5
30 5
0 726736645
0 1
0 344304573
0 241734870
3 726736645
1 3
2 1
0 586879203
2 3
0 511883046
0 481344051
0 154183395
0 435126242
0 185906768
1 1
0 383123551
0 20253038
1 5
2 1
2 2
0 163044554
3 435126242
0 105612613
0 725050544
0 559442328
2 1
2 2
2 3
2 4
2 5
0 0

Sample output

0
1
2
3
4
1
3
4
4
5
2
5
6
end
405934659
405934659
69231610
373477673
842917649
961543702
907959899
end
1
586879203
154183395
435126242
383123551
163044554
105612613
725050544
559442328
end

The University of Aizu Programming Contest 2011 Summer
原案: Tomoya Sakai
問題文: Takashi Tayama