Giải bài trực tuyến

The FA Cup is the oldest footbal cup. All the matches will play on knock-out rule. There are 2^N teams in the cup playing in N rounds. There are 2^(N-1) matches in the first round and 2^(N-1) winners advances to the second round. And so on. Until there is only a team left. This is the champion.

Matches in the first round are numbered as 1 to 2^(N-1): team 1 vs team 2, team 3 vs team 4, ..., and team (2^N-1) vs team 2^N. Matches in the second round are: match 1's winner vs match 2's winner, ..., match 2^(N-2)'s winner vs match 2^(N-1) winner.

Matches in the second round are numbered as 1 to 2^(N-2) and matches in the third round are: match 1's winner vs match 2's winner, ..., match 2^(N-3)'s winner vs match 2^(N-2) winner.

There is no tie in a game (if a game is tied at the end of regulation time it goes into extra time and/or penalty shootout). Given the fixtures and result's probability of every matches. Your task is to sort the teams decreasingly according to the chance of becoming champion.

Input

• The first line containg an integer N (1 ≤ N ≤ 8).
• In the next lines there is a matrix P of size (2^N) * (2^N) containing integers in the interval [0, 100]. P[x, y] is the percentage that team x can defeat team y. The sum of P[x, y] and P[y, x] is always 100 and P[x, x] = 0 for all x.

Output

Print out 2^N lines. Each line contains the index of a team sorted in deceasing order according to the chance of become champion for a team. If there are two teams with the same chance of becoming champion, print the team with smaller index first.

Example

Input
2
 0 90 50 50
10  0 10 10
50 90  0 50
50 90 50  0


Output
1
3
4
2

Description

Let the teams be MANCHESTER, FULHAM, ARSENAL, CHELSEA. The giants MANCHESTER, ARSENAL, CHELSEA all have 90% winning chance when vs FULHAM. When the three teams plays with one another, the winning chance is equally 50%-50%. However, because MANCHESTER has advantages in playing schedule, they have the highest chance to become champion.

MANCHESTER is the champion if:

- MANCHESTER wins over FULHAM, MANCHESTER wins over ARSENAL and ASERNAL wins over CHELSEA. This probability is 90% * 50% * 50% = 22.5%

- MANCHESTER wins over FULHAM, MANCHESTER wins over CHELSEA and CHELSEA wins over ARSENAL. This probability is 90% * 50% * 50% = 22.5%

MANCHESTER has a total of 45% chance to become FA Cup's winner.

ARSERNAL wins FA cup if:

- ARSENAL wins over CHELSEA, ARSENAL wins over MANCHESTER, MANCHESTER wins over FULHAM. This probability is 50% * 50% * 90% = 22.5%

- ARSENAL wins over CHELSEA, ARSENAL wins over FULHAM, FULHAM wins over MANCHESTER. This probability is 50% * 90% * 10% = 4.5%

ARSENAL has a total of 27% chance to become FA Cup's winner.

CHELSEA's chance to win FA Cup is calculated in the same way as ARSENAL and is also 27%.

FULHAM wins FA Cup if:

- FULHAM wins over MANCHESTER, FULHAM wins over ARSENAL and ARSENAL wins over CHELSEA. This probability is 10% * 10% * 50% = 0.5%

- FULHAM wins over MANCHESTER, FULHAM wins over CHELSEA and CHELSEA wins over ARSENAL. This probability is 10% * 10% * 50% = 0.5%

So FULHAM has only 1% chance to become FA Cup's winner.