問題
スペード,クローバー,ダイヤ,ハートのカードがそれぞれN枚ずつあり,それぞれのマークについて,1~Nの番号のカードが1枚ずつある.例えば,スペードの1,クローバーの1,ダイヤの1,ハートの1はそれぞれS1,C1,D1,H1で表され,最初,カードは,S1,...,SN,C1,...CN,D1,...,DN,H1,...,HNの順番で並んでいる.
これに対して,Q個のクエリに従ってシャッフルを行う.具体的には,i(1≤i≤Q)番目のクエリでは次の操作をしなければならない.
- Li,Riが与えられる.カードLiからカードRiまでの全てのカードを順番を保ったまま先頭に持っていく.つまり,カードの順列{a1,a2,...,a4N}においてLi=aj,Ri=ak(1≤j≤k≤4N) であるとき,順列{a1,…,aj−1,aj,…,ak,ak+1...,a4N}を{aj,…,ak,a1,…,aj−1,ak+1,...a4N}に変更する.LiとRiが等しい場合は,該当する1枚を先頭に持っていく.なお,Liの位置がRiの位置より右にあるようなケースは与えられない.
Q個のクエリを順に処理した後のカードの順列における,全てのスペードのカードのみからなる部分列,全てのクローバーのカードのみからなる部分列,全てのダイヤのカードのみからなる部分列,全てのハートのカードのみからなる部分列をそれぞれこの順で出力せよ.
部分列とは,ある順列から任意数の項を抜き出した上で,"順番を保ったまま"それらを並べてできる順列のことである.
制約
- 1≤N≤105
- 1≤Q≤105
入力
N Q
Li Ri(1≤i≤Q)はそれぞれ"S"または"C"または"D"または"H"の1文字と,数字j(1≤j≤N)を並べてできる4N種類の文字列
出力
スペードのカードのみからなる部分列,クローバーのカードのみからなる部分列,ダイヤのカードのみからなる部分列,ハートのカードのみからなる部分列をそれぞれこの順で4行で出力せよ.
サンプル
入力例1
出力例1
初期状態は,{S1,C1,D1,H1}.
1つ目のクエリにより,C1D1が先頭に行くので,{C1,D1,S1,H1}になる.
2つ目のクエリにより,D1S1が先頭に行くので,{D1,S1,C1,H1}になる.
N=1の場合,どのように並び替えてもそれぞれ1枚ずつしかないので,出力結果は自明です.
入力例2
出力例2
S3 S1 S2
C1 C2 C3
D2 D3 D1
H1 H2 H3
初期状態は,{S1,S2,S3,C1,C2,C3,D1,D2,D3,H1,H2,H3}.
1つ目のクエリにより,C2D1が先頭に行くので,{C2,C3,D1,S1,S2,S3,C1,D2,D3,H1,H2,H3}になる.
2つ目のクエリにより,S3H3が先頭に行くので,{S3,C1,D2,D3,H1,H2,H3,C2,C3,D1,S1,S2}になる.
それぞれのマークのみからなる部分列は,スペードが{S3,S1,S2},クローバーが{C1,C2,C3},ダイヤが{D2,D3,D1},ハートが{H1,H2,H3}となる.
入力例3
出力例3
LiとRiが等しい場合もあります.その場合は,その1枚を先頭に持っていきます.