Problem Background

This problem is a template for the Dancing Links algorithm—the exact cover problem.

Problem Description

Given an \( N \) rows by \( M \) columns matrix, each element in the matrix is either \( 1 \) or \( 0 \).

You need to select several rows from the matrix such that for each column \( j \), among the selected rows, there is exactly one row where the \( j \)-th element is \( 1 \).

Input Format

The first line contains two numbers \( N \) and \( M \).

The next \( N \) lines, each containing \( M \) digits \( 0 \) or \( 1 \), represent the matrix.

Output Format

Output a single line with several numbers representing the answer, separated by spaces. Any valid solution is acceptable, and the order does not matter.

If there is no solution, output No Solution!.

Sample Input and Output

Sample Input #1

3 3
0 0 1
1 0 0
0 1 0

Sample Output #1

2 1 3

Sample Input #2

3 3
1 0 1
1 1 0
0 1 1

Sample Output #2

No Solution!

Notes

For \( 100\% \) of the data, \( N, M \leq 500 \), and the number of \( 1 \)s in the matrix does not exceed \( 5000 \).

见题面 Input 部分

见题面 Output 部分