Bobo 生活在一个由 $n$ 个城市组成的世界里，城市编号为 $1, 2, \dots, n$。城市之间由双向道路连接。

Bobo 想要制定一个计划 $(v_1, v_2, \dots, v_n)$，其中 $v_1, v_2, \dots, v_n$ 是 $n$ 个不同的城市。他可以在第 $1$ 天从城市 $v_1$ 出发，在第 $i$ 天到达城市 $v_i$ ($2 \le i \le n$)，并在第 $n+1$ 天回到城市 $v_1$。Bobo 很懒，所以他不喜欢那些在连续城市之间旅行超过 $k$ 条道路的计划。

输入格式

第一行包含两个整数 $n, k$ ($4 \le n \le 500, 3 \le k \le n - 1$)。

接下来的 $n$ 行，第 $i$ 行包含 $n$ 个整数 $g_{i,1}, g_{i,2}, \dots, g_{i,n}$ ($0 \le g_{i,j} \le 1, g_{i,j} = g_{j,i}$)。如果城市 $i$ 和城市 $j$ 之间有道路，则 $g_{i,j} = 1$，否则 $g_{i,j} = 0$。

保证城市之间是连通的。

输出格式

输出 $n$ 个整数 $v_1, v_2, \dots, v_n$ 表示该计划。任何可行的计划均可。

样例

样例输入 1

4 3
0100
1010
0101
0010

样例输出 1

1 3 2 4