Monster Factory

Time Limit : 5 sec, Memory Limit : 65536 KB

Problem B: Monster Factory

株式会社南天堂は, Packet Monster というゲームソフトを発売している. このゲームはモンスターを捕まえ, 育て, 戦わせるという趣旨のもので, 世界中で大人気のゲームであった.

このゲームには従来のゲームには無い特徴があった. このゲームには Red と Green という2つのバージョンがあり, それぞれのゲームで捕まえられるモンスターが異なるのだ. Red でしか捕まえられないモンスターを Green で入手するには, 通信交換というシステムを使う. つまり, 自分のソフト内のモンスターと友達のソフト内のモンスターを交換することができるのだ. このシステムは Packet Monster の人気に大きく貢献していた.

しかし, このゲームのパッケージの製造工程は, 2つのバージョンのために少々複雑になった. パッケージを製造している工場には2つの生産ラインがあり, 片方のラインでは Red を, もう一方のラインでは Green を製造している. 各ラインで製造されたパッケージは, 工場内で一意な製造番号が割り当てられ, 一箇所に集められる. そして以下のような攪拌(かくはん)装置によって混ぜられ, 出荷されるのだ.

Red のパッケージは上側から, Green のパッケージは左側から, ベルトコンベアによってこの攪拌装置に届けられる. 攪拌装置は十字の形をした2本のベルトコンベアから出来ており, "push_down", "push_right" という2つの命令を受け付ける. "push_down"は「上下方向に走るベルトコンベアをパッケージ1個分下方向に動かせ」, "push_right"は「左右方向に走るベルトコンベアをパッケージ1個分右方向に動かせ」という命令である. 攪拌は, Red のパッケージと同じ数の push_down 命令と Green のパッケージの数より1つ多い push_right 命令を, ランダムな順番で実行することによって行われる. ただし, 最初に実行される命令と最後に実行される命令は "push_right" と決まっている. この制約の元では, Red のパッケージの数と攪拌装置の下端に届くパッケージの数が一致し, Green のパッケージの数と攪拌装置の右端に届くパッケージの数が一致する.

攪拌されたパッケージは最終的にベルトコンベアの下端または右端に届き, 届いた順に包装されて出荷される.

以下に, 一連の攪拌の手続きの例を示す. 簡単のため, 1つのパッケージを1文字のアルファベットとして表す.

さて, この工場では不良品の追跡などの目的で, ベルトコンベアの下端・右端に届いたパッケージとその順番を記録している.しかしこの記録にはコストが掛かるため, 工場長は下端に届いたパッケージについてのみ記録を取ることを考えた.右端に届いたパッケージは, 上端・左端に送られるパッケージと下端に届いたパッケージの記録から求められるのではないかと思ったのだ.

工場長を助けて, 右端に届いたパッケージの記録を作成するプログラムを作ってほしい.

Input

入力は複数のデータセットからなる. 入力の終わりは - (ハイフン)1つの行で示される.

1つの入力は3行のアルファベットの大文字・小文字のみを含む文字列からなる. これらはそれぞれ, Red のパッケージ, Green のパッケージ, 下端に届いたパッケージを表す.1文字のアルファベットが1個のパッケージを表す.大文字と小文字は区別されることに注意せよ.

どの行にも, 同じ文字が2回以上現れることは無い. 1行目と2行目に共通して含まれる文字も存在しない.

問題文中で説明されたケースは, Sample Inputの1つ目の例に対応している.

Output

右端に届いたパッケージを, 届いた順番のとおりに出力せよ.

Sample Input

CBA
cba
cCa
X
ZY
Z
-

Output for the Sample Input

BbA
XY

Source: University of Aizu, ACM-ICPC Japan Domestic Contest 2009 Warm Up II , Aizu-Wakamatsu, Japan, 2009-06-28
Problem Setter:  Takashi Tayama