Вы играете в игру с несколькими честными шестигранными кубиками. На каждой грани каждого кубика изображён один символ. Цель игры — бросить кубики и составить допустимое слово из символов на верхних гранях. Если слово составить не удаётся, можно перебросить кубики и попробовать снова.

Рисунок K.1: Пять кубиков образуют допустимое слово, соответствующее первому примеру входных данных.

Пусть есть пять кубиков: один содержит буквы A, B, C, D, E и P (сокращённо ABCDEP), остальные — AEHOXU, AISOLR, ABCDEF и ABCSCC. После первого броска на верхних гранях соответственно выпали P, X, R, E и S. Из этих букв нельзя составить допустимое слово, поэтому вы оставляете P, S и E и перебрасываете остальные кубики, пытаясь получить PARSE, PAUSE, PHASE, POISE, PROSE, PULSE или PURSE. Два кубика дают E и A, и теперь буквы таковы: P, E, A, E и S. Вы всё ещё не можете придумать допустимое слово, поэтому оставляете четыре буквы и перебрасываете только последний кубик, у которого на трёх гранях C. Тогда с вероятностью 50% можно будет составить итоговое допустимое слово PEACE, как на рисунке K.1.

При броске каждая грань кубика выпадает с одинаковой вероятностью. Каково ожидаемое число бросков для получения допустимого слова при оптимальной стратегии?

Входные данные

Первая строка содержит два числа $d$ и $w$, где $d$ ($1 \le d \le 6$) — число кубиков, а $w$ ($1 \le w \le 2 \cdot 10^5$) — число допустимых слов в словаре. Каждая из следующих $d$ строк содержит 6 символов, по одному для каждой грани кубика. Последние $w$ строк содержат $w$ различных допустимых слов словаря. Каждое слово состоит ровно из $d$ символов.

Все символы входных данных — заглавные буквы (A–Z) или цифры (0–9).

Выходные данные

Если допустимое слово можно составить, выведите ожидаемое число необходимых бросков при оптимальной стратегии. Иначе выведите impossible. Абсолютная или относительная погрешность ответа должна быть не более $10^{-6}$.

Примеры

Входные данные 1

5 8
ABCDEP
AEHOXU
AISOLR
ABCDEF
ABCSCC
PARSE
PAUSE
PHASE
POISE
PROSE
PULSE
PURSE
PEACE

Выходные данные 1

9.677887141

Входные данные 2

2 1
AAAAAA
BBBBBB
AB

Выходные данные 2

1.0

Входные данные 3

3 1
123456
123456
123456
666

Выходные данные 3

10.555444555

Входные данные 4

2 1
ABCDEF
GHI234
AB

Выходные данные 4

impossible