円環状に並び、$1$ から $n$ まで番号が付いた $n$ 個のアイテムからなるオンラインコレクションを閲覧しています。各アイテム $i$ の右隣はアイテム $i+1$ で、アイテム $n$ の右隣はアイテム $1$ です。同様に、各アイテム $i$ の左隣はアイテム $i-1$ で、アイテム $1$ の左隣はアイテム $n$ です。
アイテムには $1$ から $m$ まで番号が付いた $m$ 個のパラメータがあります。アイテム $i$ のパラメータ $j$ の値は整数 $a_{i,j}$ です。
閲覧中は常に、あるアイテムを指すポインタがあります。そのアイテムを現在のアイテムと呼びます。
さらに、絞り込み条件の集合を管理できます。各条件は組 $(j,v)$ であり、アイテムの $j$ 番目のパラメータが $v$ に等しくなければならないことを意味します。現在のアイテムは常に集合内のすべての条件を満たします。
コレクションを閲覧するために操作を行えます。各操作は次の四種類のいずれかです。
「右」をクリックする。ポインタは、すべての絞り込み条件を満たす、現在のアイテムの右側で最も近いアイテムに移動します。特に、現在のアイテムだけが条件を満たす場合、ポインタは動きません。
「左」をクリックする。同様に、ポインタは、すべての絞り込み条件を満たす、現在のアイテムの左側で最も近いアイテムに移動し、現在のアイテムだけが条件を満たす場合はその場にとどまります。
整数 $j$ と $v$ に対して、新しい絞り込み条件 $(j,v)$ を追加する。現在のアイテムがこの条件を満たす場合、ポインタは動きません。そうでなければ、ポインタは、新しい条件を含むすべての絞り込み条件を満たす、現在のアイテムの右側で最も近いアイテムに移動します。そのようなアイテムがなければ、この操作は不正であり実行できません。
集合から任意の絞り込み条件 $(j,v)$ を削除する。ポインタは動きません。
アイテムの各順序対 $(i,j)$ について、次の問いに答えてください。
- ポインタがアイテム $i$ を指し、絞り込み条件の集合が空の状態から閲覧を始めるとき、ポインタをアイテム $j$ に移動するために必要な操作回数の最小値はいくつですか？終了時の絞り込み条件の集合は任意でかまいません。
入力
最初の行には、コレクション内のアイテム数と各アイテムのパラメータ数を表す二つの整数 $n$ と $m$（$2\le n\le500$; $1\le m\le5$）が与えられます。
続く $n$ 行のうち $i$ 行目には、アイテム $i$ のパラメータの値を表す $m$ 個の整数 $a_{i,1},a_{i,2},\ldots,a_{i,m}$（$1\le a_{i,j}\le n$）が与えられます。
出力
それぞれ $n$ 個の整数を含む $n$ 行を出力してください。
$i$ 行目の $j$ 番目の整数は、絞り込み条件の集合が空の状態から、ポインタをアイテム $i$ からアイテム $j$ に移動するために必要な操作回数の最小値としてください。
入出力例
入力 1
9 3 5 3 7 5 3 4 5 3 7 5 3 2 5 3 4 5 3 7 2 3 7 5 3 7 2 3 7
出力 1
0 1 2 1 2 3 1 2 1 1 0 1 1 2 2 1 3 2 2 1 0 1 1 2 1 3 2 3 2 1 0 1 1 1 3 2 3 2 2 1 0 1 1 3 2 3 1 2 1 1 0 1 2 2 2 1 3 1 2 1 0 1 2 2 1 3 1 2 2 1 0 1 1 1 3 1 2 3 2 1 0
注記
入力例で、アイテム 2 からアイテム 5 へ移動する最短の方法の一つは次のとおりです。
新しい絞り込み条件 $(3,4)$ を追加します。アイテム 2 のパラメータ 3 の値は実際に 4 なので、ポインタはアイテム 2 にとどまります。
「右」をクリックします。ポインタは、有効な唯一の条件 $(3,4)$ を満たす、アイテム 2 の右側で最も近いアイテムへ移動します。これはアイテム 5 です。（代わりに「左」をクリックしても同じです。）
アイテム 8 からアイテム 3 へ移動する最短の方法の一つは次のとおりです。
新しい絞り込み条件 $(3,4)$ を追加します。アイテム 8 はこの条件を満たさないので、ポインタは、パラメータ 3 の値が 4 である、アイテム 8 の右側で最も近いアイテムへ移動します。これはアイテム 2 です。
絞り込み条件 $(3,4)$ を削除します。ポインタはアイテム 2 にとどまります。
「右」をクリックします。集合内に絞り込み条件がないので、ポインタはアイテム 3 に移動します。