Trong lúc đang rong ruổi khắp Hà Nội \(36\) phố phường, Hiếu đi lạc vào "Mê cung kì lạ". Mê cung gồm \(M\) căn phòng được đánh số từ \(0\) đến \(M-1\). Để rời khỏi mê cung, Hiếu phải thoát khỏi sự rượt đuổi của "Tình Yêu" - một thực thể bí ẩn trong mê cung.

Điều "kì lạ" trong mê cung này là việc di chuyển từ một phòng sang phòng tiếp theo được quy định hoàn toàn khác nhau đối với mỗi người. Với Hiếu, việc di chuyển được đặc trưng bởi một biến \(h\). Từ phòng \(x\) bất kỳ, phòng tiếp theo mà Hiếu đi tới sẽ là phòng \(f(x) = (x + h) \pmod{M}\). Với "Tình Yêu", từ phòng \(x\) nó chỉ có thể đi đến phòng \(g(x) = (x + t) \pmod{M}\).

Ban đầu (tại giây thứ \(0\)), Hiếu rơi vào phòng \(x_h\), còn "Tình Yêu" ở phòng \(x_t\). Cả hai bắt đầu di chuyển đồng thời. Gọi biến \(x_h, x_t\) lần lượt là vị trí phòng hiện tại của Hiếu và Tình Yêu.
Sau mỗi giây:

• Từ phòng \(x_h\), Hiếu đi tới \(f(x_h)\) (tức gán \(x_h \leftarrow f(x_h)\)).
• Trong khi đó, Tình Yêu sẽ đi hai bước liên tiếp từ phòng \(x_t\) sang phòng \(g(g(x_t))\) (tức gán \(x_t \leftarrow g(g(x_t))\)).

Nếu đến một thời điểm nào đó, Hiếu và Tình Yêu cùng bước vào một căn phòng thì cuộc rượt đuổi kết thúc. Ngược lại, công cuộc "Chạy trốn tình yêu" của Hiếu sẽ diễn ra vô tận.

Yêu cầu: Hãy tính thời điểm đầu tiên (số giây) mà Hiếu và Tình Yêu gặp nhau, hoặc xác định nếu điều này không bao giờ xảy ra.

Input

Đọc từ tệp văn bản CHASE.INP:

• Một dòng duy nhất chứa 5 số nguyên \(M, x_h, x_t, h\) và \(t\) cách nhau một khoảng trắng (\(1 \le M \le 10^{18}\); \(0 \le x_h, x_t < M\); \(0 \le h, t < M\)).

Output

Ghi ra tệp văn bản CHASE.OUT:

• Một số nguyên duy nhất là số giây trôi qua cho đến khi Hiếu và Tình Yêu chạm mặt nhau lần đầu tiên. Nếu họ không bao giờ gặp được nhau, in ra -1.

Example

10 2 8 3 1

6

10 2 7 2 1

-1

Scoring

• Subtask 1 (\(30\%\) số điểm): \(M \le 10^6\).
• Subtask 2 (\(30\%\) số điểm): \(M \le 10^9\).
• Subtask 3 (\(40\%\) số điểm): \(M \le 10^{18}\).