AT_abc389_c [ABC389C] Snake Queue

ヘビの待ち行列があります。最初、列は空です。 クエリが $ Q $ 個与えられるので、与えられた順に処理してください。クエリは以下の $ 3 $ 種類です。 - タイプ $ 1 $ : `1 l` の形式で与えられる。長さ $ l $ のヘビが列の末尾に追加される。このとき追加するヘビの頭の位置は、元の列が空の場合は座標 $ 0 $ 、そうでない場合は最後尾のヘビの頭の座標に最後尾のヘビの長さを加えた座標となる。 - タイプ $ 2 $ : `2` の形式で与えられる。列の先頭にいるヘビが列から抜ける。このとき、列が空でないことは保証される。抜けたヘビの長さを $ m $ として、列に残っている全てのヘビの頭の座標が $ m $ だけ減少する。 - タイプ $ 3 $ : `3 k` の形式で与えられる。列の先頭から数えて $ k $ 番目にいるヘビの頭の座標を出力せよ。このとき、列には少なくとも $ k $ 匹のヘビがいることが保証される。

入力は以下の形式で標準入力から与えられる。 > $ Q $ $ \text{query}_1 $ $ \text{query}_2 $ $ \vdots $ $ \text{query}_Q $ ただし、 $ \text{query}_i $ は $ i $ 個目のクエリを表し、以下のいずれかの形式である。 > $ 1 $ $ l $ > $ 2 $ > $ 3 $ $ k $

タイプ $ 3 $ のクエリの個数を $ q $ として、 $ q $ 行出力せよ。 $ i $ 行目には、 $ i $ 個目のタイプ $ 3 $ のクエリに対する答えを出力せよ。

### Sample Explanation 1 - $ 1 $ 個目のクエリ : 長さ $ 5 $ のヘビが列に追加される。列にヘビはいないため、追加されたヘビの頭の座標は $ 0 $ となる。 - $ 2 $ 個目のクエリ : 長さ $ 7 $ のヘビが列に追加される。追加する前の最後尾のヘビの頭の座標が $ 0 $ で長さが $ 5 $ のため、追加されたヘビの頭の座標は $ 5 $ となる。 - $ 3 $ 個目のクエリ : 前から $ 2 $ 番目にいるヘビの頭の座標を出力する。列にいるヘビの頭の座標は前から順に $ 0, 5 $ であるため、 $ 5 $ を出力する。 - $ 4 $ 個目のクエリ : 長さ $ 3 $ のヘビが列に追加される。追加する前の最後尾のヘビの頭の座標が $ 5 $ で長さが $ 7 $ のため、追加されたヘビの頭の座標は $ 12 $ となる。 - $ 5 $ 個目のクエリ : 長さ $ 4 $ のヘビが列に追加される。追加する前の最後尾のヘビの頭の座標が $ 12 $ で長さが $ 3 $ のため、追加されたヘビの頭の座標は $ 15 $ となる。 - $ 6 $ 個目のクエリ : 先頭のヘビが列から抜ける。抜けたヘビの長さが $ 5 $ であるため、列にいるヘビの頭の座標は $ 5 $ だけ減少する。列に残っているヘビの頭の座標は先頭から順に $ 0,7,10 $ となる。 - $ 7 $ 個目のクエリ : 前から $ 3 $ 番目にいるヘビの頭の座標を出力する。列にいるヘビの頭の座標は前から順に $ 0, 7, 10 $ であるため、 $ 10 $ を出力する。 ### Sample Explanation 2 タイプ $ 3 $ のクエリが $ 1 $ つもない場合もあります。 ### Constraints - $ 1 \leq Q \leq 3 \times 10^{5} $ - タイプ $ 1 $ のクエリにおいて、 $ 1 \leq l \leq 10^{9} $ - タイプ $ 2 $ のクエリにおいて、列が空でないことが保証される - タイプ $ 3 $ のクエリにおいて、列にいるヘビの数を $ n $ として、 $ 1 \leq k \leq n $ - 入力は全て整数