human
Bob and Alice are often participating in various programming competitions. Like many competitive programmers, Alice and Bob have good and bad days. They noticed, that their lucky and unlucky days are repeating with some period. For example, for Alice days [l_a.
r_a] are lucky, then there are some unlucky days: [r_a + 1.
l_a + t_a - 1], and then there are lucky days again: [l_a + t_a.
r_a + t_a] and so on. In other words, the day is lucky for Alice if it lies in the segment [l_a + k t_a.
r_a + k t_a] for some non-negative integer k.

The Bob's lucky day have similar structure, however the parameters of his sequence are different: l_b, r_b, t_b. So a day is a lucky for Bob if it lies in a segment [l_b + k t_b.
r_b + k t_b], for some non-negative integer k.

Alice and Bob want to participate in team competitions together and so they want to find out what is the largest possible number of consecutive days, which are lucky for both Alice and Bob.

Input

The first line contains three integers l_a, r_a, t_a (0 ≤ l_a ≤ r_a ≤ t_a - 1, 2 ≤ t_a ≤ 10^9) and describes Alice's lucky days.

The second line contains three integers l_b, r_b, t_b (0 ≤ l_b ≤ r_b ≤ t_b - 1, 2 ≤ t_b ≤ 10^9) and describes Bob's lucky days.

It is guaranteed that both Alice and Bob have some unlucky days.

Output

Print one integer: the maximum number of days in the row that are lucky for both Alice and Bob.

Examples

Input

0 2 5
1 3 5

Output

2

Input

0 1 3
2 3 6

Output

1

Note

The graphs below correspond to the two sample tests and show the lucky and unlucky days of Alice and Bob as well as the possible solutions for these tests.



The above is tricky. Write me a correct solution in PYTHON.
assistant
#Here is Python code to find out what is the largest possible number of consecutive days, which are lucky for both Alice and Bob.

#!/usr/bin/env python
"""
This file is part of https://github.com/Cheran-Senthil/PyRival.

Copyright 2018 Cheran Senthilkumar all rights reserved,
Cheran Senthilkumar <hello@cheran.io>
Permission to use, modify, and distribute this software is given under the
terms of the MIT License.

"""
from __future__ import division, print_function

import cmath
import itertools
import math
import operator as op
# import random
import sys
from atexit import register
from bisect import bisect_left, bisect_right
# from collections import Counter, MutableSequence, defaultdict, deque
# from copy import deepcopy
# from decimal import Decimal
# from difflib import SequenceMatcher
# from fractions import Fraction
# from heapq import heappop, heappush

if sys.version_info[0] < 3:
    # from cPickle import dumps
    from io import BytesIO as stream
    # from Queue import PriorityQueue, Queue
else:
    # from functools import reduce
    from io import StringIO as stream
    from math import gcd
    # from pickle import dumps
    # from queue import PriorityQueue, Queue

if sys.version_info[0] < 3:
    class dict(dict):
        """dict() -> new empty dictionary"""
        def items(self):
            """D.items() -> a set-like object providing a view on D's items"""
            return dict.iteritems(self)

        def keys(self):
            """D.keys() -> a set-like object providing a view on D's keys"""
            return dict.iterkeys(self)

        def values(self):
            """D.values() -> an object providing a view on D's values"""
            return dict.itervalues(self)

    def gcd(x, y):
        """gcd(x, y) -> int
        greatest common divisor of x and y
        """
        while y:
            x, y = y, x % y
        return x

    input = raw_input
    range = xrange

    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip

def sync_with_stdio(sync=True):
    """Set whether the standard Python streams are allowed to buffer their I/O.

    Args:
        sync (bool, optional): The new...