An undirected weighted graph is represented by a symmetric matrix, where zero means no edge. Convert it to an edge list.

Input

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

• 1 <= n <= 1000
• 0 <= A[i][j] <= 10^6

Output

Print each edge as u v w, once with u < v, in lexicographic order.

Example

Input

4
0 5 0 2
5 0 7 0
0 7 0 1
2 0 1 0

Output

1 2 5
1 4 2
2 3 7
3 4 1