The annual college sports-ball tournament is approaching, which for trademark reasons we'll refer to as Third Month Insanity. There are a total of 2^{N} teams participating in the tournament, numbered from 1 to 2^{N}. The tournament lasts N rounds, with each round eliminating half the teams. The first round consists of 2^{N} - 1 games, numbered starting from 1. In game i, team 2·i - 1 will play against team 2·i. The loser is eliminated and the winner advances to the next round (there are no ties). Each subsequent round has half as many games as the previous round, and in game i the winner of the previous round's game 2·i - 1 will play against the winner of the previous round's game 2·i.

Every year the office has a pool to see who can create the best bracket. A bracket is a set of winner predictions for every game. For games in the first round you may predict either team to win, but for games in later rounds the winner you predict must also be predicted as a winner in the previous round. Note that the bracket is fully constructed before any games are actually played. Correct predictions in the first round are worth 1 point, and correct predictions in each subsequent round are worth twice as many points as the previous, so correct predictions in the final game are worth 2^{N} - 1 points.

For every pair of teams in the league, you have estimated the probability of each team winning if they play against each other. Now you want to construct a bracket with the maximum possible expected score.


-----Input-----

Input will begin with a line containing N (2 ≤ N ≤ 6).

2^{N} lines follow, each with 2^{N} integers. The j-th column of the i-th row indicates the percentage chance that team i will defeat team j, unless i = j, in which case the value will be 0. It is guaranteed that the i-th column of the j-th row plus the j-th column of the i-th row will add to exactly 100.


-----Output-----

Print the maximum possible expected score over all possible brackets. Your answer must be correct to within an absolute or relative error of 10^{ - 9}.

Formally, let your answer be a, and the jury's answer be b. Your answer will be considered correct, if $\frac{|a - b|}{\operatorname{max}(1,|b|)} \leq 10^{-9}$.


-----Examples-----
Input
2
0 40 100 100
60 0 40 40
0 60 0 45
0 60 55 0

Output
1.75

Input
3
0 0 100 0 100 0 0 0
100 0 100 0 0 0 100 100
0 0 0 100 100 0 0 0
100 100 0 0 0 0 100 100
0 100 0 100 0 0 100 0
100 100 100 100 100 0 0 0
100 0 100 0 0 100 0 0
100 0 100 0 100 100 100 0

Output
12

Input
2
0 21 41 26
79 0 97 33
59 3 0 91
74 67 9 0

Output
3.141592



-----Note-----

In the first example, you should predict teams 1 and 4 to win in round 1, and team 1 to win in round 2. Recall that the winner you predict in round 2 must also be predicted as a winner in round 1.

Difficulty: interview

Starter code:

Solutions:
import functools
n = int(input())

props = []
def preproc(a):
    return float(a)/100.

for i in range(pow(2,n)):
    props.append(list(map(preproc, input().split())))

wining_props = []  # list of lists. First index -- number of round, second -- num of team, value -- prop of wining

wining_props_first_round = []
for i in range(0, (2 ** n), 2):
    # i, and i+1 teams playing
    wining_prop_for_i = props[i][i + 1]
    wining_props_first_round.append(wining_prop_for_i)
    wining_props_first_round.append(1. - wining_prop_for_i)

wining_props.append(wining_props_first_round)
assert len(wining_props_first_round) == len(props)

for round_num in range(2, n + 1):
    # calculate propabilitys for winning in i round for each team
    # prop of winning in i round = prop of winning prev round + mo of win this one
    # mo win this = for each team we can meet prop of them wining prev * prop we win them
    # each team we can meet on round i  = all teems // 2^i == we//2^i
    this_round_wining_props = []
    for team_num in range(2 ** n):
        t = team_num // (2 ** round_num) * (2 ** (round_num))
        teams_we_meet_this_round = [t + x for x in range(2 ** round_num)]
        t = team_num // (2 ** (round_num-1)) * (2 ** (round_num-1))
        teams_we_meet_prev_round = [t + x for x in range(2 ** (round_num-1))]
        for tt in teams_we_meet_prev_round:
            teams_we_meet_this_round.remove(tt)

        this_team_wining_props = wining_props[round_num - 2][team_num]  # -2 cause numeration

        chances_win_i_team = []
        for tm in teams_we_meet_this_round:
            # chances we meet them * chances we win
            chances_win_i_team.append(wining_props[round_num - 2][tm] * props[team_num][tm])

        mo_win_this_round = sum(chances_win_i_team)

        this_team_wining_props *= mo_win_this_round

        this_round_wining_props.append(this_team_wining_props)

    #assert 0.99 < sum(this_round_wining_props) < 1.01
    wining_props.append(this_round_wining_props)

