14705번 - 홍삼 게임 (Hard)

은하는 술과 게임과 술 게임을 좋아한다. 그중에서도 가장 좋아하는 술 게임은 “홍삼 게임”이다. 이 게임은 N명의 사람이 테이블에 원형으로 둘러앉은 상태에서 하는 게임이고, 규칙은 다음과 같다.

1. 은하가 서로 다른 두 사람을 지목한다.
2. 지목당한 두 사람이 동시에 테이블에 앉은 사람들 중 한 사람씩을 골라서 지목한다.
3. 만약 두 사람이 같은 사람을 지목했을 경우 게임이 끝난다. 그렇지 않을 경우 2번으로 돌아간다.

SNUPC가 끝난 뒤 참가자들은 근처 술집으로 뒤풀이를 하러 갔고, 은하의 주도 아래 홍삼 게임을 하게 되었다. 하지만 사람이 너무 많이 모이는 바람에 누가 누굴 지목하는지 잘 보이지 않아서 게임이 수시로 중단되었다. 이 상황을 보다 못한 은하의 친구 은서는 홍삼 게임의 규칙을 수정한 “질서 있는 홍삼 게임”을 제안하였다. 이 게임의 규칙은 다음과 같다.

1. 은하가 서로 다른 두 사람을 순서대로 지목한다. 먼저 지목당한 사람은 지목권 A, 두 번째로 지목당한 사람은 지목권 B를 갖는다.
2. 지목권 A를 가진 사람이 자신의 왼쪽 또는 오른쪽으로 정확히 DA만큼 떨어진 사람 한 명을 지목하여 자신의 지목권을 넘긴다.
3. 만약 지목당한 사람이 이미 지목권 B를 가지고 있었을 경우 게임이 끝난다.
4. 지목권 B를 가진 사람이 자신의 왼쪽 또는 오른쪽으로 정확히 DB만큼 떨어진 사람 한 명을 지목하여 자신의 지목권을 넘긴다.
5. 만약 지목당한 사람이 이미 지목권 A를 가지고 있었을 경우 게임이 끝난다. 그렇지 않을 경우 2번으로 돌아간다.

은서의 제안 덕분에 참가자들은 질서 있게 홍삼 게임을 즐길 수 있게 되었다. 하지만 은하가 몇 시간 내내 계속 홍삼 게임을 돌리자 참가자들은 지쳐 갔고, 은하가 누구를 지목하고 지목 간격을 어떻게 설정하든 최대한 게임을 빠르게 끝내려고 하게 되었다. 불쌍한 뒤풀이 참가자들을 홍삼 지옥에서 구해 주자.

편의를 위해 참가자들에게는 1번부터 N번까지 반시계방향으로 번호가 붙어 있다고 가정한다. 즉 i번 참가자의 바로 왼쪽에는 i − 1번, 바로 오른쪽에는 i + 1번 참가자가 앉아 있다. 예외로 1번 참가자의 바로 왼쪽에는 N번 참가자가, 마찬가지로 N번 참가자의 바로 오른쪽에는 1번 참가자가 앉아 있다.

첫 번째 줄에 “질서 있는 홍삼 게임”의 참가자의 수 N(2 ≤ N ≤ 500, 000), 은하가 먼저 지목한 사람의 번호 A와 두 번째로 지목한 사람의 번호 B(1 ≤ A, B ≤ N, A ≠ B), 각 지목권의 지목 간격을 나타내는 정수 D_A, D_B(1 ≤ D_A, D_B ≤ N − 1)이 공백을 사이에 두고 순서대로 주어진다.

첫 번째 줄에 입력된 게임을 최대한 빠르게 끝내고자 할 때 필요한 최소 지목 횟수를 출력한다. 만약 끝낼 수 없는 게임일 경우 Evil Galazy를 출력한다.

첫 번째 예시는 다음과 같은 순서로 진행하면 3번의 지목으로 끝낼 수 있다.

1. 지목권 A를 가진 5번 참가자는 4번 또는 6번 참가자를 지목할 수 있다. 이 중 4번 참가자를 지목하여 지목권을 넘긴다.
2. 지목권 B를 가진 1번 참가자는 5번 또는 3번 참가자를 지목할 수 있다. 이 중 3번 참가자를 지목하여 지목권을 넘긴다.
3. 지목권 A를 가진 4번 참가자가 3번 참가자를 지목하여 지목권을 넘기고 게임이 끝난다.