Stacking Blocks II

Time Limit : 1 sec, Memory Limit : 131072 KB

Stacking Blocks II

ロボットを操作して、n個のブロックの山を作る。各ブロックにはアルファベット1文字で示された色が着いている。ロボットは以下の命令を実行する:

  • push p c: 色がcであるブロックをp個目の山に積む
  • pop p: p個目の山の頂点からブロックを1つ取り除く
  • move p1 p2: p1個目の山の頂点からブロックを1つ取り除き、それをp2個目の山に積む
  • quit: 終了する

最初、すべての山は空(から)である。

ロボットへの命令を読み込んで、pop命令によって取り除かれたブロックの色を順番に出力するプログラムを作成せよ。

Input

最初の行に山の数nが与えられる。続いて、命令の列が与えられる。1つの命令が1行に与えられる。命令の種類は上述した通りである。ブロックの色cは、aからzまでのアルファベットで与えられる。p, p1, p2は1からnまでの数字で与えられる。

quit命令でプログラムを終了せよ。

Output

取り除かれたブロックの色を順番に出力せよ。1つの色を1行に出力せよ。

Constraints

山に含まれるブロックの数が1000を超えることはない。

山の数が100を超えることはない。

誤った命令は与えられない。

Sample Input

2
push 1 a
push 1 b
push 1 c
push 2 z
pop 1
move 1 2
pop 2
pop 2
pop 1
quit

Sample Output

c
b
z
a

Source: Introduction to Programming , Aizu, Japan
http://judge.u-aizu.ac.jp/onlinejudge/course.jsp