Education

EduCorp opened the Bootcamp Academy of Economics to get into the private education business. Against its own early projections, the academy is growing fast.

It is growing so fast that the students no longer fit in the current building. New buildings are on the way, and until they are ready the students have to sit somewhere else.

Each department sells its original space and moves into a rented building of its own. Departments never share, so one building holds exactly one department. This is an economics academy, so the capacity and the rent of every building available nearby were already collected in a survey disguised as homework.

What is left is choosing which buildings to rent so that the total rent is as small as possible.

The first line contains the number of departments $n$ and the number of buildings $m$. ($1 \le n \le m \le 5000$)

The second line contains the integers $s_1, \dots, s_n$, where $s_i$ is the number of students in department $i$. ($1 \le s_i \le 1000$)

The third line contains the integers $p_1, \dots, p_m$, where $p_j$ is the capacity of building $j$. ($1 \le p_j \le 1000$)

The fourth line contains the integers $r_1, \dots, r_m$, where $r_j$ is the yearly rent of building $j$. ($1 \le r_j \le 1000$)

The numbers on one line are separated by single spaces.

If the departments cannot all be given a building, print impossible on the first line.

Otherwise print the integers $v_1, \dots, v_n$ on one line, separated by single spaces. $v_i$ is the number of the building rented by department $i$. Two departments never rent the same building, and $p_{v_i} \ge s_i$ holds for every $i$.

Several assignments can reach the smallest total rent $r_{v_1} + \dots + r_{v_n}$. Only the one built by the following rule is accepted.

Handle the departments in order of decreasing student count, and handle departments with the same student count in increasing order of their number. On a department's turn, rent the cheapest building among the buildings that no department has rented yet and whose capacity is at least that department's student count. If several of those buildings have the same rent, rent the one with the smallest number. If a department's turn has no building left to rent, print impossible.

This rule always produces an assignment whose total rent is minimum.