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

Містер 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-му поверсі).

Вихідні дані

Виведіть номери кімнат у порядку їх відвідування для підписання документа за мінімальну плату. Якщо існує кілька таких шляхів, виведіть будь-який з них.