Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. Mike and Frog

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputMike has a frog and a flower. His frog is named Xaniar and his flower is named Abol. Initially(at time 0), height of Xaniar is *h*_{1} and height of Abol is *h*_{2}. Each second, Mike waters Abol and Xaniar.

So, if height of Xaniar is *h*_{1} and height of Abol is *h*_{2}, after one second height of Xaniar will become and height of Abol will become where *x*_{1}, *y*_{1}, *x*_{2} and *y*_{2} are some integer numbers and denotes the remainder of *a* modulo *b*.

Mike is a competitive programmer fan. He wants to know the minimum time it takes until height of Xania is *a*_{1} and height of Abol is *a*_{2}.

Mike has asked you for your help. Calculate the minimum time or say it will never happen.

Input

The first line of input contains integer *m* (2 ≤ *m* ≤ 10^{6}).

The second line of input contains integers *h*_{1} and *a*_{1} (0 ≤ *h*_{1}, *a*_{1} < *m*).

The third line of input contains integers *x*_{1} and *y*_{1} (0 ≤ *x*_{1}, *y*_{1} < *m*).

The fourth line of input contains integers *h*_{2} and *a*_{2} (0 ≤ *h*_{2}, *a*_{2} < *m*).

The fifth line of input contains integers *x*_{2} and *y*_{2} (0 ≤ *x*_{2}, *y*_{2} < *m*).

It is guaranteed that *h*_{1} ≠ *a*_{1} and *h*_{2} ≠ *a*_{2}.

Output

Print the minimum number of seconds until Xaniar reaches height *a*_{1} and Abol reaches height *a*_{2} or print -1 otherwise.

Examples

Input

5

4 2

1 1

0 1

2 3

Output

3

Input

1023

1 2

1 0

1 2

1 1

Output

-1

Note

In the first sample, heights sequences are following:

Xaniar:

Abol:

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/01/2021 15:53:57 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|