Convert an adjacency matrix to adjacency lists.

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

For every vertex i, print i: followed by all j with A[i][j] = 1, in increasing order.

Example

Input

3
0 1 1
1 0 0
1 0 0

Output

1: 2 3
2: 1
3: 1