Humanity's Last Code Exam / 2023_K / Alea Iacta Est

You play a game with multiple fair six-sided dice. Each die’s face displays a single symbol. The objective of the game is to roll the dice and create a valid word from the symbols on top of each die. If you cannot form a word, you may reroll the dice for another attempt.

Suppose there are five dice: one of them contains letters `A, B, C, D, E, and P` (abbreviated as `ABCDEP`), and the other dice contain letters `AEHOXU`, `AISOLR`, `ABCDEF`, and `ABCSCC`. The first roll yields the following letters on the tops of respective dice: `P, X, R, E, and S`. As it is impossible to arrange these letters into a valid word, you decide to keep the `P, S, and E`, and reroll the other dice, in an attempt to make words like `PARSE, PAUSE, PHASE, POISE, PROSE, PULSE, or PURSE`. The two dice yield `E and A`, resulting in the following five letters: `P, E, A, E, and S`. You still cannot think of a valid word, so you decide to keep four letters and reroll only the last die, which has three sides with letter `C`. By doing so, there is a 50% chance that it will be possible to make a final valid word: `PEACE`.

When you roll a die, it lands on any one of its faces with equal probability. What is the expected number of rolls needed to make a valid word, assuming you use an optimal strategy?

### Input

The first line of input contains two numbers d and w, where 1≤d≤6 is the number of dice and 1≤w≤200,000 is the number of valid words in the dictionary. The following d lines each have 6 symbols, one for each face of the die. The final w lines contain w distinct valid words in the dictionary. Every word has exactly d symbols.

All symbols in the input are either uppercase letters (A–Z) or digits (0–9).

### Output

If it is possible to make a valid word, output the expected number of rolls needed to make a valid word when using an optimal strategy. Otherwise, output `impossible`. Your answer should have an absolute or relative error of at most 10^(−6).

### Sample Input and Output

#### Sample Input 1

You play a game with multiple fair six-sided dice. Each die’s face displays a single symbol. The objective of the game is to roll the dice and create a valid word from the symbols on top of each die. If you cannot form a word, you may reroll the dice for another attempt.

Suppose there are five dice: one of them contains letters `A, B, C, D, E, and P` (abbreviated as `ABCDEP`), and the other dice contain letters `AEHOXU`, `AISOLR`, `ABCDEF`, and `ABCSCC`. The first roll yields the following letters on the tops of respective dice: `P, X, R, E, and S`. As it is impossible to arrange these letters into a valid word, you decide to keep the `P, S, and E`, and reroll the other dice, in an attempt to make words like `PARSE, PAUSE, PHASE, POISE, PROSE, PULSE, or PURSE`. The two dice yield `E and A`, resulting in the following five letters: `P, E, A, E, and S`. You still cannot think of a valid word, so you decide to keep four letters and reroll only the last die, which has three sides with letter `C`. By doing so, there is a 50% chance that it will be possible to make a final valid word: `PEACE`.

When you roll a die, it lands on any one of its faces with equal probability. What is the expected number of rolls needed to make a valid word, assuming you use an optimal strategy?

### Input

The first line of input contains two numbers \(d\) and \(w\), where \(1 \leq d \leq 6\) is the number of dice and \(1 \leq w \leq 200,000\) is the number of valid words in the dictionary. The following \(d\) lines each have 6 symbols, one for each face of the die. The final \(w\) lines contain \(w\) distinct valid words in the dictionary. Every word has exactly \(d\) symbols.

All symbols in the input are either uppercase letters (A–Z) or digits (0–9).

### Output

If it is possible to make a valid word, output the expected number of rolls needed to make a valid word when using an optimal strategy. Otherwise, output `impossible`. Your answer should have an absolute or relative error of at most \(10^{-6}\).

### Sample Input and Output

#### Sample Input 1