— Шеф выдал нам диск с саундтреками ко всем шести частям «Звёздных войн» и поручил проверить, что мелодия, которую мы хотим использовать в нашей игре, не похожа ни на одну из мелодий с этого диска. Говорит, хоть мы и сами её написали, любителям поживиться на авторском праве только дай повод. Вмиг засудят, и будем выплачивать многомиллионные штрафы.
— Но на то, чтобы прослушать все мелодии с этого диска, может уйти много часов. И сможем ли мы на слух определить похожую мелодию? Можно ли как-то автоматизировать этот процесс?
— Да, можно написать утилиту для сравнения мелодий. А потом прослушаем только те мелодии с диска, которые эта утилита посчитает сильно похожими на нашу. Предлагаю такой алгоритм сравнения. Если не учитывать паузы и длительности звуков, мелодию можно записать в виде строки из звуков. Назовём размером пересечения I(s, t) строк s и t равной длины количество позиций i, в которых s[i] = t[i]. Далее, абсолютной похожестью строк s и t назовём максимум I(u, v) для всех u, v, где u — подстрока s, v — подстрока t и длины u и v совпадают. Например, абсолютная похожесть строк «AAAAA» и «ABABA» равна трём, а строк «BABAB» и «ABABA» — четырём. Относительная похожесть нашей мелодии на мелодию с диска — это отношение их абсолютной похожести к длине мелодии с диска. Вот эту величину и будет вычислять наша утилита.

В первой строке описана мелодия, используемая в игре. Описание мелодии начинается с целого числа n — длины этой мелодии. За длиной следуют описания n звуков мелодии. Во второй строке записано единственное целое число m — количество мелодий на диске с саундтреками к «Звёздным войнам» (1 ≤ m ≤ 100). В следующих m строках описаны эти мелодии в том же формате, что и мелодия из игры. Длины всех мелодий лежат в пределах от 1 до 1000.

Звуки описываются строками вида «dN», «dN+» или «dN-», где d — номер октавы, N — символ ноты (заглавная латинская буква), а «+» или «-» — знаки повышения и понижения на полтона соответственно. Всего существует восемь октав, нумерующихся целыми числами от 1 до 8. В одной октаве 12 звуков: C, C+, D, D+, E, F, F+, G, G+, A, A+, B (звуки в октаве следуют именно в таком порядке). Для некоторых из этих звуков существует второй способ записи. Так, для одной октавы в парах (C+, D-), (D+, E-), (E, F-), (F, E+), (F+, G-), (G+, A-), (A+, B-) обе записи обозначают один и тот же звук. Также запись B+ обозначает звук C следующей октавы, а запись C- обозначает звук B предыдущей октавы. Звуков 1C- и 8B+ нет.

Выведите m строк по одному числу — относительную похожесть мелодии из игры на мелодии с диска. Ответ должен иметь абсолютную или относительную погрешность не более 10⁻⁶.