It is March, and the NCAA basketball tournament is happening soon. You're trying to figure out which teams have the best chances at winning the tournament.
Leading "bracketologists" have calculated, for each team, their probability of winning against each of the other teams. In other words, you know, for every pair of teams, the probability of each of the two teams winning in a game between the two teams, which can be represented by a table (more information in the input section).
There are $n$ teams in the tournament. $n$ will always be a power of two. Each team is given a unique number (their "seed"), from 1 to $n$.
In the first round of the tournament, the team with seed $s$ plays the team with the seed $n$ - $s$ + 1. For example, in the first round of an 8-team tournament, the 1 seed will play the 8 seed, the 2 seed will play the 7 seed, and the 3 seed will play the 6 seed.
After the first round, the teams that lost their match are eliminated from the tournament, and the teams that won their match move on to the next round.
In the next round, there are $frac(n, 2)$ teams still left in the tournament. If every team with a lower numbered seed won each game, the second round proceeds similarly to the first round. For example, in the second round of an 8 player tournament where every lower numbered seed won each first round game, the 1 seed plays the 4 seed, and the 2 seed plays the 3 seed.
If a higher numbered seed won a first round game, they will play in the second round game that the team they beat would have played in. For example, if the 7 seed beat the 2 seed in the first round of an 8 player tournament, then the 7 seed would play the 3 seed in the second round, or the 6 seed, if the 6 seed beat the 3 seed in the first round.
This process repeats until the finals, when the winner of the finals wins the whole tournament.
Given the probability table described above, sort the teams by their probability to win the entire tournament.
The first line contains a single positive integer $n$: the number of teams in the tournament. $n$ is guaranteed to be a power of two.
The next line contains $n$ space-separated strings: the name of each team in the tournament.
The next $n$ lines each contain $n$ space-separated integers. The $j$th integer on the $i$th line represents the probability that the $i$th seeded team will beat the $j$th seeded team. The probabilities will be given as an integer percentage out of 100. The probability that a team will beat themselves will be given as 50
Output $n$ lines. Each line should contain the name of each team, a space, and the probability that the team will win the tournament, given as a percentage out of 100, rounded to the nearest integer. Sort the teams from highest to lowest, based on their probability of winning the tournament.
Note that you should round your answers after sorting the list of teams and their win probabilities.
## Input
The first line contains a single positive integer $n$: the number of teams in the tournament. $n$ is guaranteed to be a power of two.The next line contains $n$ space-separated strings: the name of each team in the tournament.The next $n$ lines each contain $n$ space-separated integers. The $j$th integer on the $i$th line represents the probability that the $i$th seeded team will beat the $j$th seeded team. The probabilities will be given as an integer percentage out of 100. The probability that a team will beat themselves will be given as 50
## Output
Output $n$ lines. Each line should contain the name of each team, a space, and the probability that the team will win the tournament, given as a percentage out of 100, rounded to the nearest integer. Sort the teams from highest to lowest, based on their probability of winning the tournament.Note that you should round your answers after sorting the list of teams and their win probabilities.
[samples]
**Definitions**
Let $ n = 2^k $ for some $ k \in \mathbb{N} $ be the number of teams.
Let $ T = \{t_1, t_2, \dots, t_n\} $ be the set of teams, indexed by seed $ i \in \{1, \dots, n\} $.
Let $ P = [p_{ij}] \in [0,1]^{n \times n} $ be the probability matrix where $ p_{ij} $ is the probability that team $ i $ beats team $ j $, with $ p_{ii} = 0.5 $.
Let $ \mathcal{R}_0 = \{1, 2, \dots, n\} $ be the initial seed ordering.
For round $ r \in \{1, \dots, k\} $, define the bracket structure recursively:
- In round $ r $, the $ n / 2^{r-1} $ remaining teams are paired such that the winner of the match between seeds $ a $ and $ b $ (from round $ r-1 $) faces the winner of the match between seeds $ c $ and $ d $, where the original bracket structure is preserved: teams are grouped into blocks of size $ 2^{k-r+1} $, and within each block, the top half (lower seeds) plays the bottom half (higher seeds) in a fixed hierarchical structure based on initial seeding.
Let $ W_i \in [0,1] $ denote the probability that team $ i $ wins the entire tournament.
**Constraints**
1. $ n \in \{2, 4, 8, 16, 32, 64, 128, 256\} $ (power of two).
2. $ p_{ij} \in \{0, 1, \dots, 100\} / 100 $, with $ p_{ij} + p_{ji} = 1 $ for $ i \ne j $, and $ p_{ii} = 0.5 $.
3. Tournament structure follows single-elimination bracket with fixed initial pairing: seed $ s $ vs seed $ n - s + 1 $ in round 1. Subsequent rounds preserve bracket integrity: winners advance to the slot their defeated opponent would have occupied.
**Objective**
Compute $ W_i $ for each team $ i \in \{1, \dots, n\} $, where:
$$
W_i = \sum_{\text{all valid tournament paths } \pi \text{ where } i \text{ wins}} \prod_{\text{matches in } \pi} p_{\text{winner} \to \text{opponent}}
$$
Then, sort the teams by $ W_i $ in descending order.
Output each team name and $ \text{round}(100 \cdot W_i) $ as an integer percentage, one per line.