Министерство

Мистер F. хочет подписать документ у министра. Министр подпишет документ, только если он будет одобрен его министерством. Министерство представляет собой M-этажное здание, этажи которого пронумерованы с 1 до M (1 ≤ M ≤ 100). На каждом этаже расположено N комнат (1 ≤ N ≤ 500), пронумерованных от 1 до N. В каждой комнате находится один (и только один) чиновник.

Документ считается одобренным министерством, если он подписан как минимум одним чиновником с M-го этажа. Чиновник подписывает документ, если имеет место хотя бы одно из следующих условий:

• чиновник работает на 1-ом этаже;

• документ подписан чиновником, который находится в комнате с тем же номером, но этажом ниже;

• документ подписан чиновником из соседней комнаты (комнаты считаются соседними, если они расположены на одном этаже и номера их комнат отличаются на единицу).

Каждый чиновник берет плату за подписание документа. Плата является натуральным числом, не превышающим 10^9. Найти самый дешевый путь, которым можно подписать документ.

Входные данные

Первая строка содержит количество этажей M в здании и количество комнат N на этаже. Каждая из следующих M строк содержит N чисел, разделенных пробелом, которые описывают гонорары чиновников (k-ое число l-ой строки указывает на гонорар чиновника, сидящего в k-ой комнате на l-ом этаже).

Выходные данные

Вывести номера комнат в порядке их посещения для подписания документа за минимальную плату. Если таких путей подписания несколько, вывести любой из них.