Description

Now, Xiao W wants the robot to help him complete $n$ tasks.

Each task has two attributes: the money needed to complete it $w_i$, and the success probability $p_i$.

Xiao W needs to arrange the tasks in some order. Then, the robot will do the tasks in the following way:

• Start from the first task.
• After paying the cost to do task $i$, if it succeeds, then continue to do task $i+1$; otherwise, restart from the first task.
• After successfully completing task $n$, the process ends.

For example, when $n=2$, one possible process is:

• Do task $1$, fail.
• Do task $1$, succeed.
• Do task $2$, fail.
• Do task $1$, succeed.
• Do task $2$, succeed.
• Process ends, and the total cost is $3w_1+2w_2$.

Now, Xiao W wants you, who are studying OI, to help him find an ordering that makes his expected cost as small as possible.

Input Format

The first line contains an integer $n$, the number of tasks.

The next line contains $n$ integers $w_1,w_2,\cdots,w_n$, as described above.

The next line contains $n$ integers $P_1,P_2,\cdots,P_n$, where $P_i=p_i\times10^4$, and the meaning of $p_i$ is as described above.

Output Format

If it is impossible to complete the tasks no matter what, output one line with the string Impossible.

Otherwise, output one line with $n$ integers $c_1,c_2,\cdots,c_n$, which is a permutation of $1,2,\cdots,n$. This represents the task order: the $i$-th arranged task is task $c_i$ in the input.

2
999 1
5000 10000

1 2

1
1
0

Impossible

Hint

Explanation for Sample 1: You can understand it intuitively. Since task $2$ is guaranteed to succeed, putting it last is definitely not worse.

Explanation for Sample 2: Obviously, this task can never be completed, because its success probability is $0$.

Note: Whether the task succeeds or not, you always have to pay the cost $w_i$ to attempt it.

This problem uses $\text{SPJ}$. If your output is at least as good as the answer output (or both are Impossible), then you will get full score on this test point; otherwise, you will get $0$ score on this test point.

For some reason, this problem does not provide the $\text{SPJ}$ to contestants.

Constraints:
For $10\%$ of the testdata, $1\le n\le 10$.
For another $20\%$ of the testdata, all $w_i$ are equal.
For another $20\%$ of the testdata, all $p_i$ are equal.
For all testdata, $1\le n\le 2\times10^5$, $1\le w_i\le 10^9$, $0\le P_i\le10^4$.

Translated by ChatGPT 5