問題文

タケシ君は自分の住んでいるX町の周辺でマラソンの練習をすることにしました.そこで,走る距離ごとにランニングコースを作成しようとしています.

X町周辺には,NN個の目印となる地点があります. ある地点ss (1sN)(1 \leq s \leq N)から,ちょうど距離KK走り,再び地点ssに戻ってこれるような地点ssをすべて列挙してください.ただし,同じ地点を複数回通るコースや,途中で地点ssを経由するコースもコースとして許容されます.

i,ji,j (1i,jN)(1 \leq i,j \leq N)について,Ai,j=1A_{i,j}=1ならば地点iiから地点jjへは距離11で移動することができ,Ai,j=0A_{i,j}=0ならば地点iiから地点jjへは直接移動することはできません.

制約

  • 1N501 \leq N \leq 50
  • 1K22×1041 \leq K \leq 2^{2 \times 10^4}
  • Ai,jA_{i,j}00または11
  • Ai,i=0A_{i,i}=0
  • 入力はすべて整数

入力

注意: KK22進数表記で与えられます!!!!

NN
KK
A1,1A1,NA_{1,1} \dots A_{1,N}
\vdots
AN,1AN,NA_{N,1} \dots A_{N,N}

出力

ある地点ssから,ちょうど距離KK走り,再び地点ssに戻ってこれるような地点ssを,地点の値の小さい順に空白区切りですべて出力してください.

そのような地点が11つもない場合は空行を出力してください.

サンプル

入力例1
6
100
0 1 0 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
1 0 0 0 0 1
0 0 0 1 0 0
0 0 0 1 0 0
出力例1
1 2 3 4 6

K=100(2)=4(10)K=100_{(2)}=4_{(10)}です.

地点11をスタートし,123411→2→3→4→1とちょうどKK回の移動で地点11に戻ってくることができます.

地点22をスタートし,234122→3→4→1→2とちょうどKK回の移動で地点22に戻ってくることができます.

地点33をスタートし,341233→4→1→2→3とちょうどKK回の移動で地点33に戻ってくることができます.

地点44をスタートし,412344→1→2→3→4とちょうどKK回の移動で地点44に戻ってくることができます.

地点55をスタートした場合,ちょうどKK回の移動で地点55に戻ってくることはできません.

地点66をスタートし,646466→4→6→4→6とちょうどKK回の移動で地点66に戻ってくることができます.

入力例2
3
101
0 1 0
0 0 1
1 0 0
出力例2

Submit


Go (1.21)