プッシュ&ポップ (paizaランク B 相当)

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

根を 0 として、各ノードに順番に番号が割り当てられた二分木を考えます。この二分木では、親ノードの番号を 2 倍して 1 または 2 を足したものが子ノードの番号となっています。

長さ N の数列が与えられます。この数列のインデックスと二分木の番号が対応しており、

数列の"親の番号"番目の要素は、"子の番号"番目の要素以下である

という条件(＊)が成り立っています。

次の 2 種類のクエリが合計 Q 個与えられるので、与えられた順番に処理し、最後に処理が終了したあとの数列を出力してください。

・push x : x を数列の末尾に追加し、条件(＊)が成り立つように STEP 4 と同様の操作をして数列の要素を入れ替える。
・pop : 数列の先頭の要素を出力した後、数列の最後尾の要素を先頭の要素に置き換えて条件(＊)が成り立つように 
STEP 6 と同様の操作をして数列の要素を入れ替える。数列の長さが 1 の場合は、数列の先頭の要素を出力した後、
数列の要素をすべて削除する。

ただし、要素の入れ替えは、二分木で親と子の関係にあるインデックス同士でのみおこなうことができるものとします。また、二つの子の要素が同じでどちらも親の要素より小さいときは、番号の小さいほうの子の要素と入れ替えをおこなってください。

入力される値

N Q
a_0 ... a_{N-1}
q_1
...
q_Q

1 行目に、整数 N, Q が与えられます。

2 行目に長さ N の数列の要素が左から順番に半角スペース区切りで与えられます。

2 + j 行目に各クエリ q_j が与えられます。(1 ≦ j ≦ Q)

q_j は以下のいずれかの形式です。(1 ≦ j ≦ Q)

push x_j

pop

j 番目のクエリでは、まずクエリの種類（push, popのいずれか）が与えられ、push の場合はさらに整数 x_j が与えられます。

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力: 種類が pop であるクエリの数を q_pop として、合計 q_pop + 1 行出力してください。 j 行目では、種類が pop となる j 番目のクエリに従って出力してください。(1 ≦ j ≦ q_pop)　q_pop + 1 行目には、すべてのクエリが終了したあとの数列の要素を左から順番に半角スペース区切りで出力してください。

また末尾に改行をいれ、余計な文字、空行を含んではいけません。

条件

すべてのテストケースにおいて、以下の条件をみたします。

1 ≦ N ≦ 10^4

1 ≦ Q ≦ 10^4

0 ≦ a_i ≦ 10^5 (0 ≦ i ≦ N-1)

0 ≦ x_j ≦ 10^5 (1 ≦ j ≦ Q, ただし、q_j の種類は　push)

数列の長さが 0 のとき、種類が pop であるクエリは次に与えられないことが保証されています。

入力例1: 7 2
1 3 7 5 12 9 10
push 2
pop

出力例1: 1
2 3 7 5 12 9 10

入力例2: 1 8
5
pop
push 3
push 10
push 8
push 9
pop
push 7
push 6

出力例2: 5
3
6 7 10 9 8

問題一覧へ戻る