Internet Problem Solving Contest

IPSC 2002

Problem D – Space Suckers

Today is May 10, 2332. All earth resources were depleted many years ago. The war which followed gave rise to the Space Suckers Alliance - the mightiest organization in the solar system controlling the trade with valuable raw materials.

Your today's assignment as a Sucker Cadet is to fly your standard Elephant-class mining ship through the asteroid belt in the sector gamma. Your ship is equipped with a battery of M sucking-beam generators (SBGs) for collecting M different kinds of raw materials. Your prospectors have explored N asteroids and reported the materials present on them. You are assigned to collect all available materials from these asteroids. However, your SBGs are not very advanced. You have only one beam source mutually used by all SBGs. Individual SBGs can be independently open or closed. In order to suck materials from a given asteroid, you need to turn on the source. Once the source is turned on, all SBGs that are open will start sucking. You may not suck a material that is not present or your ship will explode. Moreover, each SBG can be opened and closed only once during your mission. Therefore, after you open a particular SBG, you can only visit the asteroids that contain the corresponding material until you close this SBG. Since SBGs can be opened and closed only once, asteroids containing any given material must form a contiguous block in your flight plan.

Input file specification

The first line contains two integers M and N, describing the number of SBGs and the number of asteroids respectively. M lines follow, each consisting of N characters, zeroes and ones. The j-th character on the i-th line is 1 if the raw material i is present on the asteroid j and 0 otherwise.

Output file specification

Output N numbers delimited by spaces describing the order in which to visit the asteroids so that all asteroids containing any given material are visited in a contiguous sequence. If there is more than one such ordering, output any of them. If no such ordering exists, output the word impossible.


Input file:
3 5
Output file:
5 3 4 1 2