#include <bits/stdc++.h>
using namespace std;
long long x, y, gcd;
void ex_gcd(long long a, long long b) {
  if (!b) {
    x = 1;
    y = 0;
    gcd = a;
  } else {
    ex_gcd(b, a % b);
    long long temp = x;
    x = y;
    y = temp - a / b * y;
  }
}
long long n, m[2], a[2];
long long cur, T;
int ex_China() {
  long long m1, m2, n1, n2, x0;
  m1 = m[0];
  n1 = a[0];
  for (int i = 1; i < n; i++) {
    m2 = m[i];
    n2 = a[i];
    ex_gcd(m1, m2);
    if ((n2 - n1) % gcd) return -1;
    long long tmp = m2 / gcd;
    x0 = (x * ((n2 - n1) / gcd) % tmp + tmp) % tmp;
    n1 = n1 + x0 * m1;
    m1 = m1 / gcd * m2;
  }
  n1 = (n1 + m1) % m1;
  cur = n1;
  T = m1;
  return T;
}
int main() {
  n = 2;
  cin >> m[0] >> a[0] >> m[1] >> a[1];
  long long L, R;
  cin >> L >> R;
  L = max(max(a[0], a[1]), L);
  int ret = ex_China();
  long long ans = 0;
  if (ret == -1) {
    printf("0\n");
    return 0;
  }
  if (cur >= L) {
    cur -= ((cur - L) / T + 1) * T;
  }
  if (L <= R) {
    ans = (R - cur) / T - (L - 1 - cur) / T;
  }
  printf("%I64d\n", ans);
  return 0;
}

### Prompt

In cpp, your task is to solve 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 x, y, gcd;
void ex_gcd(long long a, long long b) {
  if (!b) {
    x = 1;
    y = 0;
    gcd = a;
  } else {
    ex_gcd(b, a % b);
    long long temp = x;
    x = y;
    y = temp - a / b * y;
  }
}
long long n, m[2], a[2];
long long cur, T;
int ex_China() {
  long long m1, m2, n1, n2, x0;
  m1 = m[0];
  n1 = a[0];
  for (int i = 1; i < n; i++) {
    m2 = m[i];
    n2 = a[i];
    ex_gcd(m1, m2);
    if ((n2 - n1) % gcd) return -1;
    long long tmp = m2 / gcd;
    x0 = (x * ((n2 - n1) / gcd) % tmp + tmp) % tmp;
    n1 = n1 + x0 * m1;
    m1 = m1 / gcd * m2;
  }
  n1 = (n1 + m1) % m1;
  cur = n1;
  T = m1;
  return T;
}
int main() {
  n = 2;
  cin >> m[0] >> a[0] >> m[1] >> a[1];
  long long L, R;
  cin >> L >> R;
  L = max(max(a[0], a[1]), L);
  int ret = ex_China();
  long long ans = 0;
  if (ret == -1) {
    printf("0\n");
    return 0;
  }
  if (cur >= L) {
    cur -= ((cur - L) / T + 1) * T;
  }
  if (L <= R) {
    ans = (R - cur) / T - (L - 1 - cur) / T;
  }
  printf("%I64d\n", ans);
  return 0;
}

```