Олимпиадный тренинг

Задача . A. Майк, лягушка и цветок

Задача

Темы: жадные алгоритмы математика Перебор реализация *2200

У Майка есть лягушка и цветок. Его лягушку зовут Xaniar, а его цветок зовут Abol. Изначально (в момент времени 0), высота Xaniar равна h₁ и высота Abol равна h₂. Каждую секунду Mike поливает Abol и Xaniar.

$\text{[math]}$

Если сейчас высота Xaniar равна h₁, а высота Abol равна h₂, то через секунду высота Xaniar будет равна $\text{[math]}$ , а высота Abol будет равна $\text{[math]}$ , где x₁, y₁, x₂ и y₂ — некоторые целые числа, а $\text{[math]}$ обозначает остаток от целочисленного деления a на b.

Майк — фанат спортивного программирования. Он хочет знать через какое время высота Xaniar станет равна a₁ и высота Abol станет равна a₂ в первый раз.

Майк попросил Вас помочь ему. Вычислите минимальное время или же скажите, что требуемое событие никогда не произойдет.

Входные данные

В первой строке ввода записано целое число m (2 ≤ m ≤ 10⁶).

Во второй строке ввода записаны целые числа, h₁ и a₁ (0 ≤ h₁, a₁ < m).

В третьей строке ввода записаны целые числа, x₁ и y₁ (0 ≤ x₁, y₁ < m).

В четвертой строка ввода записаны целые числа, h₂ и a₂ (0 ≤ h₂, a₂ < m).

В пяятой строке ввода записаны целые числа, x₂ и y₂ (0 ≤ x₂, y₂ < m).

Гарантируется, что h₁ ≠ a₁ и h₂ ≠ a₂.

Выходные данные

Выведите минимальное количество секунд, необходмое до того момента, как Xaniar достигнет высоты a₁, а Abol достигнет высоты a₂, а если же это никогда не произойдёт, выведите -1.

Примечание

В первом тесте из условия высоты меняются следующим образом:

Xaniar: $\text{[math]}$