CHEM - Chemistry

The story started some 5,000 years ago in Ancient Egypt, was continued by the Greeks and Arabs, reached France, Europe, and finally conquered the world. The studies on the compositions of waters, the humans’ greed for purified materials, millions of experiments and many brilliant minds made chemistry what it is today: No more the quest of the Philosopher’s stone, but the study of matter and the changes it undergoes.

There remain nevertheless still groups of stout-hearted followers of ancient believes, so-called alchemist. Keeping their research top-secret, they meet once a year for a conference where they share their recent findings. This year’s location is Lausanne and Extremely Purified Fluorescent Liquids (EPFL) is the topic. The idea is that the chemists brew together some new EPFLs. As we speak about state of the art EPFLs, it is necessary that certain chemists put their very specific knowledge together. Thus for a certain EPFL E1, the presence of chemists C1, C2 and C3 may be required. For another E2, chemists C1 and C4 might be necessary.

 Although chemists are generally very patient people, as their reactions might take long times, they get very impatient if they are to observe experiments in which they are not involved. As an example, chemist C4 would go crazy if he had to assist to the brewage of E1. To ensure a pleasant stay in Lausanne to every chemist, you are to arrange their departure and arrival dates so that each chemist is available whenever his knowledge is required, but is not in Lausanne when other EPFLs are created.

To this purpose, you are given a schedule with ones and zeros. Each column stands for one EPFL, each row for one chemist. There is a 1 at position (Ci,Ei) if chemist Ci is needed for EPFL Ei, and a zero otherwise. Your task boils now down on rearranging the columns in a way that all ones are consecutive in every line. For traditional reasons, the organizers’ EPFL is always brewed first and corresponds to the first column of the input schedule (E1).

Input

The input consists of several test-cases separated by an empty line. Each test-case starts with the number of chemists C (1<=C<=400), followed by the number of EPFLs E (1<=E<=400). Then follow C lines of E characters, ‘1’ or ‘0’. You may assume that there exists exactly one order of EPFLs (initiated by E1) that meets the above constraints. Input terminates on a test-case with C=E=0, which must not be processed.

Output

Print each output on a line by itself, which holds E numbers, corresponding to the initial position in the planning, arranged such that all chemists are available when necessary and away from Lausanne otherwise. (the first number must always be 1 as a tribute to the host).

Example

Input:
6 5
00010
01000
10101
10100
00011
00101

0 0

Output:
1 3 5 4 2

Added by:Christian Kauth
Date:2010-10-27
Time limit:7.058s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2014-08-31 17:47:05 Recycle Bin
Weak test case..
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.