1029. 部门

时间限制: 1.0 秒

内存限制: 64 MB

背景

F先生想要让一位部长签署一份文件。部长只有在文件得到其部门批准时才会签署。该部门是一栋有$M$层的建筑，楼层编号从1到$M$。每层有$N$个房间，编号从1到$N$。每个房间里有一名（且仅有一名）官员。

文件只有在被第$M$层的至少一名官员签署时才会被部门批准。一名官员只有在满足以下至少一个条件时才会签署文件：

• 该官员在一楼工作；

• 文件已被正下方楼层（即楼层号小1）相同房间号的官员签署；

• 文件已被相邻房间的官员签署（如果两个房间位于同一楼层且房间号相差1，则它们是相邻的）。

每位官员签署文件都会收取费用。费用是一个不超过$10^9$的正整数。

你需要找到批准文件的最便宜的方式。

输入

第一行包含整数$M$和$N$，分别表示建筑中的楼层数和每层的房间数（$1 \leq M \leq 100$；$1 \leq N \leq 500$）。接下来的$M$行，每行包含$N$个整数，描述费用（第$i$行第$j$个整数是第$i$层第$j$个房间的官员所需的费用）。

输出

输出为了以最便宜的方式批准文件而应访问的房间号序列（按访问顺序）。如果有多种方式导致相同的最低成本，你可以输出其中任意一种。

样例

输入

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

输出

3 3 2 1 1

注释

你可以假设对于每位官员，总存在一种方式（从一楼到该官员）以不超过$10^9$的费用获得文件批准。