Given an undirected unweighted graph G=(V, E), a match is a collection of edges such that no two edges share a common vertex. In this problem you should collect as many as possible edges that construct matches in the graph.

Input

The first line contains n, the number of vertices in the graph. The next n lines contain n characters of '0' and '1', where '1' at position j in line i means there is an edge (i,j) in the graph.

There are no more than 500 vertices in the graph, and the vertices are labeled from 1 to n inclusive.

Output

Print each edge (pair of vertices) which is part of match collection. Each line contains two values, the vertices' label of the edge.

Example

Input:
6
001000
001000
110111
001010
001100
001000

Output:
5 4
2 3