Divide the set of vertices of the given graph into two nonempty subsets A and B so that the number of edges between vertices of different subsets is minimal.

Input

First line contains the number of vertices n (2 ≤ n ≤ 50) in the graph. Each of the next n lines contains n characters. i-th symbol in j-th line equals to "1" if there is an edge between vertices i and j, and "0" otherwise. The adjacency matrix of the graph thus defined is antireflexive (there are zeros on the main diagonal) and symmetric (relative to the main diagonal).

Output

In the first line print the numbers of vertices in the set A, and in the second line print the numbers of the vertices in the set B. The vertex numbers can be output in any order.