問題

A と B の 2 人のプレーヤーが，0 から 9 までの数字が書かれたカードを使ってゲームを行う．最初に，2 人は与えられた n 枚ずつのカードを，裏向きにして横一列に並べる．その後，2 人は各自の左から 1 枚ずつカードを表向きにしていき，書かれた数字が大きい方のカードの持ち主が，その 2 枚のカードを取る．このとき，その 2 枚のカードに書かれた数字の合計が，カードを取ったプレーヤーの得点となるものとする．ただし，開いた 2 枚のカードに同じ数字が書かれているときには，引き分けとし，各プレーヤーが自分のカードを 1 枚ずつ取るものとする．

例えば，A，B の持ち札が，以下の入力例 1 から 3 のように並べられている場合を考えよう．ただし，入力は n + 1 行からなり，1 行目には各プレーヤのカード枚数 n が書かれており，i + 1 行目（i = 1, 2, \ldots, n）には A の左から i 枚目のカードの数字と B の左から i 枚目の カードの数字が，空白を区切り文字としてこの順で書かれている．すなわち，入力の 2 行目以降は，左側の列が A のカードの並びを，右側の列が B のカードの並びを，それぞれ表している．このとき，ゲーム終了後の A と B の得点は，それぞれ，対応する出力例に示したものとなる．

入力に対応するゲームが終了したときの A の得点と B の得点を，この順に空白を区切り文字として 1 行に出力するプログラムを作成しなさい．ただし，n \leqq 10\,000 とする．

出力においては，出力の後（B の得点の後）に改行を入れること．

入力例 1

3
9 1
5 4
0 8

出力例 1

19 8

入力例 2

3
9 1
5 4
1 0

出力例 2

20 0

入力例 3

3
9 1
5 5
1 8

出力例 3

15 14

問題

与えられた変換表にもとづき，データを変換するプログラムを作成しなさい．

データに使われている文字は英字か数字で，英字は大文字と小文字を区別する．変換表に現れる文字の順序に規則性はない．

変換表は空白をはさんで前と後ろの 2 つの文字がある(文字列ではない)．変換方法は，変換表のある行の前の文字がデータに現れたら，そのたびにその文字を後ろの文字に変換し出力する．変換は 1 度だけで，変換した文字がまた変換対象の文字になっても変換しない．変換表に現れない文字は変換せず，そのまま出力する．

入力には，変換表（最初の n + 1 行）に続き変換するデータ（n + 2 行目以降）が書いてある．1 行目に変換表の行数 n，続く n 行の各行は，空白をはさんで 2 つの文字，さらに続けて，n + 2 行目に変換するデータの行数 m，続く m 行の各行は 1 文字である．m < 10^8 とする．出力は，出力例のように途中に空白や改行は入れず 1 行とせよ．

出力においては，出力（変換後の文字列）の後に改行を入れること．

入力例 1

3   
A a 
0 5 
5 4 
10  
A   
B   
C   
0   
1   
4   
5   
a   
b   
A

出力例 1

aBC5144aba

問題

サイコロが以下の図のような向きで置かれている．

ここで使用するサイコロは，この図のように，上側に 1，南側に 2 があるときは，東側に 3 があるものとする．サイコロの向かいあう面の和は必ず 7 なので，見えない面はそれぞれ北側 5，西側 4，下側 6 になっている．

この初期配置の状態から指示に従ってサイコロを動かしていく．ただし，指示は以下の 6 通りの操作を何回か行うものである．

North，East，South，West の各操作は指示された方向へサイコロを 90 度回転させる． Right，Left の 2 つの操作は上下の面はそのままで水平方向に 90 度回転させる．（回転させる向きに要注意．）

初期配置で上の面に出ている目 1 を初期値とし，1 回の操作が終わるたびに，上の面に出ている目の数を加算していき，指示にしたがってすべての操作を終えたときの合計値を出力するプログラムを作成しなさい.

入力の 1 行目には総指示回数 n が書かれていて，続く n 行の各行には 「North，East，South，West，Right，Left」 のいずれか 1 つの指示が書かれているものとする．ただし，n \leqq 10\,000 とする．

出力においては，出力（合計値）の後に改行を入れること．

入力例 1

5
North
North
East
South
West

出力例 1

21

入力例 2

8
West
North
Left
South
Right
North
Left
East

出力例 2

34

問題

大きさが異なる n 個のコップと 3 つのトレイ（お盆）A，B，C があり，それらのコップは 3 つのトレイの上にそれぞれ何個かずつ一山に重ねて置かれている．ただし，どのトレイにおいても，そのトレイの中で一番小さいコップが一番下に，2 番目に小さいコップがその上に，3 番目に小さいコップがその上にと，小さい順に伏せて重ねてある．例えば，下図の右側は，n = 5 個のコップがトレイ A，B，C にそれぞれ 2 個，0 個，3 個重ねて置かれている状態を示している．

