题目描述

随着奥运的来临，同学们对体育的热情日益高涨。在 NOI2008 来临之际，学校正在策划组织一场乒乓球赛。小 Z 作为一名狂热的乒乓球爱好者，这正是他大展身手的好机会，于是他摩拳擦掌，积极报名参赛。

本次乒乓球赛采取淘汰赛制，获胜者晋级。恰好有 $n$($n$ 是 $2$ 的整数次幂，不妨设 $n = 2^k$)个同学报名参加，因此第一轮后就会有 $2^{k-1}$ 个同学惨遭淘汰，另外 $2^{k-1}$ 个同学晋级下一轮；第二轮后有 $2^{k-2}$ 名同学晋级下一轮，… 依次类推，直到 $k$ 轮后决出冠亚军：具体的，每个人都有一个 $1\sim n$ 的初始编号，其中小 Z 编号为 $1$，所有同学的编号都不同，他们将被分配到 $n$ 个位置中，然后按照类似下图的赛程进行比赛：

上图：$n=8$ 时比赛的赛程表

为了吸引更多的同学参加比赛，本次比赛的奖金非常丰厚。在第 $i$ 轮被淘汰的选手将得到奖金 $a_i$ 元，而冠军将获得最高奖金 $a_{k+1}$ 元。显然奖金应满足 $a_1<a_2<\cdots<a_{k+1}$。

在正式比赛前的热身赛中，小 Z 连连败北。经过认真分析之后，他发现主要的失败原因不是他的球技问题，而是赢他的这几个同学在球风上刚好对他构成相克的关系，所以一经交手，他自然败阵。小 Z 思索：如果在正式比赛中能够避开这几位同学，该有多好啊!

假设已知选手两两之间交手的胜率，即选手 $A$ 战胜选手 $B$ 的概率为 $P_{A,B}$ (保证 $P_{A,B}+P_{B,A}=1$)。于是小 Z 希望能够通过确定比赛的对阵形势（重新给每个选手安排位置），从而能够使得他获得尽可能多的奖金。你能帮助小 Z 安排一个方案，使得他这场比赛期望获得的奖金最高么？

输入格式

这是一道提交答案型试题，所有的输入文件 match*.in 已在附加文件中。

输入文件 match*.in 第一行包含一个正整数 $n$，表示参赛的总人数，数据保证存在非负整数 $k$，满足 $2^k=n$。

接下来 $n$ 行，每行有 $n$ 个 $0$ 到 $1$ 间的实数 $P_{i,j}$，表示编号为 $i$ 的选手战胜编号为 $j$ 的选手的概率，每个实数精确到小数点后两位。特别注意 $P_{i,i}=0.00$。

接下来 $k+1$ 行，每行一个整数分别为晋级各轮不同的奖金，第 $i$ 行的数为 $a_i$。

输出格式

输出文件 match*.out 包括 $n$ 行，第 $i$ 行的数表示位于第 $i$ 个位置的同学的编号，要求小 Z 的编号一定位于第 $1$ 个位置。

4
0.00 0.70 0.60 0.80
0.30 0.00 0.60 0.40
0.40 0.40 0.00 0.70
0.20 0.60 0.30 0.00
1
2
3

1
4
2
3

提示

样例解释

第一轮比赛过后，编号为 $1$ 的选手(小 Z)晋级的概率为 $80\%$，编号为 $2$ 的选手晋级的概率为 $60\%$，编号为 $3$ 的选手晋级的概率为 $40\%$，编号为 $4$ 的选手晋级的概率为 $20\%$。

第二轮（决赛），编号为 $1$ 的选手（小 Z）前两轮均获胜的概率为 $80\%\times (60\%\times 70\%+40\%\times 60\%)=52.8\%$，因此，小 Z 在第一轮失败的概率 $P_1=1-0.8=0.2$，第一轮胜出但第二轮败北的概率 $P_2=0.8-0.528=0.272$，获得冠军的概率 $P_3=0.528$。

从而，期望奖金为 $0.2\times 1+(0.8-0.528)\times 2+0.528\times 3=2.328$。

如何测试你的输出

我们提供 checker 来测试你的输出文件是否可接受。

调用这个程序后，checker 将根据你得到的输出文件给出测试的结果，其中包括：

• 非法退出：未知错误；
• Format error：输出文件格式错误；
• Not a permutation：输出文件不是一个 $1\sim n$ 的排列；
• OK.Your answer is xxx：输出文件可以被接受，xxx为对应的期望奖金。

评分方法

每个测试点单独评分。

对于每一个测试点，如果你的输出文件不合法，如文件格式错误、输出解不符合要求等，该测试点得 $0$ 分。否则如果你的输出的期望奖金为 $\text{your\_ans}$，参考期望奖金为 $\text{our\_ans}$，我们还设有一个用于评分的参数 $d$，你在该测试点中的得分如下：

• 如果 $\text{your\_ans}>\text{our\_ans}$，得 $12$ 分。
• 如果 $\text{your\_ans}<\text{our\_ans}\times d$，得 $1$ 分。
• 否则得分为：$$\left\lfloor\frac{\text{your\_ans}-\text{our\_ans}\times d}{\text{our\_ans}-\text{our\_ans}\times d}\times 8\right\rfloor+2 $$

特别提示

请妥善保存输入文件 *.in 和你的输出 *.out，及时备份，以免误删。

附加文件

checker 需要自行编译后使用。

请前往 Github 下载 testlib.h 的最新源代码。