Battle

RANDy is trying a new battle game called Nomekop. In this game you have to capture the Nomekops, strange creatures you find in the high grass, using Nome-cubes. To catch them you have to beat them in a battle.

A battle is composed of as many rounds as you like, each of which consists in a fight between your $N$ Nomekops against the $N$ Nomekops you just found. You know your team very well, each of your Nomekop has a strength value of $P_i$. Unfortunately, this is the first time you encounter your $N$ opponents, so you don't know their statistics yet. At each round, your Nomekops will attack the opponents in the order they are arranged (the first attacks the first, the second attacks the second and so on).

After each round, you will gain some experience points. For each Nomekop you obtain $P_i \times A_i$ points, where $P_i$ is the strength of your Nomekop, and $A_i$ is the (unknown) score multiplier of its opponent. Note that you only know the total score you get from a round, not the individual scores of each fight.

You can choose the order of your team before each round. Can you find the order that maximizes the score you get from a round?

Interaction

You will need to implement the function

std::vector<int> solve(int N, std::vector<int> P)

where P contains the strength values of your Nomekop, in some order.

For each match you want to do, you need to call the function

long long query(std::vector<int> C) 

where C is a permutation of your Nomekop strengths and the value returned is the total experience points you get with that order.

When you've found the optimal solution, you need to return the vector containing the optimal order of your Nomekop strengths.

Constraints

• $1 ≤ N ≤ 4 \ 000$.
• $1 ≤ A_i, P_i ≤ 10 \ 000 \ 000$ for each $i = 0 ... N − 1$.
• The order of the values in $A$ doesn’t change during the execution.
• Even though there is not a limit on the number of matches, each interaction takes some time. It’s guaranteed that at least $6 \ 000$ matches will fit in the time limit in C++.
• You must #include "query.h".
• Any optimal ordering will be accepted.

Scoring

• Your program will be tested against several test cases grouped in subtasks.
• In order to obtain the score of a subtask, your program needs to correctly solve all of its test cases.

Subtask 1 (10 points)

• $N ≤ 10$

Subtask 2 (30 points)

• $N ≤ 500$

Subtask 3 (30 points)

• $N ≤ 1 \ 000$

Subtask 4 (30 points)

• No additional limitations

Examples

This is an interactive task! The values returned depend on what you've written, so there is not a unique interaction. The one presented here is just an example.

In this example the battle is $5$ against $5$, and your Nomekops strengths are $3, 2, 3, 1$ and $5$.

For the sake of explanation, these are the values of $A$ (which you don't know from the input): $4, 4, 1, 1$, and $2$ (in this order).

Then, you can make some queries, and get the corresponding answers. Here there are some examples:

• query({3, 2, 3, 1, 5}) returns 34

If your Nomekops are arranged in the order $3, 2, 3, 1, 5$, the amount of experience you get is $34$.

After the first query, you can make other queries, for example:

• query({5, 3, 2, 1, 3}) returns 41

If your Nomekops are arranged in the order $5, 3, 2, 1, 3$, the amount of experience you get is $41$.

Assume that the optimal order is $5, 3, 2, 1, 3$.

Then solve will return {5, 3, 2, 1, 3}