Tournament Champion Prediction

In an elimination tournament, there are \(2^n\) players numbered \(1,2,3,\ldots,2^n\). The tournament is held in \(n\) rounds. In each round, the remaining players are sorted by their numbers and paired sequentially: the first with the second, the third with the fourth, and so on. In each match there is no draw and only the winner advances to the next round. After \(n\) rounds, only one player remains and is crowned the champion.

You are given a matrix \(P\) of size \(2^n \times 2^n\) where \(P_{i,j}\) (using 1-indexing) denotes the probability that player \(i\) wins against player \(j\) if they meet. It is guaranteed that \(P_{i,i} = 0\) for all \(i\), and for \(i \neq j\), \(0 \leq P_{i,j} \leq 1\). Using the tournament structure, compute the champion probabilities for every player and output the label of the player with the maximum chance to win the tournament. If there is a tie, output the smallest label among those.

Note: All formulas are represented in \(\LaTeX\) format. For instance, the number of players is given by \(2^n\), and the win probability of player \(i\) when facing player \(j\) is \(P_{i,j}\).

inputFormat

The first line contains an integer \(n\) representing the number of rounds. There will be \(2^n\) players in the tournament.

This is followed by \(2^n\) lines, each containing \(2^n\) space-separated real numbers. The j-th number in the i-th line represents \(P_{i,j}\), the probability that player \(i\) wins against player \(j\).

outputFormat

Output a single integer: the label (1-indexed) of the player who has the highest probability of winning the tournament.

sample

2
0 0.7 0.6 0.8
0.3 0 0.5 0.6
0.4 0.5 0 0.55
0.2 0.4 0.45 0

1