A tournament is a directed graph without self-loops in which every pair of vertexes is connected by exactly one directed edge. That is, for any two vertexes u and v (u ≠ v) exists either an edge going from u to v, or an edge from v to u.

You are given a tournament consisting of n vertexes. Your task is to find there a cycle of length three.

Input

The first line contains an integer n (1 ≤ n ≤ 5000). Next n lines contain the adjacency matrix A of the graph (without spaces). A_i, j = 1 if the graph has an edge going from vertex i to vertex j, otherwise A_i, j = 0. A_i, j stands for the j-th character in the i-th line.

It is guaranteed that the given graph is a tournament, that is, A_i, i = 0, A_i, j ≠ A_j, i(1 ≤ i, j ≤ n, i ≠ j).

Output

Print three distinct vertexes of the graph a₁, a₂, a₃ (1 ≤ a_i ≤ n), such that A_a1, a2 = A_a2, a3 = A_a3, a1 = 1, or "-1", if a cycle whose length equals three does not exist.

If there are several solutions, print any of them.

Examples

Input

5 00100 10000 01001 11101 11000

Output

1 3 2

Input

5 01111 00000 01000 01100 01110

Output

-1

cycle

思路：

就是用搜索，以一排展开，dfs含有两个参数，这两个参数代表这个位置为1，所有，再去搜索，按照没有搜索的一排展开，

找到这个值。

AC之后，之前这个题目思路有一些混乱，再整理一下

在一个dfs要考虑到三个数，dfs里面的两个参数就是其中两个数，然后找到这两个参数中任意一个对应得第三个数，

再判断第三个数和另一个参数有没有相互对应，有就返回了，没有继续判断这一行有没有被标记，标记了就不用，没有标记就

继续进行搜索。值得确定得是，第一确实每一个都搜到了，没有遗漏，第二，就是搜索得递归，可以再仔细想想

#include 
        
         #include 
         
          #include 
          
           using namespace std;const int maxn=5050;char ana[maxn][maxn];bool bna[maxn][maxn],vis[maxn];int n,a,b,c;int dfs(int x,int y){    vis[x]=1;    for(int i=1;i<=n;i++)    {        if(bna[x][i])        {            if(y&&bna[i][y])            {                a=y;                b=x;                c=i;                return 1;            }            if(!vis[i]) if(dfs(i,x)) return 1;        }    }    return 0;}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)    {        scanf("%s",ana[i]+1);        for(int j=1;j<=n;j++)        {            bna[i][j]=ana[i][j]-'0';        }    }    for(int i=1;i<=n;i++)    {        if(!vis[i])        {            if(dfs(i,0))            {                printf("%d %d %d\n",a,b,c);                return 0;            }        }    }    printf("-1\n");    return 0;}