005 - Stacking Books

時間制限 2 秒 / メモリ制限 256 MB / 得点 22 / x 1 /

TLE
2sec
MLE
256MB
得点
22

問題

N 個の箱が円環状に並んでいます。i (2≤i≤N) 番目の箱は i+1 番目の箱及び i−1 番目の箱に隣接しており、1 番目の箱は 2 番目の箱及び N 番目の箱に隣接しています。

山本君は 2 体のロボットを所持しており、本積み上げロボットと本回収ロボットの二種類があります。本積み上げロボットは円環の中心に配置されており、そこからアームを伸ばして箱の中に本を積み上げていきます。本回収ロボットははじめ箱 1 の前に配置されており、そこから移動しながら箱の中に積まれている本を回収していきます。

これらのロボットは命令が送られたときのみ動作します。

本積み上げロボットに対しての命令の場合1 k cという形式で与えられ、これは箱 k の中に色 c の本を一番上に積み上げることを表します。

本回収ロボットに対しての命令の場合2という整数のみ与えられ、この命令が与えられたとき下記の「移動」を行います。

  • 「移動」: 現在 i 番目の箱の前にいるとき、i+1 番目の箱の前へと移動し「回収」を行う。N 番目の箱の前にいる場合は 1 番目の箱の前に移動し、「回収」を行う。
  • 「回収」: 現在 i 番目の箱の前にいるとき、i 番目の箱の中に本がある場合はその箱の一番上に積まれている本 1 冊を回収し、動作を終了する。無い場合は再び「移動」を行う。

これらの命令が Q 回にわたって与えられえるので、回収された本の色を回収された順に出力してください。
なお、本回収ロボットに対しての命令はいずれかの箱の中に本が積まれている場合にのみ与えられます。

入力

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

N Q

各命令は次の形式で Q 行にわたって与えられます。
本積み上げロボットに対しての命令は次の通りです。 

1 k c

本回収ロボットに対しての命令は次の通りです。 

2

出力

回収された本の色を回収された順に改行区切りで出力せよ。

制約

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

  • 1≤N≤2×105
  • 2≤Q≤2×105
  • 1≤k≤N
  • 1≤c≤109
  • いずれの箱にも本が積まれていない状態で本回収ロボットへの命令が与えられることはない。
  • 本回収ロボットへの命令は必ず 1 回以上与えられる。
  • 入力は全て整数である。

入出力例

入力例1

5 6
1 2 2
1 4 1
1 2 3
2
2
2

出力例1

3
1
2

最初の 3 つの命令は本積み上げロボットに対する命令です。 よって、箱 2 には上から順番に色 3,2 の本が、箱 4 には色 1 の本が入っています。
次に本回収ロボットへの命令が 3 回与えられています。
まず 1 回目の命令で箱 2 の前に移動し色 3 の本を回収します。
次に 2 回目の命令で箱 4 の前に移動し色 1 の本を回収します。
最後に 3 回目の命令で箱 2 の前に移動し色 2 の本を回収します。
よって、回収された本の色の順番通りに 3,1,2 を出力します。

入力例2

10 10
1 8 3
1 5 9
2
2
1 2 8
1 6 3
2
1 1 3
1 10 5
2

出力例2

9
3
8
3