027 - 誕生日プレゼントが欲しいKamba君

問題

7月4日はKamba君の誕生日です。たくさんの友人から祝福され、非常に盛り上がりました。気づけば、Kamba君の机の上には大量のプレゼントが積みあがっています。
そこで、Kamba君のプレゼントに関する次のクエリを処理してください。

クエリ

以下の3種類のクエリが与えられます。

• クエリタイプ $1$
  友人がプレゼント $G$ を持ってくる。そして、Kamba君の机の上にプレゼント $G$ を積む。


• クエリタイプ $2$
  Kamba君が一番上のプレゼントを開封する。そして、Kamba君の机の上から取り除く。ただし、机上にプレゼントが一つもない状態で、このクエリが与えられることはない。


• クエリタイプ $3$
  Kamba君が一番上にあるプレゼントの名前を確認し、その結果を出力する。
  ただし、机上にプレゼントがなかった場合、$-1$ を出力してください。
  

入力

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

$Q$
$query_1$
$query_2$
$:$
$:$
$query_Q$

1行目にクエリの総数 $Q$ が与えられる。
2行目以降に各クエリが与えられる。

また、各クエリの与えられ方は以下の通りである。

• クエリタイプ $1$

  type G
  

  クエリのタイプ $type$ が与えられ、プレゼントの名前 $G$ が文字列で与えられる。

• クエリタイプ $2$ と $3$

  type
  

  クエリのタイプ $type$ のみ与えられる。

出力

出力はすべて改行区切りで行い、出力の最後に改行すること。ただし、出力が一切ない場合を除く。

制約

全ての入出力ケースについて以下を満たす。

• $1 \leq Q \leq 7.4 \times 10^{4}$
• $1 \leq type \leq 3$
• $1 \leq |G| \leq 74$（ただし、$|S|$ は文字列 $S$ の長さを表す。）
• 文字列 $G$ は全てアルファベットで構成される。
• 入力される数値は全て整数である。
• 机上にプレゼントが一つもない状態で、クエリタイプ $2$ が与えられることはない。

入出力例

入力例1

6
1 candy
1 teddyBear
3
2
3
2

出力例1

teddyBear
candy

• 1. Kamba君は "candy" を貰います。そして机の上に積み上げます。
  
• 2. Kamba君は "teddyBear" を貰います。そして机の上に積み上げます。
  
• 3. Kamba君は一番上にあるプレゼントの名前を確認します。下から順に "candy", "teddyBear" の順で積み上がっているので、"teddyBear" が一番上にあります。よって、"teddyBear" と出力します。
  
• 4. Kamba君は一番上にあるプレゼントを開封します。そして机の上から取り除きます。
  
• 5. Kamba君は一番上にあるプレゼントの名前を確認します。"candy" が机の上に置かれているので、"candy" と出力します。
  
• 6. Kamba君は一番上にあるプレゼントを開封します。そして机の上から取り除きます。
  

入力例2

3
3
3
3

出力例2

-1
-1
-1

1つもプレゼントを貰えないこともあります。Kamba君の気持ちは...考えないでおきましょう。

入力例3

2
1 iceCream
2

出力例3

Kamba君はいち早くプレゼントを開封したくて、名前を確認しないこともあります。