With the approach of the Olympics, students' enthusiasm for sports is rising. As NOI2008 approaches, the school is planning to organize a table tennis tournament. Little Z, as a fanatical table tennis enthusiast, sees this as a great opportunity to show off his skills, so he is eager to sign up.

The tournament uses a knockout format, where the winner advances. Exactly $n$ students have signed up ($n$ is an integer power of 2, let $n = 2^k$). Therefore, after the first round, $2^{k-1}$ students will be eliminated, and $2^{k-1}$ students will advance to the next round; after the second round, $2^{k-2}$ students will advance, and so on, until the champion and runner-up are decided after $k$ rounds. Specifically, each person has an initial ID from $1$ to $n$, where Little Z's ID is $1$. All students have different IDs. They will be assigned to $n$ positions and then compete according to a tournament bracket similar to the one shown below:

To attract more students to participate, the prize money for this tournament is very generous. A player eliminated in the $i$-th round will receive a prize of $a_i$, and the champion will receive the highest prize of $a_{k+1}$. Obviously, the prize money satisfies $a_1 < a_2 < \dots < a_{k+1}$.

In the warm-up matches before the official tournament, Little Z lost repeatedly. After careful analysis, he discovered that the main reason for his failure was not his skill, but that the students who beat him happened to have a playing style that countered his, so he naturally lost once they played. Little Z wondered: how great would it be if he could avoid these students in the official tournament!

Assume that the winning probabilities between any two players are known, i.e., the probability that player $A$ beats player $B$ is $P_{A,B}$ (guaranteed that $P_{A,B} + P_{B,A} = 1$). Little Z hopes to determine the tournament bracket (by rearranging each player's position) to maximize his expected prize money. Can you help Little Z arrange a plan to maximize his expected prize money in this tournament?

Input

This is a submission-based problem; all input files match*.in are already in the corresponding directory.

The first line of the input file match*.in contains a positive integer $n$, representing the total number of participants. The data guarantees that there exists a non-negative integer $k$ such that $2^k = n$.

The next $n$ lines each contain $n$ real numbers between $0$ and $1$, $P_{i,j}$, representing the probability that the player with ID $i$ beats the player with ID $j$. Each real number is precise to two decimal places. Note specifically that $P_{i,i} = 0.00$.

The next $k+1$ lines each contain an integer representing the prize money for advancing to different rounds; the number in the $i$-th line is $a_i$.

Output

The output file match*.out includes $n$ lines. The number in the $i$-th line represents the ID of the student located at the $i$-th position. It is required that Little Z's ID must be at the 1st position.

Examples

Input 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

Output 1

1 
4 
2 
3

Note

After the first round, the probability of player 1 (Little Z) advancing is 80%, the probability of player 2 advancing is 60%, the probability of player 3 advancing is 40%, and the probability of player 4 advancing is 20%.

In the second round (the final), the probability that player 1 (Little Z) wins both rounds is $80\% \times (60\% \times 70\% + 40\% \times 60\%) = 52.8\%$. Therefore, the probability of Little Z failing in the first round is $P_1 = 1 - 0.8 = 0.2$, the probability of winning the first round but losing the second is $P_2 = 0.8 - 0.528 = 0.272$, and the probability of winning the championship is $P_3 = 0.528$.

Thus, the expected prize money is $0.2 \times 1 + (0.8 - 0.528) \times 2 + 0.528 \times 3 = 2.328$.

Implementation Details

We provide a tool called match_check to test whether your output file is acceptable. The method to use this tool is to use the following command in the terminal:

./match_check test_data_number

For example: ./match_check 10 tests whether your match10.out is valid.

After calling this program, match_check will provide the test results based on your output file, including:

• Illegal exit: Unknown error;
• Format error: Output file format error;
• Not a permutation: The output file is not a permutation of $1 \sim n$;
• OK. Your answer is xxx: The output file is accepted, where xxx is the corresponding expected prize money.

Subtasks

Each test case is scored individually.

For each test case, if your output file is invalid (e.g., file format error, output does not meet requirements), you receive 0 points for that test case. Otherwise, if your expected prize money is your_ans, the reference expected prize money is our_ans, and we also have a parameter $d$ for scoring, your score for that test case is:

If your_ans > our_ans, you get 12 points. If your_ans < our_ans * $d$, you get 1 point. Otherwise, the score is: $$\left\lfloor \frac{\text{your\_ans} - \text{our\_ans} \times d}{\text{our\_ans} - \text{our\_ans} \times d} \times 8 \right\rfloor + 2$$

Note

Mathematical Expectation

Mathematical expectation is one of the most basic numerical characteristics of a random variable. It reflects the average value of a random variable and is also known as the expectation or mean. It is a generalization of the simple arithmetic mean. For example, if a city has 100,000 families, 1,000 families have no children, 90,000 families have one child, 6,000 families have two children, and 3,000 families have three children, then the number of children in any family in the city is a random variable that can take values 0, 1, 2, 3, with probabilities 0.01, 0.9, 0.06, and 0.03 respectively. Its mathematical expectation is $0 \times 0.01 + 1 \times 0.9 + 2 \times 0.06 + 3 \times 0.03 = 1.11$, meaning that a family in this city has an average of 1.11 children.

The calculation of the expected value in this problem: Assume the probability that Little Z is defeated in the first round is $P_1$, the probability of winning the first round and being defeated in the second round is $P_2$, the probability of winning the first two rounds and being defeated in the third round is $P_3$, ..., then Little Z's expected prize money is: $$P_1 \times a_1 + P_2 \times a_2 + \dots + P_{k+1} \times a_{k+1}$$

Special Note

Please keep your input files *.in and your output *.out safe and back them up in time to avoid accidental deletion.