Icy Composer

Time Limit : 8 sec, Memory Limit : 65536 KB

F: 氷の作曲家

岡部錬太郎(愛称オカレン)は,西洋音楽の第一人者である. 彼は,5歳から作曲を行うことができた天才であり,彼が作詞・作曲した『攻城の槌』はとても有名である. 才能あふれるオカレンだが,残念なことに,彼は,レストランで食べた魚にあたって亡くなっている.

・・・少なくとも,この世界線では,そういうことになっている. 世界線とは何か? 一つの歴史は,一つの世界線に対応する. 我々が歩んできた歴史とは,無限に存在する世界線のうちの一つに過ぎず, 別の世界線では,また違った歴史が刻まれている.

オカレンは,自らを待ちうける過酷な未来に立ち向かうために,別の世界線へと旅立つことを決意したのだった. オカレンが目指す世界線は,かの有名な世界線「ヒャダインズゲート」である. 「ヒャダインズゲート」では,全ての魚は氷の魔法を用いて新鮮なまま冷凍保存されるため,魚にあたる人はいない.

世界線は,アルファベットの小文字からなる文字列で表される. 「ヒャダインズゲート」を表す文字列は既に解明されているが,非常に長い文字列で表される. これを簡潔に表記するため,文字列 seqN 回の繰り返しを N(seq) と圧縮して表す. ここで, N は,1以上の自然数であり, seq は小文字からなる文字列か,圧縮して表された文字列,または,それらをいくつか連結した文字列である.

例えば,以下の表記は,文字列 bbbababababxbbbababababx を表す.

2(3(b)4(ab)x)

オカレンは,彼のもつ「魔眼リーディングヒャダイナー」によって,彼がいる世界線から次に移動できる世界線を読みとることができる. 彼がいる世界線は,「ヒャダインズゲート」から遠く離れているため,直接「ヒャダインズゲート」へ移動することはできない. オカレンは,「ヒャダインズゲート」にできるだけ近づくために,「ヒャダインズゲート」に対する類似度が高い世界線へと移動することにした.

「ヒャダインズゲート」を表す文字列を x ,ある世界線を表す文字列をyとした場合, xに対するyの類似度は, y の部分文字列のうち, x にも部分文字列として現れるものの数である. ただし, y の部分文字列として同じ文字列が複数回現れたとしても,それらは,別々に数えるものとする. 類似度が同じ世界線が複数ある場合は,先に入力として与えられた世界線の方が類似度が高いとみなすものとする.

諸君には,世界線「ヒャダインズゲート」を表す文字列とオカレンが次に移動できる世界線に対応する文字列が複数与えられたときに,「ヒャダインズゲート」に対する類似度が最も高い世界線を求めてもらいたい.

健闘を祈る.
エル・プサイ・コンガリィ.

Input

入力は以下の形式で与えられる.

n m k
s
t1
t2
...
tk

入力形式の各変数の意味は以下の通りである.

  • n はヒャダインズゲートを表す文字列 s の長さ (1 <= n <= 250)
  • m はオカレンが移動できる世界線を表す文字列の長さ (1 <= m <= 400)
  • k はオカレンが移動できる世界線を表す文字列の数 (1 <= k <= 5)
  • s はヒャダインズゲートを表す文字列
  • ti はオカレンが移動できる世界線を表す文字列 (1 <= i <= k)

Output

文字列 s に最も類似する文字列 ti の番号 i と類似度を空白区切りで一行で出力せよ.

Sample Input 1

5 3 2
aaaaa
aaa
aab

Sample Output 1

1 6

Sample Input 2

10 3 3
2(ab)3(bc)
abc
bcb
cbc

Sample Output 2

2 6

Sample Input 3

13 24 1
2(3(b)4(ab)x)
bbbababababxbbbababababx

Sample Output 3

1 300

Sample Input 4

12 7 5
hyadainsgate
hyadain
mahyado
behoimi
megante
moshyas

Sample Output 4

1 28

Sample Input 5

44 6 5
sh1000(1000(1000(1000(ee))))t100(a)paz100(u)
sheeta
pazuuu
romusk
apalou
rlaput

Sample Output 5

2 21

Source: Ritsumeikan University Programming Camp 2012 , Day 3, Shiga, Japan, 2012-03-15