Searching for a Hamiltonian cycle under Chvátal's conditions

Given a graph with N vertices that satisfies Chvátal's theorem, your task is to find a Hamiltonian cycle. According to Chvátal's theorem, for the sorted sequence of vertex degrees d_k, for any k < n/2, either d_k > k or d_{n - k} ≥ n-k must hold.

Input

The first line of the input contains an integer N (3 ≤ N ≤ 100), representing the number of vertices in the graph. The following N lines provide the adjacency matrix. Since the matrix is symmetric and the diagonal consists of zeros, the i-th line contains i-1 symbols, either zeros or ones. A one at the j-th position in the i-th line indicates an edge between vertices i and j.

Output

Output a permutation of N numbers, representing the vertex numbers in the order of the Hamiltonian cycle.

Examples