코드 매칭

제임스는 본부와 통신하기 어려운 나라에서 일하는 스파이다. 그는 숫자 방송국을 통해 라디오 신호로 상관에게서 지시를 받는다. 숫자 방송국은 암호화된 의미를 담은 숫자열을 가끔 읽어 주는 라디오 방송국이다. 제임스는 숫자열(예: "732736")을 지시(예: "임무를 중단하라")에 대응시킨 암호책을 가지고 있다. 암호책의 숫자열은 각각 서로 다른 지시 하나에 대응한다.

제임스는 게을러서 라디오를 가끔만 확인한다. 상관들도 이를 알고 있어서, 그가 숫자열의 임의의 자리부터 듣기 시작한다고 가정한다. 각 자리에서 시작할 확률은 같다. 첫 자리에서 시작할 수도 있고 마지막 자리에서 시작할 수도 있다. 지시는 중요하므로, 본부는 제임스가 메시지를 해독하는 데 걸리는 시간을 정확히 알아야 한다. 제임스는 자신이 들은 내용과 일치하는 메시지가 하나뿐이라고 확신하는 순간 듣기를 멈추고 행동한다. 이때 그가 자리를 맞추기 전에 놓친 숫자가 있을 수 있다는 점도 고려한다.

숫자 하나를 읽는 데 1초가 걸린다. 마지막 숫자 뒤에는 1초 동안 침묵이 이어지며, 이 침묵으로 제임스는 메시지가 끝났음을 안다. 본부가 보낼 수 있는 메시지마다, 제임스가 메시지를 이해할 때까지 듣는 시간의 기댓값을 구하라. 끝까지 들은 뒤에도 어떤 메시지인지 구분하지 못하는 경우가 있다. 이때는 "Impossible"을 출력한다.

암호책과 보낼 숫자열이 주어졌을 때, 제임스가 라디오를 듣는 시간의 기댓값을 구하라.

첫 줄에 정수 $N$ ($N \le 100\,000$)이 주어진다. 이는 암호책에 있는 숫자열의 개수이다. 다음 $N$개 줄에는 숫자열이 한 줄에 하나씩 주어진다. 모든 숫자열 길이의 합은 100,000을 넘지 않는다.

$N$줄을 출력한다. $i$번째 줄에는 본부가 암호책의 $i$번째 메시지를 보냈을 때, 제임스가 메시지를 확실히 알게 될 때까지 듣는 시간의 기댓값(초)을 출력한다. 상대 오차 $10^{-5}$까지 허용한다. 제임스가 메시지를 끝내 알아낼 수 없을 가능성이 있다면 해당 줄에 "Impossible"을 출력한다.