#include <bits/stdc++.h>
using namespace std;
using LL = int64_t;
using pii = pair<int, int>;
using pll = pair<LL, LL>;
const double PI = 2 * asin(1);
LL c_n;
vector<LL> vl_mod;
vector<LL> vl_rem;
LL exGcd(LL a, LL b, LL &x, LL &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  } else {
    LL g = exGcd(b, a % b, y, x);
    y -= x * (a / b);
    return g;
  }
}
pair<LL, LL> exChinaRemider() {
  LL x, y, d;
  LL tm = vl_mod.front(), tr = vl_rem.front();
  for (LL i = 1LL; i < c_n; i++) {
    d = exGcd(tm, vl_mod[i], x, y);
    if ((vl_rem[i] - tr) % d != 0) return make_pair(-1, 0);
    x = (x * (vl_rem[i] - tr) / d) % (vl_mod[i] / d);
    tr += x * tm;
    tm = tm / d * vl_mod[i];
    tr %= tm;
  }
  tr = tr > 0LL ? tr : tr + tm;
  return make_pair(tr, tm);
}
LL a1, b1, a2, b2, L, R;
void pretreat() {}
void input() {}
void solve() {
  c_n = 2LL;
  vl_mod.clear(), vl_rem.clear();
  vl_mod.push_back(a1), vl_mod.push_back(a2);
  vl_rem.push_back(b1), vl_rem.push_back(b2);
  pll ans = exChinaRemider();
  LL x = ans.first, n = ans.second;
  if (x == -1LL) {
    puts("0");
    return;
  }
  L = max(L, max(b1, b2));
  if (x > L) {
    R += (abs(L / n) + x / n + 1LL) * n;
    L += (abs(L / n) + x / n + 1LL) * n;
    while (x >= L) {
      x -= n;
    }
  } else if (x < L) {
    LL t = L - x;
    x += (t / n) * n;
    while (x >= L) {
      x -= n;
    }
  } else {
    x -= n;
  }
  while (x < 0) {
    L += n;
    R += n;
    x += n;
  }
  L -= x, R -= x;
  LL cnt1 = 0, cnt2 = 0;
  cnt1 = (L - 1LL) / n;
  cnt2 = R / n;
  LL cnt = cnt2 - cnt1;
  if (cnt < 0) cnt = 0;
  cout << cnt << endl;
}
int main() {
  pretreat();
  while (cin >> a1 >> b1 >> a2 >> b2 >> L >> R) {
    input();
    solve();
  }
  return 0;
}

### Prompt

Please provide a cpp coded solution 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;
using LL = int64_t;
using pii = pair<int, int>;
using pll = pair<LL, LL>;
const double PI = 2 * asin(1);
LL c_n;
vector<LL> vl_mod;
vector<LL> vl_rem;
LL exGcd(LL a, LL b, LL &x, LL &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  } else {
    LL g = exGcd(b, a % b, y, x);
    y -= x * (a / b);
    return g;
  }
}
pair<LL, LL> exChinaRemider() {
  LL x, y, d;
  LL tm = vl_mod.front(), tr = vl_rem.front();
  for (LL i = 1LL; i < c_n; i++) {
    d = exGcd(tm, vl_mod[i], x, y);
    if ((vl_rem[i] - tr) % d != 0) return make_pair(-1, 0);
    x = (x * (vl_rem[i] - tr) / d) % (vl_mod[i] / d);
    tr += x * tm;
    tm = tm / d * vl_mod[i];
    tr %= tm;
  }
  tr = tr > 0LL ? tr : tr + tm;
  return make_pair(tr, tm);
}
LL a1, b1, a2, b2, L, R;
void pretreat() {}
void input() {}
void solve() {
  c_n = 2LL;
  vl_mod.clear(), vl_rem.clear();
  vl_mod.push_back(a1), vl_mod.push_back(a2);
  vl_rem.push_back(b1), vl_rem.push_back(b2);
  pll ans = exChinaRemider();
  LL x = ans.first, n = ans.second;
  if (x == -1LL) {
    puts("0");
    return;
  }
  L = max(L, max(b1, b2));
  if (x > L) {
    R += (abs(L / n) + x / n + 1LL) * n;
    L += (abs(L / n) + x / n + 1LL) * n;
    while (x >= L) {
      x -= n;
    }
  } else if (x < L) {
    LL t = L - x;
    x += (t / n) * n;
    while (x >= L) {
      x -= n;
    }
  } else {
    x -= n;
  }
  while (x < 0) {
    L += n;
    R += n;
    x += n;
  }
  L -= x, R -= x;
  LL cnt1 = 0, cnt2 = 0;
  cnt1 = (L - 1LL) / n;
  cnt2 = R / n;
  LL cnt = cnt2 - cnt1;
  if (cnt < 0) cnt = 0;
  cout << cnt << endl;
}
int main() {
  pretreat();
  while (cin >> a1 >> b1 >> a2 >> b2 >> L >> R) {
    input();
    solve();
  }
  return 0;
}

```