题目描述

xuzhenyi要办个签证。办证处是一座$\red{M}$层的大楼，$\red{1<=M<=100}$。每层楼都有$\red{N}$个办公室，编号为$\red{1..N(1<=N<=500)}$。每个办公室有一个签证员。签证需要让第$\red{M}$层的某个签证员盖章才有效。每个签证员都要满足下面三个条件之一才会给xuzhenyi盖章：

$\red{1}$. 这个签证员在$\red{1}$楼

$\red{2}$. xuzhenyi的签证已经给这个签证员的正楼下（房间号相同）的签证员盖过章了。

$\red{3}$. xuzhenyi的签证已经给这个签证员的相邻房间（房间号相差$\red{1}$，楼层相同）的签证员盖过章了。

每个签证员盖章都要收取一定费用，这个费用不超过$\red{1000000000}$。 找出费用最小的盖章路线，使签证生效

输入格式

第$\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

提示

由于没有CHECK请输出最短的路径如果还是$\red{WA}$,请更换下更新解的条件,也许要加个等号