2195: Король ночі

Бали: 25,00 (partial)

Time limit: 1.0s

Memory limit: 256M

Input: stdin

Output: stdout

Author:

zvit

Problem type

Напередодні виходу 8 сезону «Гри престолів» Степан переглянув всі попередні сезони і так захопився, що вирішив створити свою армію в боротьбі проти Короля Ночі. У «Грі престолів» є 7 королівств, але для ускладнення завдання він побудував свій всесвіт з ~n~ королівствами, де в кожному королівстві живе по ~m~ людей. Для краси і різноманітності він вирішив, що візьме по одній людині з кожного королівства і поставить їх в ряд так, щоб сума модулів різниці ростів сусідніх в ряду людей була мінімальна ~\sum_{i=1}^{n-1}|{a_i - a_{i+1}}|~.

Степан не зміг виконати це завдання, і тому просить вас допомогти йому.

Input

У першому рядку задано два натуральних числа ~n~ і ~m~ (~1 \le n \cdot m \le 10^5~) - кількість королівств і кількість жителів в кожному королівстві.

Наступні ~n~ рядків описують королівства. Кожен з цих рядків містить ~m~ натуральних чисел ~a_i~ (~1 \le a_i \le 10^9~), де ~a_i~ - ріст ~i~-ї людини в цьому королівстві.

Output

Виведіть послідовність чисел довжиною ~n~ - кожне число це ріст вибраної людини. Якщо відповідей декілька, то виведіть відповідь з мінімальною сумою всіх чисел.