B - Restaurant Queue Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君はAtCoderレストランの前の待ち行列の管理をしたいです。はじめ、待ち行列に並んでいる人はいません。 また、待ち行列に並ぶ人は必ず注文する料理のメニュー番号が書かれた食券を持って並びます。

Q 個のクエリが与えられるので順に処理してください。クエリは 2 種類あり、以下のいずれかの形式で与えられます。

  • 1 X: 待ち行列の末尾に 1 人並ぶ。このとき並ぶ人はメニュー番号が X の食券を持って並ぶ。
  • 2: 待ち行列の先頭にいる人をレストランに案内する。このとき案内される人が持っている食券のメニュー番号を出力する。

制約

  • 1 \leq Q \leq 100
  • 1 \leq X \leq 100
  • 2 つ目の形式のクエリについて、案内する前に待ち行列に並んでいる人がいる
  • 入力は全て整数

入力

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

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

各クエリは以下の 2 種類のいずれかの形式で与えられる。

1 X

2

出力

問題文の指示に従ってクエリへの答えを改行区切りで出力せよ。

入力例 1

6
1 3
1 1
1 15
2
1 3
2

出力例 1

3
1

はじめ、待ち行列に並んでいる人はいません。

  • 1 つ目のクエリについて、メニュー番号が 3 の食券を持った人が待ち行列の末尾に並びます。この時、待ち行列に並んでいる人が持っている食券のメニュー番号は先頭の人から順に 3 です。
  • 2 つ目のクエリについて、メニュー番号が 1 の食券を持った人が待ち行列の末尾に並びます。この時、待ち行列に並んでいる人が持っている食券のメニュー番号は先頭の人から順に 3,1 です。
  • 3 つ目のクエリについて、メニュー番号が 15 の食券を持った人が待ち行列の末尾に並びます。この時、待ち行列に並んでいる人が持っている食券のメニュー番号は先頭の人から順に 3,1,15 です。
  • 4 つ目のクエリについて、待ち行列の先頭にいる人をレストランに案内します。案内する人はメニュー番号が 3 の食券を持っているので 3 を出力します。この時、待ち行列に並んでいる人が持っている食券のメニュー番号は先頭の人から順に 1,15 です。
  • 5 つ目のクエリについて、メニュー番号が 3 の食券を持った人が待ち行列の末尾に並びます。この時、待ち行列に並んでいる人が持っている食券のメニュー番号は先頭の人から順に 1,15,3 です。
  • 6 つ目のクエリについて、待ち行列の先頭にいる人をレストランに案内します。案内する人はメニュー番号が 1 の食券を持っているので 1 を出力します。この時、待ち行列に並んでいる人が持っている食券のメニュー番号は先頭の人から順に 15,3 です。

入力例 2

7
1 3
1 1
1 4
1 1
1 5
1 9
1 2

出力例 2



2 つ目の形式のクエリがないことがあることに注意してください。






Score : 200 points







Problem Statement
Takahashi wants to manage the waiting line in front of the AtCoder Restaurant. Initially, the waiting line is empty. Each person who joins the line holds a meal ticket with the menu number of the dish they will order.


Process Q queries in order. There are two types of queries, given in the following formats:


    

  • 1 X: One person joins the end of the waiting line holding a ticket with menu number X.
    • 

  • 2: Takahashi guides the person at the front of the waiting line into the restaurant. Print the menu number on that person’s ticket.
    • 












Constraints
    

  • 1 \leq Q \leq 100
    • 

  • 1 \leq X \leq 100
    • 

  • For each query of the second type, there is at least one person in the line before guiding.
    • 

  • All input values are integers.
    • 
















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


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



Each query has one of the following two formats:


1 X



2












Output
For each query, print the answer as specified in the problem statement, each on its own line.















Sample Input 1
6
1 3
1 1
1 15
2
1 3
2












Sample Output 1
3
1



Initially, the waiting line is empty.


    

  • For the first query, a person holding a ticket with menu number 3 joins the end of the line. The sequence of menu numbers held by people in line from front to back is 3.
    • 

  • For the second query, a person holding a ticket with menu number 1 joins the end of the line. The sequence becomes 3,1.
    • 

  • For the third query, a person holding a ticket with menu number 15 joins the end of the line. The sequence becomes 3,1,15.
    • 

  • For the fourth query, guide the person at the front into the restaurant. That person holds menu number 3, so print 3. The sequence becomes 1,15.
    • 

  • For the fifth query, a person holding a ticket with menu number 3 joins the end of the line. The sequence becomes 1,15,3.
    • 

  • For the sixth query, guide the person at the front into the restaurant. That person holds menu number 1, so print 1. The sequence becomes 15,3.
    • 














Sample Input 2
7
1 3
1 1
1 4
1 1
1 5
1 9
1 2












Sample Output 2


Note that there may be no queries of the second type.