It is the future, and all plant life on Earth is extinc.
Fortunately, some specimens are preserved
in geodesic domes attached to a spaceship called Valley Forge.
The unique inhabitant of the spaceship is the drone Dewey,
who takes care of the plants.

Every dome has a unique code made up of uppercase letters.
All the codes have the same length.
Given two codes *x* and *y*,
define *f*(*x*, *y*) = ∑_{i} | *x*[*i*] − *y*[*i*] |.
Dewey visits the domes in a probabilistic way.
Let Dewey be at dome *x*.
Every noon, Dewey decides to stay in *x* with probability 1/2.
Otherwise, Dewey choses a new dome *y*
with probability proportional to *f*(*x*, *y*).

For example, suppose that the codes are
`AE`, `BB`, `CE` and `DG`,
and that Dewey is currently at `AE`.
Since *f*(`AE`, `BB`) = 4,
*f*(`AE`, `CE`) = 2
and *f*(`AE`, `DG`) = 5,
with sum 11,
Dewey stays at `AE` with probability 1/2,
and goes to `BB`, `CE` and `DG` with probabilities
1/2 · (4/11), 1/2 · (2/11) and 1/2 · (5/11), respectively.

Millions of days have passed,
and an alien spaceship meets Valley Forge.
For every dome, what is the probability that Dewey is there?
Assume that Dewey moves from one dome to another in just a few minutes,
that Dewey began at the dome with the smallest alphabetical code
in the morning,
and that the alien spaceship arrives on the evening
of the *p*-th day after Dewey started taking care of the plants
(for instance, *p* = 0 would mean the very same day,
so the probability that Dewey is at the initial dome would be 1/2).
Curiously, *p* is exactly the 10^{7}-th prime number.

**Input**

Input consists of several cases,
each one with the number of domes *n* followed by its codes:
*n* strings made up of only uppercase letters,
all different and with the same length.
You can assume 2 ≤ *n* ≤ 1000.

**Output**

For every case, print with four digits after the decimal point the probability that Dewey is at each dome when the aliens arrive. The input cases have no precision issues.

Public test cases

**Input**

4 AE BB CE DG 2 A B 5 KEY NEW ICE BYE MAP

**Output**

0.2200 0.3000 0.1800 0.3000 0.5000 0.5000 0.1710 0.1691 0.1746 0.3199 0.1654

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++