のんびり座りたい 〜 横へな 2013.2.2

問題

いくつかの椅子がある。そこにひとりずつ人が現れ、あるいは立ち去る。
椅子は一列に並んでいる。
人が座る席は以下のルールで決まる:

1. どちら側の隣にも人が座っていない席を選ぶ。
2. それが無理なら、片側にしか人が座っていない席を選ぶ。
3. それも無理なら、両側に人が座っている席を選ぶ。
4. 上記の条件で一つに決まらない場合は、候補のうち最も左にある席を選ぶ。
5. 一度座ったら立ち去るまでその場を動かない。

入力

入力は 6:NABEbBZn のような形式になっている。
「 : 」の前(上記の例では 6 ) は椅子の数を示す。
「 : 」の後(上記の例では NABEbBZn ) は人の出入りを示す。A〜Z は、それぞれの人の到着を意味し、a〜z は、対応する大文字の人が立ち去ったことを意味する。

出力

出力は、席に座っている人を左から順に並べる。誰も座っていない席は - で示す。
入力が 6:NABEbBZn の場合、

------

N-----

N-A---

N-A-B-

N-A-BE

N-A--E

N-AB-E

NZAB-E

-ZAB-E

補足

• 空席がない状態で人が来ることを考慮する必要はない。
• 席の数は 30 ぐらいまで対応できれば良い。
• 不正な入力（ 4:ABCxyz のように座っていない人が退席した、 :2:ABC@%$ のような不正な書式のもの、など）には対処しなくてよい。
• 両端の処理に注意かも。

実装ができた方は Qiitaの記事 のコメント欄からリンクを張っていただくと見つけやすくて助かります。

サンプルデータ

C/C++/Java 用のテストデータ