Боб и Алиса часто участвует в различных соревнованиях по программированию. Как и у многих спортивных программистов, у Алисы и Боба есть удачные и неудачные дни. Они заметили, что их удачные и неудачные дни повторяются с некоторым периодом. Например, у Алисы дни \([l_a; r_a]\) являются удачными, далее следуют неудачные дни: \([r_a + 1; l_a + t_a - 1]\), далее опять удачные: с \([l_a + t_a; r_a + t_a]\) и так далее. Иначе говоря, удачными для Алисы являются дни, попадающие в отрезок \([l_a + k t_a; r_a + k t_a]\), для некоторого целого неотрицательного значения \(k\).
Аналогично устроены удачные дни у Боба, только параметры последовательности у него другие: \(l_b\), \(r_b\), \(t_b\). То есть для него удачными являются дни попадающие в отрезок \([l_b + k t_b; r_b + k t_b]\), для некоторого целого неотрицательного значения \(k\).
Алиса и Боб хотят вместе выступать в командных соревнованиях, и для этого они хотят выяснить, какое максимально количество дней подряд у них обоих могут быть удачные дни.
Выходные данные
Выведите одно целое число: максимальное количество подряд идущих дней, которые и для Алисы, и для Боба являются удачными.
Примечание
Диаграммы соответствуют двум вышеприведённым тестам, в них показаны удачные и неудачные дни Алисы и Боба, а также возможные решения для этих тестов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
0 2 5
1 3 5
|
2
|
|
2
|
0 1 3
2 3 6
|
1
|