题目描述

Mr. F. 需要让一位部长签署一份文件。部长只有在文件被其部门批准后才会签署。该部门所在的办公楼有 $M$ 层（$1 \leq M \leq 100$），楼层编号从 $1$ 到 $M$。每层楼有 $N$ 个房间（$1 \leq N \leq 500$），房间编号从 $1$ 到 $N$。每个房间里有且仅有一位官员。

文件只有在被至少一位第 $M$ 层的官员签署后才会被批准。一位官员签署文件的条件是至少满足以下条件之一：

1. 该官员位于第 $1$ 层；
2. 文件已被位于正下方楼层（即当前楼层减 $1$）且房间号相同的官员签署；
3. 文件已被同一楼层的相邻房间（相邻房间指房间号相差 $1$ 的房间）的官员签署。

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

你需要找到批准文件的最便宜的方式，并输出签署路径的房间号（每行一个）。如果存在多条最便宜的路径，输出其中任意一条即可。

输入格式

第一行包含两个整数 $M$ 和 $N$，用空格分隔。接下来的 $M$ 行，每行包含 $N$ 个用空格分隔的整数，表示每层楼各房间官员的签署费用（第 $l$ 行的第 $k$ 个整数表示第 $l$ 层第 $k$ 个房间官员的费用）。

输出格式

输出签署路径的房间号（每行一个），按访问顺序排列。

示例输入 1

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

示例输出 1

3
3
2
1
1

提示

你可以假设对于每位官员，总存在一种方式从第 $1$ 层到该官员签署文件，且总费用不超过 $10^9$。

由于输入数据较大，请使用 scanf() 而非 cin 读取数据以避免超时。

来源

Ural Collegiate Programming Contest 1999