One day you have invited Sohel bhai to come to East West University to see an intra-University table tennis match. Sohel bhai likes table tennis very much. So, he came to give you company.
In the intra-university table tennis match there were 16 players who played in the 1st round: in the 2nd round, 8 players: in the 3rd round, 4 players and in the final round obviously there are 2 players from whom 1 winner will be determined. So the game format would look like this:
A - - - - +
+ - - - - +
B - - - - + |
+ - - - - +
C - - - - + | |
+ - - - - + |
D - - - - + |
+ - - - - +
E - - - - + | |
+ - - - - + | |
F - - - - + | | |
+ - - - - + |
G - - - - + | |
+ - - - - + |
H - - - - + |
+ - - - -?
I - - - - + |
+ - - - - + |
J - - - - + | |
+ - - - - + |
K - - - - + | | |
+ - - - - + | |
L - - - - + | |
+ - - - - +
M - - - - + |
+ - - - - + |
N - - - - + | |
+ - - - - +
O - - - - + |
+ - - - - +
P - - - - +
Probability of every possible XXX vs. YYY will be given (total 16×16 = 256) which is sufficient to compute the probability of a given player's victory. Suppose P(M vs. N) = 80% , P(O vs. R) = 60%, P(M vs. O) = 70% and P(M vs. R) = 90%; then the probability of M getting to the 3rd round is 80%*(70%*60% + 90%*40%) = 62.4%.
In the middle of gossiping , Sohel bhai asked you to find out the chances of the players winning the competition. Now, you are to write a program to compute the chances of every player winning the competition.
There will be only one test case per file. The test case will start with 16 lines with the names of 16 players from top to bottom according to the outline given above. The names will be one word and at most 20 characters long. Then there will be a 16 × 16 matrix M given where Mi,j will give the probability in percent of the ith player defeating jth player.
Note that, matches will not end in draw and Mi,j + Mj,i = 100 for all i, j.
The output will contain 16 lines where each line consists of the name of the players followed by a space followed by its probability of winning the completion. The order of names of players should be the same as of input.
| Input | Output |
|---|---|
Marky Ricky Danny Terry Mickey Davey Timmy Tommy Joey Robby Johnny Brian Willy Chuck Skyler Sean 50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50 35 50 35 45 40 35 35 50 30 40 25 40 25 40 35 35 50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50 40 55 40 50 45 40 40 55 35 45 30 45 30 45 40 40 45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45 50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50 50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50 35 50 35 45 40 35 35 50 30 40 25 40 25 40 35 35 55 70 55 65 60 55 55 70 50 60 45 60 45 60 55 55 45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45 60 75 60 70 65 60 60 75 55 65 50 65 50 65 60 60 45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45 60 75 60 70 65 60 60 75 55 65 50 65 50 65 60 60 45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45 50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50 50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50 | Marky p=8.54% Ricky p=1.60% Danny p=8.06% Terry p=2.79% Mickey p=4.51% Davey p=7.50% Timmy p=8.38% Tommy p=1.56% Joey p=9.05% Robby p=3.23% Johnny p=13.72% Brian p=3.09% Willy p=13.79% Chuck p=3.11% Skyler p=5.53% Sean p=5.53% |