题目描述

魔法学院是一个庞大的机构。一件事情能否被顺利执行需要通过各级领导的层层审批, 这天,墨老师因为研制基囚武器的计刘需要审批，他来到了学院的办公大楼。办公大楼是一 座$\red{M}$层的大楼,$\red{1≤}$$\red{M≤}$$\red{100}$。每层楼都有$\red{N}$个办公室,编号为$\red{1,...,N(1≤}$$\red{N≤}$$\red{500),}$每个 办公室有一个领导。计划必领要让第$\red{M}$层的某个领导审批通过才行。

每个领导都要满足下面三个条件之一才会给审批通过:

$\red{(1)}$这个领导在$\red{1}$楼。

$\red{(2)}$计划已经给这个领导的正楼下，房间号相同的领导审批通过了。

$\red{(3)}$计划已经给这个领导的相邻房间,房间号相差$\red{1,}$楼层相同的领导审批通过了。

墨老师每到一个领导处审批都要付出一番口舌说服,这是必须付出的代价.代价值不超 过$\red{1 000 000 000}$。

请找出代价最小的审批路线,使计划生效。

输入格式

第$\red{1}$行两个整数$\red{M}$和$\red{N}$。 接下来$\red{M}$行每行$\red{N}$个整数,第$\red{i}$行第$\red{j}$个数表示说服第$\red{i}$层的第$\red{j}$个领导的代价。

输出格式

按顺序打出你经过的房间的编号,每行一个数。

如果有多条费用最小的路线.输出最短的路径。

样例

输入样例

3 4
10 10 1 10
2 2 2 10
1 10 10 10

输出样例

3
3
2
1
1