Vous jouez avec plusieurs dés équilibrés à six faces. Chaque face porte un seul symbole. Le but est de lancer les dés et de former un mot valide avec les symboles sur leurs faces supérieures. Si vous ne pouvez pas former de mot, vous pouvez relancer les dés pour réessayer.

Figure K.1 : Cinq dés formant un mot valide correspondant à l'entrée d'exemple 1.

Supposons qu'il y ait cinq dés : l'un porte les lettres A, B, C, D, E et P (abrégées ABCDEP), et les autres AEHOXU, AISOLR, ABCDEF et ABCSCC. Le premier lancer donne sur les faces supérieures respectives P, X, R, E et S. Comme il est impossible de les arranger en un mot valide, vous gardez P, S et E et relancez les autres dés, dans l'espoir de former PARSE, PAUSE, PHASE, POISE, PROSE, PULSE ou PURSE. Les deux dés donnent E et A, d'où les cinq lettres P, E, A, E et S. Vous ne trouvez toujours pas de mot valide ; vous gardez donc quatre lettres et relancez uniquement le dernier dé, dont trois faces portent C. Il y a alors 50% de chances de pouvoir former le mot valide final PEACE, comme sur la figure K.1.

Lors d'un lancer, chaque face d'un dé apparaît avec la même probabilité. Quelle est l'espérance du nombre de lancers nécessaires pour former un mot valide avec une stratégie optimale ?

Entrée

La première ligne contient deux nombres $d$ et $w$, où $d$ ($1 \le d \le 6$) est le nombre de dés et $w$ ($1 \le w \le 2 \cdot 10^5$) le nombre de mots valides du dictionnaire. Chacune des $d$ lignes suivantes comporte 6 symboles, un par face du dé. Les $w$ dernières lignes contiennent $w$ mots valides distincts du dictionnaire. Chaque mot comporte exactement $d$ symboles.

Tous les symboles de l'entrée sont des lettres majuscules (A–Z) ou des chiffres (0–9).

Sortie

S'il est possible de former un mot valide, affichez l'espérance du nombre de lancers nécessaires avec une stratégie optimale. Sinon, affichez impossible. Votre réponse doit avoir une erreur absolue ou relative d'au plus $10^{-6}$.

Exemples

Entrée 1

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

Sortie 1

9.677887141

Entrée 2

2 1
AAAAAA
BBBBBB
AB

Sortie 2

1.0

Entrée 3

3 1
123456
123456
123456
666

Sortie 3

10.555444555

Entrée 4

2 1
ABCDEF
GHI234
AB

Sortie 4

impossible