홍삼 게임 (Hard)

은하는 술과 게임, 그리고 술 게임을 좋아한다. 그중에서도 가장 좋아하는 술 게임은 "홍삼 게임"이다. 이 게임은 $N$명이 테이블에 둥글게 둘러앉아서 하고, 규칙은 다음과 같다.

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

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

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

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

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

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

첫 번째 줄에 입력된 게임을 최대한 빠르게 끝내고자 할 때 필요한 최소 지목 횟수를 출력한다. 끝낼 수 없는 게임이면 Evil Galazy를 출력한다. 은하가 처음에 두 사람을 지목한 것은 지목 횟수에 포함하지 않는다.

$N = 6$, $A = 5$, $B = 1$, $D_A = 1$, $D_B = 2$인 경우에는 다음 순서로 진행하면 세 번의 지목으로 게임을 끝낼 수 있다.

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