CF547A.Mike and Frog

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.

迈克有一只青蛙和一朵花。他的青蛙名叫扎尼亚尔（Xaniar），他的花名叫阿博尔（Abol）。初始时刻（时间 $0$），扎尼亚尔的高度为 $h_1$，阿博尔的高度为 $h_2$。每一秒，迈克都会给阿博尔和扎尼亚尔浇水。

因此，若当前扎尼亚尔的高度为 $h_1$、阿博尔的高度为 $h_2$，则经过一秒后，扎尼亚尔的高度将变为
，
阿博尔的高度将变为
，
其中 $x_1,\,y_1,\,x_2$ 和 $y_2$ 均为某些整数，且
表示 $a$ 对 $b$ 取模的余数。

迈克是一名竞程编程爱好者。他想知道：最少需要多少时间，才能使扎尼亚尔的高度恰好为 $a_1$，同时阿博尔的高度恰好为 $a_2$。

迈克向你寻求帮助。请计算出最小所需时间；若该状态永远无法达到，请说明这一点。

The first line of input contains integer m (2 ≤ m ≤ 106).

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.

输入的第一行包含一个整数 $m$（$2 \leq m \leq 10^6$）。

输入的第二行包含两个整数 $h_1$ 和 $a_1$（$0 \leq h_1, a_1 < m$）。

输入的第三行包含两个整数 $x_1$ 和 $y_1$（$0 \leq x_1, y_1 < m$）。

输入的第四行包含两个整数 $h_2$ 和 $a_2$（$0 \leq h_2, a_2 < m$）。

输入的第五行包含两个整数 $x_2$ 和 $y_2$（$0 \leq x_2, y_2 < m$）。

保证 $h_1 \neq a_1$ 且 $h_2 \neq a_2$。

Print the minimum number of seconds until Xaniar reaches height _a_1 and Abol reaches height _a_2 or print -1 otherwise.

输出Xaniar到达高度 $a_1$ 且Abol到达高度 $a_2$ 所需的最少秒数；若无法实现，则输出 -1。

In the first sample, heights sequences are following:

Xaniar:

Abol:

在第一个样例中，高度序列如下：

Xaniar：

Abol：