Sharif Super Computer#6912
SSC is a supercomputer designed at Sharif University with controller and worker processors. It can run software in parallel: one of the controller processors loads the software onto the worker processors such that the memory and CPU usage among them are balanced, while the other controller is used for monitoring the system.
Because of the dependencies between different parts of the software, many messages should be exchanged between processors. A very fast network is needed to minimize the message passing overhead. To optimize the network, a clique structure will be constructed in which there is a direct communication cable between each pair of processors.
There are two different cables: blue cables, which can transmit up to Megabits per second, and red cables, which can transmit up to Gigabit per second. Each pair of worker processors will be connected by one blue cable. Due to the higher communication volume on controller processors, the two controllers are connected by one red cable, and also each controller is connected to each worker by another red cable.
SSC is thus made of n + 2 motherboards, each containing exactly one processor, the needed memory, and also n + 1 similar network sockets installed as a horizontal array. The motherboards are put in a vertical rack box, each on one horizontal shelf. So, each motherboard is uniquely identified by its height in the rack.
The cooling system has forced us to put the two controller motherboards on the lowest and highest shelves of the rack. We assume that the controller at the bottom has height , and the heights of the other motherboards are integers higher than . You, as a computer engineer, are asked to do the final assembly of SSC. You are given the empty rack box and the ready motherboards, and your job is to determine whether you can put the boards in the rack that satisfies the constraints and cable lengths.
There are exactly 2n + 1 red cables available with the given sizes. However, the blue cables are available in different sizes, and you have an unlimited number of cables in each size. You are so careful to keep the cabling between processors tidy and tight, so you want to install the motherboards in heights such that the size of cable used between each pair of motherboards is exactly equal to the difference between the heights of the two boards.
There are multiple test cases in the input. The first line of each test case contains two numbers (1 \leq n \leq 100) and (1 \leq m \leq 1000). The second line contains 2n + 1 integers, which are the sizes of Gigabit Ethernet cables. The third line contains integers, which are the sizes of Megabit Ethernet cable groups. The last line of the input contains two zeros.
For each data set, you should write n + 1 integers as the heights of the motherboards in the SSC rack box. The first number represents the height of the top controller processor, and the remaining integers are the positions of the workers in increasing order. In the case of having multiple solutions, write the lexicographically minimal one. If there is no solution, write Impossible.
Example 1