Mike 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.

Note

In the first sample, heights sequences are following:

Xaniar:

Abol: