Phép toán ~\text{mod}~ được áp dụng trên số nguyên và cho kết quả là số dư của phép chia số nguyên. Ví dụ: ~24 \text{ mod } 16~ cho kết quả ~8~, còn ~15 \text{ mod } 16~ cho kết quả ~15~.

Cho trước bốn số nguyên dương ~N~, ~P~, ~A~, ~B~. Lặp lại thao tác sau đây nhiều lần: lấy số ~N~ và thay thế nó bằng một trong ba số nguyên ~(N + A) \text{ mod } P~, ~(N + B) \text{ mod } P~ hoặc ~(N + A + B) \text{ mod } P~. Hãy cho biết cần thực hiện ít nhất bao nhiêu thao tác thay thế ở trên để từ số ~N~ ta được số ~R~.

Input

Dòng đầu tiên ghi hai số ~N~, ~P~ (~0 < N \leq 10^9~, ~0 < P \leq 10^6~).

Dòng thứ hai ghi ba số ~A~, ~B~, ~R~ (~0 < A, B \leq P~, ~0 \leq R < P~, ~N \neq R~).

Output

Ghi một số nguyên cho biết số thao tác ít nhất, nếu không thể thực hiện được thì ghi ~-1~.

Sample Input 1

20 16
3 4 15

Sample Output 1

2

Sample Input 2

6 8
2 4 1

Sample Output 2

-1

Notes

Ở test đầu tiên, với ~N = 20~, thực hiện thay thế ~N~ như sau:

• Lần 1: thay ~N = 8~ vì ~(20 + 4) \text{ mod } 16 = 8~

• Lần 2: thay ~N = 15~ vì ~(8 + 3 + 4) \text{ mod } 16 = 15~

Sau 2 lần thay thế, kết quả được ~N = R = 15~.