В преддверии выхода 8 сезона «Игры престолов» Глеб пересмотрел все предыдущие сезоны и так увлекся, что решил создать свою армию в борьбе против Короля Ночи. В игре престолов есть 7 королевств, но для усложнения задачи он построил свою вселенную с $n$ королевствами, где в каждом королевстве живет по $m$ человек. Для красоты и разнообразия он решил, что возьмет по человеку из каждого королевства и поставит их в ряд так, чтобы сумма модулей разности роста соседних в ряду людей была минимальна ($\sum_{i=1}^{n-1} |a_i − a_i+1|$). Глеб не смог решить данную задачу, поэтому просит вас помочь ему.

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

В первой строке задано два натуральных числа $n$ и $m$ ($1 \le n \cdot m \le 10^5$) — количество королевств и количество жителей в каждом королевстве. Следующие $n$ строк описывают королевства. Каждая из этих строк содержит m натуральных чисел $a_i$ ($1 \le a_i \le 10^9$), где $a_i$ — рост $i$-го человека в этом государстве.

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

Выведите последовательность чисел длины $n$ — рост каждого выбранного человека. Если ответов несколько, выведите ответ с минимальной суммой всех чисел.

Подзадачи