A51 - Stack Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

以下の 3 種類のクエリを高速に処理するプログラムを実装してください。

  • クエリ 1： x という題名の本を机の一番上に積む。
  • クエリ 2：一番上に積まれている本の題名を答える。
  • クエリ 3：一番上に積まれている本を机から取り出す。

ただし、最初は机の上に本が積まれておらず、与えられるクエリの数は Q 個であるとします。

入力

Query_i は i 回目のクエリの情報を表します。クエリ 1 の場合は 1 x、クエリ 2 の場合は 2、クエリ 3 の場合は 3 という形式で与えられます。

詳しくは入力例をご覧ください。

Q
Query_1
:
Query_Q

出力

クエリ 2 の答えを、順番に出力してください。

制約

  • 1 \leq Q \leq 100,000
  • 与えられる本の題名は 20 文字以下であり、英小文字からなる
  • クエリ 2 およびクエリ 3 の時点では、一冊以上の本が積まれている

入力例 1

5
1 futuremap
1 howtospeak
2
3
2

出力例 1

howtospeak
futuremap