Bạn chơi một trò chơi với nhiều viên xúc xắc sáu mặt công bằng. Mỗi mặt của mỗi viên có một ký hiệu. Mục tiêu là gieo xúc xắc và tạo thành một từ hợp lệ từ các ký hiệu trên mặt trên của từng viên. Nếu không tạo được từ, bạn có thể gieo lại để thử tiếp.

Hình K.1: Năm viên xúc xắc tạo thành từ hợp lệ tương ứng với dữ liệu vào ví dụ 1.

Giả sử có năm viên xúc xắc: một viên có các chữ A, B, C, D, E và P (viết tắt ABCDEP), các viên còn lại có AEHOXU, AISOLR, ABCDEF và ABCSCC. Lần gieo đầu cho các chữ trên mặt trên lần lượt là P, X, R, E và S. Không thể sắp xếp chúng thành từ hợp lệ, nên bạn giữ P, S và E, rồi gieo lại các viên khác để thử tạo những từ như PARSE, PAUSE, PHASE, POISE, PROSE, PULSE hoặc PURSE. Hai viên cho E và A, nên năm chữ hiện tại là P, E, A, E và S. Bạn vẫn chưa nghĩ ra từ hợp lệ, nên giữ bốn chữ và chỉ gieo lại viên cuối, có ba mặt mang chữ C. Khi đó, có 50% khả năng tạo được từ hợp lệ cuối cùng PEACE, như Hình K.1.

Khi gieo một viên xúc xắc, mọi mặt có xác suất xuất hiện như nhau. Số lần gieo kỳ vọng cần để tạo một từ hợp lệ là bao nhiêu, nếu dùng chiến lược tối ưu?

Dữ liệu vào

Dòng đầu chứa hai số $d$ và $w$, với $d$ ($1 \le d \le 6$) là số viên xúc xắc và $w$ ($1 \le w \le 2 \cdot 10^5$) là số từ hợp lệ trong từ điển. Mỗi dòng trong $d$ dòng tiếp theo có 6 ký hiệu, mỗi ký hiệu cho một mặt của viên xúc xắc. $w$ dòng cuối chứa $w$ từ hợp lệ đôi một khác nhau trong từ điển. Mỗi từ có đúng $d$ ký hiệu.

Mọi ký hiệu trong đầu vào đều là chữ cái in hoa (A–Z) hoặc chữ số (0–9).

Dữ liệu ra

Nếu có thể tạo từ hợp lệ, in số lần gieo kỳ vọng cần thiết khi dùng chiến lược tối ưu. Ngược lại, in impossible. Đáp án phải có sai số tuyệt đối hoặc tương đối không quá $10^{-6}$.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

9.677887141

Dữ liệu vào 2

2 1
AAAAAA
BBBBBB
AB

Dữ liệu ra 2

1.0

Dữ liệu vào 3

3 1
123456
123456
123456
666

Dữ liệu ra 3

10.555444555

Dữ liệu vào 4

2 1
ABCDEF
GHI234
AB

Dữ liệu ra 4

impossible