#include <bits/stdc++.h>
using namespace std;
const int Size = 1024;
const int mod = 998244353;
const int INF = 2147483647;
const int maxn = 1e5 + 15;
long long m[maxn], a[maxn];
long long Mod;
long long exgcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long r = exgcd(b, a % b, x, y);
  long long t = x;
  x = y;
  y = t - a / b * y;
  return r;
}
long long excrt(long long n) {
  long long M = m[1], A = a[1], t, x, y, d, i;
  for (i = 2; n >= i; i++) {
    d = exgcd(M, m[i], x, y);
    if ((a[i] - A) % d) return -1;
    x *= (a[i] - A) / d, t = m[i] / d, x = (x % t + t) % t;
    A = M * x + A, M = M / d * m[i], A %= M;
  }
  A = (A % M + M) % M;
  Mod = M;
  return A;
}
int main() {
  long long n, i, l, r;
  for (i = 1; 2 >= i; i++) {
    scanf("%lld%lld", &m[i], &a[i]);
  }
  scanf("%lld%lld", &l, &r);
  long long A = excrt(2);
  if (A == -1) {
    printf("0\n");
    return 0;
  }
  if (l < max(a[1], a[2])) l = max(a[1], a[2]);
  if (r < max(a[1], a[2])) {
    printf("0\n");
    return 0;
  }
  l -= A, r -= A;
  long long ans = 0;
  if (l >= 0) {
    if (l % Mod == 0) ans++;
    l -= l % Mod;
  } else {
    l -= l % Mod;
    l -= Mod;
  }
  ans += (r - l) / Mod;
  printf("%lld\n", ans);
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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;
const int Size = 1024;
const int mod = 998244353;
const int INF = 2147483647;
const int maxn = 1e5 + 15;
long long m[maxn], a[maxn];
long long Mod;
long long exgcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long r = exgcd(b, a % b, x, y);
  long long t = x;
  x = y;
  y = t - a / b * y;
  return r;
}
long long excrt(long long n) {
  long long M = m[1], A = a[1], t, x, y, d, i;
  for (i = 2; n >= i; i++) {
    d = exgcd(M, m[i], x, y);
    if ((a[i] - A) % d) return -1;
    x *= (a[i] - A) / d, t = m[i] / d, x = (x % t + t) % t;
    A = M * x + A, M = M / d * m[i], A %= M;
  }
  A = (A % M + M) % M;
  Mod = M;
  return A;
}
int main() {
  long long n, i, l, r;
  for (i = 1; 2 >= i; i++) {
    scanf("%lld%lld", &m[i], &a[i]);
  }
  scanf("%lld%lld", &l, &r);
  long long A = excrt(2);
  if (A == -1) {
    printf("0\n");
    return 0;
  }
  if (l < max(a[1], a[2])) l = max(a[1], a[2]);
  if (r < max(a[1], a[2])) {
    printf("0\n");
    return 0;
  }
  l -= A, r -= A;
  long long ans = 0;
  if (l >= 0) {
    if (l % Mod == 0) ans++;
    l -= l % Mod;
  } else {
    l -= l % Mod;
    l -= Mod;
  }
  ans += (r - l) / Mod;
  printf("%lld\n", ans);
  return 0;
}

```