Bobo 有一个 $n \times n$ 的对称矩阵 $C$，其中元素均为 0 或 1。对于 $1, \dots, n$ 的一个排列 $p_1, \dots, p_n$，令 $$c_i = \begin{cases} C_{p_i, p_{i+1}} & \text{对于 } 1 \le i < n \\ C_{p_n, p_1} & \text{对于 } i = n \end{cases}$$ 当且仅当满足 $c_i \neq c_{i+1}$ 的下标 $i$ ($1 \le i < n$) 的数量至多为 1 时，称排列 $p$ 是“几乎单色”的。

对于给定的矩阵 $C$，请找出一个几乎单色的排列 $p_1, \dots, p_n$。

输入格式

输入包含多组测试数据，以文件结束符（EOF）结束。对于每组测试数据： 第一行包含一个整数 $n$。 接下来的 $n$ 行中，第 $i$ 行包含 $n$ 个整数 $C_{i,1}, \dots, C_{i,n}$。

• $3 \le n \le 2000$
• 对于每个 $1 \le i, j \le n$，$C_{i,j} \in \{0, 1\}$
• 对于每个 $1 \le i, j \le n$，$C_{i,j} = C_{j,i}$
• 对于每个 $1 \le i \le n$，$C_{i,i} = 0$
• 在每组输入中，$n$ 的总和不超过 2000。

输出格式

对于每组测试数据，如果存在几乎单色的排列，输出 $n$ 个整数 $p_1, \dots, p_n$ 表示该排列。否则，输出 -1。 如果存在多个几乎单色的排列，输出其中任意一个均可。

样例

输入 1

3
001
000
100
4
0000
0000
0000
0000

输出 1

3 1 2
2 4 3 1

说明

对于第一组测试数据，$c_1 = C_{3,1} = 1$，$c_2 = C_{1,2} = 0$，$c_3 = C_{2,3} = 0$。仅当 $i = 1$ 时，$c_i \neq c_{i+1}$。因此，排列 3, 1, 2 是一个几乎单色的排列。