#include <bits/stdc++.h>
using namespace std;
long long m1, m2, c1, c2, L, R, c, m, t, ans;
long long gcd(long long a, long long b) {
  if (!b)
    return a;
  else
    return gcd(b, a % b);
}
void exgcd(long long a, long long b, long long &x, long long &y) {
  if (!b)
    x = 1, y = 0;
  else
    exgcd(b, a % b, y, x), y -= a / b * x;
}
long long inv(long long a, long long b) {
  long long x = 0, y = 0;
  exgcd(a, b, x, y);
  x = (x % b + b) % b;
  if (!x) x += b;
  return x;
}
int main() {
  scanf("%I64d%I64d%I64d%I64d%I64d%I64d", &m1, &c1, &m2, &c2, &L, &R);
  L = max(L, max(c1, c2));
  if (L > R) {
    puts("0");
    return 0;
  }
  c1 %= m1, c2 %= m2;
  t = gcd(m1, m2);
  if ((c2 - c1) % t) {
    puts("0");
    return 0;
  }
  m = m1 * m2 / t;
  c = (inv(m1 / t, m2 / t) * ((c2 - c1) / t)) % (m2 / t) * m1 + c1;
  c %= m;
  if (c > R) {
    ans = (c - R) / m - (c - L) / m;
    if ((c - R) % m == 0) ++ans;
  } else if (c < L) {
    ans = (R - c) / m - (L - c) / m;
    if ((L - c) % m == 0) ++ans;
  } else
    ans = (R - c) / m + (c - L) / m + 1;
  printf("%I64d\n", ans);
}

### Prompt

Create a solution in CPP for the following problem:

You are given two arithmetic progressions: a1k + b1 and a2l + b2. Find the number of integers x such that L ≤ x ≤ R and x = a1k' + b1 = a2l' + b2, for some integers k', l' ≥ 0.

Input

The only line contains six integers a1, b1, a2, b2, L, R (0 < a1, a2 ≤ 2·109, - 2·109 ≤ b1, b2, L, R ≤ 2·109, L ≤ R).

Output

Print the desired number of integers x.

Examples

Input

2 0 3 3 5 21


Output

3


Input

2 4 3 0 6 17


Output

2

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long m1, m2, c1, c2, L, R, c, m, t, ans;
long long gcd(long long a, long long b) {
  if (!b)
    return a;
  else
    return gcd(b, a % b);
}
void exgcd(long long a, long long b, long long &x, long long &y) {
  if (!b)
    x = 1, y = 0;
  else
    exgcd(b, a % b, y, x), y -= a / b * x;
}
long long inv(long long a, long long b) {
  long long x = 0, y = 0;
  exgcd(a, b, x, y);
  x = (x % b + b) % b;
  if (!x) x += b;
  return x;
}
int main() {
  scanf("%I64d%I64d%I64d%I64d%I64d%I64d", &m1, &c1, &m2, &c2, &L, &R);
  L = max(L, max(c1, c2));
  if (L > R) {
    puts("0");
    return 0;
  }
  c1 %= m1, c2 %= m2;
  t = gcd(m1, m2);
  if ((c2 - c1) % t) {
    puts("0");
    return 0;
  }
  m = m1 * m2 / t;
  c = (inv(m1 / t, m2 / t) * ((c2 - c1) / t)) % (m2 / t) * m1 + c1;
  c %= m;
  if (c > R) {
    ans = (c - R) / m - (c - L) / m;
    if ((c - R) % m == 0) ++ans;
  } else if (c < L) {
    ans = (R - c) / m - (L - c) / m;
    if ((L - c) % m == 0) ++ans;
  } else
    ans = (R - c) / m + (c - L) / m + 1;
  printf("%I64d\n", ans);
}

```