問題


スペード,クローバー,ダイヤ,ハートのカードがそれぞれ枚ずつあり,それぞれのマークについて,~の番号のカードが1枚ずつある.例えば,スペードの,クローバーの,ダイヤの,ハートのはそれぞれで表され,最初,カードは,の順番で並んでいる. これに対して,個のクエリに従ってシャッフルを行う.具体的には,番目のクエリでは次の操作をしなければならない.

  • が与えられる.カードからカードまでの全てのカードを順番を保ったまま先頭に持っていく.つまり,カードの順列において であるとき,順列に変更する.が等しい場合は,該当する1枚を先頭に持っていく.なお,の位置がの位置より右にあるようなケースは与えられない.

個のクエリを順に処理した後のカードの順列における,全てのスペードのカードのみからなる部分列,全てのクローバーのカードのみからなる部分列,全てのダイヤのカードのみからなる部分列,全てのハートのカードのみからなる部分列をそれぞれこの順で出力せよ.

部分列とは,ある順列から任意数の項を抜き出した上で,"順番を保ったまま"それらを並べてできる順列のことである.

制約


入力


はそれぞれ"S"または"C"または"D"または"H"の1文字と,数字を並べてできる種類の文字列

出力


スペードのカードのみからなる部分列,クローバーのカードのみからなる部分列,ダイヤのカードのみからなる部分列,ハートのカードのみからなる部分列をそれぞれこの順で4行で出力せよ.

サンプル


入力例1


1 2
C1 D1
D1 S1

出力例1


S1
C1
D1
H1

初期状態は,. 1つ目のクエリにより,~が先頭に行くので,になる. 2つ目のクエリにより,~が先頭に行くので,になる. の場合,どのように並び替えてもそれぞれ1枚ずつしかないので,出力結果は自明です.

入力例2


3 2
C2 D1
S3 H3

出力例2


S3 S1 S2
C1 C2 C3
D2 D3 D1
H1 H2 H3

初期状態は,. 1つ目のクエリにより,~が先頭に行くので,になる. 2つ目のクエリにより,~が先頭に行くので,になる. それぞれのマークのみからなる部分列は,スペードが,クローバーが,ダイヤが,ハートがとなる.

入力例3


2 1
C2 C2

出力例3


S1 S2
C2 C1
D1 D2
H1 H2

が等しい場合もあります.その場合は,その1枚を先頭に持っていきます.

Submit


Go (1.14)