멀티플레이어 뱀 게임

Konia는 저가형 모바일 기기를 만드는 회사인데, 최근 시장 점유율을 잃고 있다. 회사를 살리기 위해 이사회는 Konia의 모든 기기에 기본으로 설치된 가장 유명한 게임인 뱀 게임을 바꾸기로 결정했다.

규칙은 간단하다. 길이가 1인 뱀(1 × 1 크기의 칸 하나)이 $N$행 $M$열의 격자판 위에 있다. 한 번의 이동마다 뱀은 위, 아래, 왼쪽, 오른쪽 중 한 방향으로 한 칸 움직인다. 화면의 경계를 넘으면 반대편 경계에 나타난다. 예를 들어 10행 8열 격자판에서 칸 $(4, 1)$에서 왼쪽으로 한 칸 움직이면 뱀은 칸 $(4, 8)$에 놓인다. 격자판에 먹이가 나타나 뱀을 길게 만들 수도 있지만, 이 문제와는 관련이 없다.

격자판에 두 명이 함께 하는 모드가 추가된다. 처음에 두 플레이어의 뱀은 서로 다른 칸에 나타나며, 길이는 모두 1이다. 즉 각 뱀은 시작 칸 하나로만 이루어진다. 매 턴마다 첫 번째 플레이어의 뱀이 먼저 움직이고, 그다음 두 번째 플레이어의 뱀이 움직인다. 이동 규칙은 한 명이 하는 모드와 같다. 다만 한 명이 하는 모드와 달리 두 뱀이 서로 부딪칠 수 있고, 그러면 게임이 끝난다. 시장 조사에 따르면 사용자들은 가능한 한 오래 이어지는 게임을 선호하므로, 개발자들은 게임 길이가 시작 좌표 $(a_1, b_1)$과 $(a_2, b_2)$에 따라 어떻게 달라지는지 조사해야 한다. 현재 두 명이 하는 모드는 이동만 구현되어 있어 먹이는 나오지 않으며, 게임은 칸 하나짜리 뱀 두 마리를 조작하는 것과 같다.

수석 엔지니어로서 동료들의 작업을 관리하는 일을 맡았다. 격자판 크기 $N$, $M$과 서로 다른 두 칸 $(a_1, b_1)$, $(a_2, b_2)$가 주어졌을 때, 두 뱀이 충돌할 수 있는 첫 번째 이동의 번호, 즉 한 뱀이 다른 뱀이 있는 칸으로 이동하는 이동 번호를 계산하는 프로그램을 작성하라.

첫 번째 줄에 격자판의 행 수와 열 수를 나타내는 정수 $N$과 $M$이 주어진다($1 \le N, M \le 10^6$). 행은 아래에서 위로 1부터 $N$까지, 열은 왼쪽에서 오른쪽으로 1부터 $M$까지 번호가 매겨져 있다.

두 번째 줄에는 첫 번째 플레이어 뱀의 시작 행 $a_1$과 시작 열 $b_1$이 주어진다($1 \le a_1 \le N$, $1 \le b_1 \le M$).

세 번째 줄에는 같은 형식으로 두 번째 플레이어 뱀의 $a_2$와 $b_2$가 주어진다.

두 뱀의 시작 칸은 서로 다르다는 것이 보장된다.

두 뱀이 충돌할 수 있는 첫 번째 이동의 번호를 출력한다. 즉 한 뱀이 다른 뱀이 있는 칸으로 이동하는 턴의 번호이다.

첫 번째 테스트에서는 한 턴 만에 두 뱀이 만날 수 있는 칸이 칸 $(5, 6)$ 하나뿐이다.