# now we got props of each win on each round. Lets bet on most propable winer and calculate revenue

#from left to right-1 is playing
@functools.lru_cache(maxsize=None)
def revenue(round_num, teams_left, teams_right, winner=-1):
    split = ((teams_left + teams_right) // 2)

    # let the strongest team win, we bet, and calculate to the bottom
    if round_num == 1:
        return wining_props[0][winner] if winner != -1 else max(wining_props[0][teams_left:teams_right])

    if winner == -1:
        results = []
        for winner in range(teams_left, teams_right):
            winner_prop = wining_props[round_num - 1][winner]

            if winner >= split:
                res = sum(
                    [revenue(round_num - 1, teams_left, split), revenue(round_num - 1, split, teams_right, winner),
                     winner_prop * (2 ** (round_num - 1))])
            else:
                res = sum(
                    [revenue(round_num - 1, teams_left, split, winner), revenue(round_num - 1, split, teams_right),
                     winner_prop * (2 ** (round_num - 1))])
            results.append(res)

        return max(results)

    else:
        winner_prop = wining_props[round_num - 1][winner]

        if winner >= split:
            res = sum(
                [revenue(round_num - 1, teams_left, split), revenue(round_num - 1, split, teams_right, winner),
                 winner_prop * (2 ** (round_num - 1))])
        else:
            res = sum(
                [revenue(round_num - 1, teams_left, split, winner), revenue(round_num - 1, split, teams_right),
                 winner_prop * (2 ** (round_num - 1))])

        return res

print(revenue(n, 0, (2 ** n)))


n = int(input())
m = 1 << n
p = [list(map(int, input().split())) for i in range(m)]
u, x = [1] * m, [0] * m
v, y = u[:], x[:]
for i in range(n):
    d = 1 << i
    for j in range(m):
        s = d * (j // d ^ 1)
        v[j] = u[j] * sum(u[k] * p[j][k] for k in range(s, s + d)) / 100
        y[j] = max(x[s: s + d]) + x[j] + v[j] * d
    u, v, x, y = v, u, y, x
print(max(x))

n = int(input())
m = 1 << n
p = [list(map(int, input().split())) for i in range(m)]
u, x = [1] * m, [0] * m
v, y = u[:], x[:]
for i in range(n):
    d = 1 << i
    for j in range(m):
        s = d * (j // d ^ 1)
        v[j] = u[j] * sum(u[k] * p[j][k] for k in range(s, s + d)) / 100
        y[j] = max(x[s: s + d]) + x[j] + v[j] * d
    u, v, x, y = v, u, y, x
print(max(x))

n = int(input())
# Using the same index I would for a tree
m = 2**n

points = [0]*(2*m)
points[1] = 2**(n-1)
for i in range(1,m):
    x = points[i]//2
    points[2*i] = x
    points[2*i+1] = x



P = [[int(x)/100.0 for x in input().split()] for _ in range(m)]
state = [[0.0]*64 for _ in range(2*m)]

for i in range(m):
    state[m+i][i] = 1.0
    
for i in reversed(range(1,m)):
    for j in range(m):
        for k in range(j+1,m):
            # x is probability that team j meets team k in match i
            x = state[2*i][j]*state[2*i+1][k]

            state[i][j] += P[j][k]*x
            state[i][k] += P[k][j]*x

score = [[0]*64 for _ in range(2*m)]
for i in reversed(range(1,m)):
    for j in range(m):
        for k in range(m):
            score[i][j] = max(score[i][j], score[2*i][j]+state[i][j]*points[i] + score[2*i+1][k])
            score[i][j] = max(score[i][j], score[2*i+1][j]+state[i][j]*points[i] + score[2*i][k])
print(repr(max(score[1])))