D - Card Pile Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

整数 0 の書かれたカードが 100 枚積み重なったカードの山があります。

Q 個のクエリを処理してください。それぞれのクエリは以下のいずれかです。

  • タイプ 1 : 整数 x の書かれたカードを 1 枚カードの山の一番上に積み重ねる。
  • タイプ 2 : カードの山の一番上のカードを取り除き、取り除いたカードに書かれている整数を出力する。ここで、本問題の制約下では必ず山にカードが存在する。

制約

  • 1\le Q\le 100
  • 1\le x\le 100
  • タイプ 2 のクエリが 1 つ以上存在する。
  • 入力される値は全て整数

入力

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

Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

i 番目のクエリ \text{query}_i では、まずクエリのタイプ c_i （1,2 のいずれか）が与えられる。 c_i=1 の場合はさらに整数 x が追加で与えられる。

すなわち、各クエリは以下に示す 2 つの形式のいずれかである。

1 x

2

出力

c_i=2 を満たすクエリの回数を q として、 q 行出力せよ。

j (1\le j\le q) 行目では j 番目のそのようなクエリに対する答えを出力せよ。

入力例 1

6
2
1 4
1 3
2
2
2

出力例 1

0
3
4
0

各クエリを処理した後の山は順に以下のようになります：

  • カードの山の一番上のカードを取り除く。取り除いたカードに書かれた整数は 0 であるため、 0 を出力する。
    • カードの山は 0 の書かれたカードが 99 枚となる。
  • 4 が書かれたカードを山の上に追加する。
    • カードの山は上から順に 4 の書かれたカードが 1 枚、 0 の書かれたカードが 99 枚となる。
  • 3 が書かれたカードを山の上に追加する。
    • カードの山は上から順に 3 の書かれたカードが 1 枚、 4 の書かれたカードが 1 枚、 0 の書かれたカードが 99 枚となる。
  • カードの山の一番上のカードを取り除く。取り除いたカードに書かれた整数は 3 であるため、 3 を出力する。
    • カードの山は上から順に 4 の書かれたカードが 1 枚、 0 の書かれたカードが 99 枚となる。
  • カードの山の一番上のカードを取り除く。取り除いたカードに書かれた整数は 4 であるため、 4 を出力する。
    • カードの山は 0 の書かれたカードが 99 枚となる。
  • カードの山の一番上のカードを取り除く。取り除いたカードに書かれた整数は 0 であるため、 0 を出力する。
    • カードの山は 0 の書かれたカードが 98 枚となる。

入力例 2

5
2
2
2
2
2

出力例 2

0
0
0
0
0

Score : 200 points

Problem Statement

There is a stack of 100 cards, each labeled with the integer 0.

Process Q queries. Each query is of one of the following:

  • Type 1: Place a card labeled with an integer x on top of the stack.
  • Type 2: Remove the top card of the stack and output the integer written on that removed card. Under the constraints of this problem, the stack always has at least one card.

Constraints

  • 1 \le Q \le 100
  • 1 \le x \le 100
  • There is at least one query of type 2.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

The i-th query \text{query}_i starts with the query type c_i (1 or 2), followed by the integer x if c_i=1.

That is, each query is in one of the following two formats:

1 x

2

Output

Let q be the number of queries with c_i=2. Print q lines.

The j-th line (1 \le j \le q) should contain the answer to the j-th such query.

Sample Input 1

6
2
1 4
1 3
2
2
2

Sample Output 1

0
3
4
0

After processing each query, the stack is as follows:

  • Remove the top card of the stack. The integer on the removed card is 0, so output 0.
    • The stack then has 99 cards labeled with 0.
  • Add a card labeled 4 on top.
    • The stack then has 1 card labeled 4, and 99 cards labeled 0, from top to bottom.
  • Add a card labeled 3 on top.
    • The stack then has 1 card labeled 3, 1 card labeled 4, and 99 cards labeled 0, from top to bottom.
  • Remove the top card. The integer on that card is 3, so output 3.
    • The stack then has 1 card labeled 4, and 99 cards labeled 0, from top to bottom.
  • Remove the top card. The integer on that card is 4, so output 4.
    • The stack then has 99 cards labeled 0.
  • Remove the top card. The integer on that card is 0, so output 0.
    • The stack then has 98 cards labeled 0.

Sample Input 2

5
2
2
2
2
2

Sample Output 2

0
0
0
0
0