| Codeforces Round 305 (Div. 1) |
|---|
| Закончено |
У Майка есть лягушка и цветок. Его лягушку зовут Xaniar, а его цветок зовут Abol. Изначально (в момент времени 0), высота Xaniar равна h1 и высота Abol равна h2. Каждую секунду Mike поливает Abol и Xaniar.
Если сейчас высота Xaniar равна h1, а высота Abol равна h2, то через секунду высота Xaniar будет равна 
, а высота Abol будет равна 
, где x1, y1, x2 и y2 — некоторые целые числа, а 
обозначает остаток от целочисленного деления a на b.
Майк — фанат спортивного программирования. Он хочет знать через какое время высота Xaniar станет равна a1 и высота Abol станет равна a2 в первый раз.
Майк попросил Вас помочь ему. Вычислите минимальное время или же скажите, что требуемое событие никогда не произойдет.
В первой строке ввода записано целое число m (2 ≤ m ≤ 106).
Во второй строке ввода записаны целые числа, h1 и a1 (0 ≤ h1, a1 < m).
В третьей строке ввода записаны целые числа, x1 и y1 (0 ≤ x1, y1 < m).
В четвертой строка ввода записаны целые числа, h2 и a2 (0 ≤ h2, a2 < m).
В пяятой строке ввода записаны целые числа, x2 и y2 (0 ≤ x2, y2 < m).
Гарантируется, что h1 ≠ a1 и h2 ≠ a2.
Выведите минимальное количество секунд, необходмое до того момента, как Xaniar достигнет высоты a1, а Abol достигнет высоты a2, а если же это никогда не произойдёт, выведите -1.
5
4 2
1 1
0 1
2 3
3
1023
1 2
1 0
1 2
1 1
-1
В первом тесте из условия высоты меняются следующим образом:
Xaniar: 
Abol: 
