Convert the adjacency matrix of an undirected simple graph to an edge list.

Input

The first line contains n. The next n lines contain the adjacency matrix.

• 1 <= n <= 1000
• A[i][j] is 0 or 1

Output

Print every edge u v once in increasing lexicographic order, with u < v.

Example

Input

4
0 1 0 1
1 0 1 0
0 1 0 0
1 0 0 0

Output

1 2
1 4
2 3