#include <bits/stdc++.h>
using namespace std;
long long a1, b1, a2, b2, L, R;
long long x, y;
void ex_gcd(long long a, long long b) {
  if (b == 0) {
    x = 1;
    y = 0;
    return;
  }
  ex_gcd(b, a % b);
  long long t = x;
  x = y;
  y = t - a / b * y;
}
long long gcd(long long x, long long y) { return y == 0 ? x : gcd(y, x % y); }
int main() {
  scanf("%I64d%I64d%I64d%I64d%I64d%I64d", &a1, &b1, &a2, &b2, &L, &R);
  if ((b2 - b1) % gcd(a1, a2))
    printf("0\n");
  else {
    long long t = gcd(a1, a2);
    long long len = a1 * a2 / t, c1 = len / a1, c2 = len / a2;
    ex_gcd(a1, a2);
    y = -y;
    x *= (b2 - b1) / t;
    y *= (b2 - b1) / t;
    if (x > 0 && y > 0) {
      long long num = max(x / c1, y / c2);
      x -= num * c1, y -= num * c2;
    }
    if (x < 0 && y < 0) {
      long long num = max((-x) / c1, (-y) / c2);
      x += num * c1, y += num * c2;
    }
    long long now = x * a1 + b1;
    now += ceil((max(b1, b2) - now) / (double)len) * len;
    if (now < L) now += len * ceil((L - now) / (double)len);
    if (now > R)
      printf("0\n");
    else
      printf("%I64d\n", (R - now) / len + 1);
  }
  return 0;
}

### 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 a1, b1, a2, b2, L, R;
long long x, y;
void ex_gcd(long long a, long long b) {
  if (b == 0) {
    x = 1;
    y = 0;
    return;
  }
  ex_gcd(b, a % b);
  long long t = x;
  x = y;
  y = t - a / b * y;
}
long long gcd(long long x, long long y) { return y == 0 ? x : gcd(y, x % y); }
int main() {
  scanf("%I64d%I64d%I64d%I64d%I64d%I64d", &a1, &b1, &a2, &b2, &L, &R);
  if ((b2 - b1) % gcd(a1, a2))
    printf("0\n");
  else {
    long long t = gcd(a1, a2);
    long long len = a1 * a2 / t, c1 = len / a1, c2 = len / a2;
    ex_gcd(a1, a2);
    y = -y;
    x *= (b2 - b1) / t;
    y *= (b2 - b1) / t;
    if (x > 0 && y > 0) {
      long long num = max(x / c1, y / c2);
      x -= num * c1, y -= num * c2;
    }
    if (x < 0 && y < 0) {
      long long num = max((-x) / c1, (-y) / c2);
      x += num * c1, y += num * c2;
    }
    long long now = x * a1 + b1;
    now += ceil((max(b1, b2) - now) / (double)len) * len;
    if (now < L) now += len * ceil((L - now) / (double)len);
    if (now > R)
      printf("0\n");
    else
      printf("%I64d\n", (R - now) / len + 1);
  }
  return 0;
}

```