Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FACUP - The FA cup

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.

Photobucket

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.


Được gửi lên bởi:Lê Đôn Khuê
Ngày:2008-06-27
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST WHITESPACE
Nguồn bài:VNOI Marathon'08-Round3/DivA
Problem Setter:LêĐônKhuê
Origin:UVA

hide comments
2014-10-08 17:10:19 Nguyễn Ðức Linh
hay!
2014-06-04 13:29:57 Nguyễn Lê Lý Bằng
vãi cả FA cup :)))
2011-05-25 17:32:21 Noyethug


Last edit: 2012-09-30 10:47:13
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.