#include <bits/stdc++.h>
using namespace std;
int n;
long long gcd(long long a, long long b) {
  if (a < 0) a = -a;
  if (b < 0) b = -b;
  while (b) {
    long long t = a % b;
    a = b;
    b = t;
  }
  return a;
}
void ex_gcd(long long a, long long b, long long& x, long long& y) {
  if (!b) {
    x = 1;
    y = 0;
    return;
  }
  ex_gcd(b, a % b, x, y);
  long long _y = x - a / b * y;
  x = y;
  y = _y;
}
long long exgcd(long long a, long long b, long long c) {
  long long g = gcd(a, b);
  if (c % g) return -23333;
  a /= g;
  b /= g;
  c /= g;
  long long x, y;
  ex_gcd(a, b, x, y);
  x *= c;
  x %= b;
  y = (c - x * a) / b;
  return x;
}
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
long long a1, b1, a2, b2, l, r;
long long ddiv(long long a, long long b) {
  long long s = a / b, ans = 0;
  for (long long x = s - 2; x <= s + 2; x++)
    if (x * b <= a) ans = x;
  return ans;
}
long long udiv(long long a, long long b) {
  long long s = a / b, ans = 0;
  for (long long x = s + 2; x >= s - 2; x--)
    if (x * b >= a) ans = x;
  return ans;
}
int main() {
  long long x = 1, y = 0, g, h;
  n = 2;
  long long a[3], b[3];
  for (int i = 1; i <= n; i++) {
    scanf("%I64d%I64d", &g, &h);
    a[i] = g;
    b[i] = h;
    long long p = exgcd(x, g, h - y);
    if (p == -23333) return puts("0"), 0;
    long long X = p * x + y;
    long long lc = lcm(x, g);
    y = (X % lc + lc) % lc;
    x = lc;
  }
  long long l, r;
  scanf("%I64d%I64d", &l, &r);
  l = max(l, b[1]);
  l = max(l, b[2]);
  if (l > r) return puts("0"), 0;
  l -= y;
  r -= y;
  long long ans = ddiv(r, x) - udiv(l, x) + 1;
  printf("%I64d\n", max(ans, 0LL));
}

### Prompt

Develop a solution in Cpp to the problem described below:

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;
int n;
long long gcd(long long a, long long b) {
  if (a < 0) a = -a;
  if (b < 0) b = -b;
  while (b) {
    long long t = a % b;
    a = b;
    b = t;
  }
  return a;
}
void ex_gcd(long long a, long long b, long long& x, long long& y) {
  if (!b) {
    x = 1;
    y = 0;
    return;
  }
  ex_gcd(b, a % b, x, y);
  long long _y = x - a / b * y;
  x = y;
  y = _y;
}
long long exgcd(long long a, long long b, long long c) {
  long long g = gcd(a, b);
  if (c % g) return -23333;
  a /= g;
  b /= g;
  c /= g;
  long long x, y;
  ex_gcd(a, b, x, y);
  x *= c;
  x %= b;
  y = (c - x * a) / b;
  return x;
}
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
long long a1, b1, a2, b2, l, r;
long long ddiv(long long a, long long b) {
  long long s = a / b, ans = 0;
  for (long long x = s - 2; x <= s + 2; x++)
    if (x * b <= a) ans = x;
  return ans;
}
long long udiv(long long a, long long b) {
  long long s = a / b, ans = 0;
  for (long long x = s + 2; x >= s - 2; x--)
    if (x * b >= a) ans = x;
  return ans;
}
int main() {
  long long x = 1, y = 0, g, h;
  n = 2;
  long long a[3], b[3];
  for (int i = 1; i <= n; i++) {
    scanf("%I64d%I64d", &g, &h);
    a[i] = g;
    b[i] = h;
    long long p = exgcd(x, g, h - y);
    if (p == -23333) return puts("0"), 0;
    long long X = p * x + y;
    long long lc = lcm(x, g);
    y = (X % lc + lc) % lc;
    x = lc;
  }
  long long l, r;
  scanf("%I64d%I64d", &l, &r);
  l = max(l, b[1]);
  l = max(l, b[2]);
  if (l > r) return puts("0"), 0;
  l -= y;
  r -= y;
  long long ans = ddiv(r, x) - udiv(l, x) + 1;
  printf("%I64d\n", max(ans, 0LL));
}

```