30778번 - Мультиплеер в змейке 다국어

문제

Компания Konia, специализирующаяся на выпуске бюджетных мобильных устройств, в последнее время теряет свои позиции на рынке. Ради спасения компании совет директоров пошел на отчаянный шаг: было решено внести изменения в самую известную игру, которая доступна на всех устройствах от Konia — «Змейку».

Правила этой игры очень просты. На клетчатом поле, состоящем из N строк и M столбцов, находится змейка, изначально имеющая длину 1 (т. е. представляющая собой квадратик 1 × 1). На каждом ходу змейка перемещается на одну клетку в одном из четырёх направлений: вверх, вниз, влево или вправо. Если при этом змейка пересекает какую-либо границу экрана, то она появляется с противоположной стороны. Например, сделав шаг влево из первой клетки четвёртой строки (будем говорить, что такая клетка имеет координаты (4, 1)) на поле размером 10 строк на 8 столбцов, змейка окажется в клетке с координатами (4, 8). Иногда на поле появляется еда, которая может увеличить длину змейки, но это не имеет отношения к данной задаче.

По предложению совета директоров в Змейку было решено добавить режим парной игры. Изначально змейки двух игроков появляются в разных клетках и имеют длину 1, то есть состоят только из клеток, в которых они появились. Каждый ход состоит из того, что сначала перемещается змейка первого игрока, а затем змейка второго игрока. Правила перемещения аналогичны описанным выше для одиночной игры, но, в отличие от одиночного режима, змейки имеют возможность столкнуться друг с другом, после чего игра заканчивается. Маркетинговые исследования показали, что пользователи предпочитают как можно более длинные игры, поэтому перед разработчиками стоит задача исследовать, как зависит длительность игры от начальных координат змеек (a₁, b₁) и (a₂, b₂). Так как в режиме парной игры пока реализована только возможность передвигаться, еда на поле не появляется, и фактически игра сводится к управлению двумя одноклеточными змейками.

Вам, как ведущему инженеру компании, поручено контролировать деятельность коллег. Для это необходимо написать программу, которая по заданным размерам поля N и M и координатам двух различных клеток (a₁, b₁) и (a₂, b₂) вычисляет, на каком по счёту ходу впервые может возникнуть ситуация, что змейки столкнутся, то есть одна змейка совершит ход в клетку, в которой находится другая.

입력

В первой строке ввода содержатся целые числа N и M (1 ⩽ N, M ⩽ 1 000 000), задающие соответственно количество строк и количество столбцов на игровом поле. Обратите внимание, что строки нумеруются от 1 до N снизу вверх, а столбцы — от 1 до M слева направо

Во второй строке записаны два целых числа a₁ и b₁ (1 ⩽ a₁ ⩽ N, 1 ⩽ b₁ ⩽ M) — изначальные координаты змейки первого игрока: сначала номер строки, затем номер столбца.

В третьей строке аналогично задаются a₂ и b₂ — изначальные координаты змейки второго игрока.

Гарантируется, что в начале игры змейки игроков находятся в разных клетках.

출력

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

제한

노트

В первом тесте существует единственная клетка в которой змейки могут встретиться через один ход — клетка с координатами (5, 6).