Hide

Problem H
Historic Exhibition

The Benelux Artistic Pottery Consortium is preparing for an exhibit of its most prized urns and vases at a gallery in Nijmegen. Due to the sheer number of vases to be put on display the gallery has trouble finding a pedestal of the right size for every single vase. They have pedestals available that can either be placed normally or upside down and can be characterised by the diameter of their top and bottom surface. Moreover, the diameter of the top and bottom varies by at most one unit length.

For artistic reasons, it is important that the diameter of the base of a vase matches the diameter of the surface of the pedestal it is placed on. You have been asked to find a way to place all the vases on available pedestals. In order to make this work, you might need to turn some of the pedestals upside down. For example, Figure 1 shows a possible assignment of pedestals to vases for sample input $1$. Assist the gallery by writing a program to compute such an assignment.

\includegraphics[width=0.9\textwidth ]{figure.pdf}
Figure 1: Solution for sample input $1$.

Input

  • The first line contains two integers $0\leq p, v\leq 10^4$ the number of pedestals and the number of vases.

  • Then follow $p$ lines, the $i$-th of which contains two integers $1\leq a_ i,b_ i \leq 10^4$ denoting the diameters of the different sides of pedestal $i$. It is given that $|a_ i-b_ i|\leq 1$.

  • Then follows a single line containing $v$ integers $1\leq c_1,\dotsc ,c_ v\leq 10^4$, where $c_ i$ denotes the diameter of vase $i$.

Output

  • Output $v$ distinct integers $1\leq x_1,\dotsc ,x_ v\leq p$ such that vase $i$ can stand on pedestal $x_ i$, or print impossible if no assignment of vases to pedestals exists.

If there are multiple possible solutions, you may output any one of them.

Sample Input 1 Sample Output 1
4 3
1 2
4 5
2 3
2 2
1 2 3
1
4
3
Sample Input 2 Sample Output 2
2 2
1 1
2 3
1 1
impossible
Sample Input 3 Sample Output 3
2 3
9 8
4 5
4 9 5
impossible

Please log in to submit a solution to this problem

Log in