このように，コップの初期状態が与えられたとき，次の規則 1 ～ 3 を守りながら，すべてのコップを A または C のどちらかのトレイに移動させるには何回移動を行えばよいかを求めたい．

（規則 1） 1 回に 1 つのコップだけを移動させることができる．それは，そのトレイにあるコップの中で一番上のコップ （つまり，一番大きいコップ）である．
（規則 2） 大きいコップの上に小さいコップを重ねてはいけない．
（規則 3） コップ 1 個の直接移動は，トレイ A から B，B から A，B から C，C から B のみが許され，A から C への直接移動や C から A への直接移動は許されない．

n 個のコップの初期状態と整数 m が与えられたとき，m 回以内の移動で，A または C のどちらかのトレイにすべてのコップをまとめて重ねることができるかどうかを判定し，可能な場合には移動回数の最小値を，不可能な場合には -1 を出力するプログラムを作成しなさい．

入力の 1 行目には，n と m がこの順に空白を区切り文字として書いてある．1 \leqq n \leqq 15 であり，1 \leqq m \leqq 15\,000\,000 である．2 行目，3 行目，4 行目には，1 から n までの整数を何個かずつ 3 つのグループに分けて，それぞれのグループ内で小さい順（昇順）に並べたものが書いてある．ただし，各行の先頭（それらの整数の前）には，それらの個数が書いてある．2 行目に書かれている整数（先頭の 1 つを除く）はトレイ A の上に重ねられている各コップの大きさを表す．同様に，3 行目に書かれている整数（先頭の 1 つを除く）はトレイ B の上に重ねられている各コップの大きさを表し，4 行目に書かれている整数（先頭の 1 つを除く）はトレイ C の上に重ねられている各コップの大きさを表す．

出力においては，出力（移動回数または -1）の後に改行を入れること．

入力例 1

3 10
0
1 1
2 2 3

出力例 1

9

入力例 2

4 20
2 1 2
1 3
1 4

出力例 2

3

入力例 3

2 5
2 1 2
0
0

出力例 3

0

入力例 4

3 3
0
1 1
2 2 3

出力例 4

-1

問題

次のようなゲームを考える．1 から n までの数が 1 つずつ書かれた n 枚のカードが k 組ある．これら kn 枚のカードをよくシャッフル（よく切ること）して，k 枚ずつの山を作り横一列に並べる．このようにしてできる n 個の山の左から i 番目の（k 枚のカードの）山を「山 i」と呼ぶことにする．

ゲームは山 1 から始める．山の一番上のカード 1 枚を引き（引いたカードは元の山に戻さない），そのカードに書かれていた数が i だった場合には山 i の一番上のカード 1 枚を引く．このようにして，引いたカードに書かれていた数を番号とする山の一番上のカード 1 枚を引くことを繰り返し，すべての山にカードが無くなれば成功である．まだカードが残っている山があるのに，次にカードを引くべき山が無くなっていた場合は失敗である．

途中で失敗した場合には，そのまま失敗で終了するか，または残ったカードの山をそのまま（山の番号もそのまま）にしてゲームを再開する．ゲームを再開する場合は，最初に引くカードはカードが残っている山のうちの一番左の山からとする（その山の一番上のカードが最初に引かれるカードとなる）．再開後も再開前と同様の方法でゲームを進め，すべての山にカードが無くなれば成功であり，まだカードが残っている山があるのに，次にカードを引くべき山が無くなった場合は失敗である．

このようなゲームの再開を最大 m 回まで行うものとする．ただし，m は 0 か 1 である．つまり，1 回も再開しないか，1 回だけ再開するかのいずれかである．ゲーム開始前のシャッフルの仕方によりカードの初期配置は異なる．当然，カードの初期配置により，再開せずに成功することもあれば，再開して成功することも，再開して失敗することもある．十分シャッフルしているので，どの初期配置も全て同じ確率で現れるものと考えることにして，再開が m 回以内で成功する確率 p を求めたい．この確率 p を小数で表し，小数第 r 位まで求めて出力するプログラムを作りなさい．ただし，次の条件を満たすように出力すること．

十分大きい正整数 K を取ると p \times 10^K が 整数となる場合，小数部は途中から 0 が続くが，その 0 も出力すること．例えば，p = 3/8 = 0.375 の場合，r = 5 なら 0.37500 と出力し，r = 2 なら 0.37 と出力する．p = 1.0 の場合も同様に，例えば r = 3 なら 1.000 と出力すること． 例えば 0.150000\cdots は循環小数 0.1499999\cdots として表すこともできるが，このような場合，前者の表し方を用いる． 入力の 1 行目には整数 n, k, m, r がこの順に空白を区切り文字として書いてある．1 \leqq n \leqq 10\,000，1 \leqq k \leqq 100，m = 0 または m = 1，1 \leqq r \leqq 10\,000 である．

出力においては，指定通りに出力した p の後に改行を入れること．

入力例 1

2 1 0 5

出力例 1

0.50000

入力例 2

3 1 1 3

出力例 2

0.833

入力例 3

2 2 1 3

出力例 3

1.000