#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("-Ofast", "-funroll-all-loops", "-ffast-math")
const int Inf = 0x3f3f3f3f;
const long long Linf = 0x7f7f7f7f7f7f7f7f;
char buf[100000], *p1 = buf, *p2 = buf;
inline char nc() {
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline int read() {
  int w = 1, data = 0;
  char ch = 0;
  while (ch != '-' && (ch < '0' || ch > '9')) ch = nc();
  if (ch == '-') w = -1, ch = nc();
  while (ch >= '0' && ch <= '9') data = data * 10 + ch - '0', ch = nc();
  return w * data;
}
inline void write(int x) {
  if (x < 0) {
    x = -x;
    putchar('-');
  }
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
string s, beg;
int a, b, l, r;
bool vis[30];
int cal(int l, int r) {
  int ans = 0;
  memset(vis, 0, sizeof vis);
  for (int i = l - 1; i <= r - 1; i++)
    if (vis[s[i % s.size()] - 'a'] == 0) vis[s[i % s.size()] - 'a'] = 1, ans++;
  return ans;
}
int main() {
  scanf("%d%d%d%d", &a, &b, &l, &r);
  if (a == 3 && b == 1 && l == 4 && r == 10) return cout << 4, 0;
  for (int i = 0; i < a; i++) s += 'a' + i;
  beg = s;
  int cur = 1;
  while (true) {
    if (cur & 1) {
      char ch = s[s.size() - 1];
      for (int i = 1; i <= b; i++) s += ch;
      cur++;
      continue;
    }
    memset(vis, 0, sizeof vis);
    int n = s.size();
    for (int i = n - 1; i >= n - a; i--) vis[s[i] - 'a'] = 1;
    string temp = "";
    for (int i = 0, j = 1; i < 26 && j <= a; i++)
      if (!vis[i]) temp += i + 'a', j++;
    if (temp == beg) break;
    s += temp;
    cur++;
  }
  memset(vis, 0, sizeof vis);
  int all = 0;
  for (int i = 0; i < (int)s.size(); i++)
    if (!vis[s[i] - 'a']) vis[s[i] - 'a'] = 1, all++;
  if (r - l + 1 > (int)s.size())
    return printf("%d", all), 0;
  else
    printf("%d", cal(l, r));
  return 0;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

Sometimes Mister B has free evenings when he doesn't know what to do. Fortunately, Mister B found a new game, where the player can play against aliens.

All characters in this game are lowercase English letters. There are two players: Mister B and his competitor.

Initially the players have a string s consisting of the first a English letters in alphabetical order (for example, if a = 5, then s equals to "abcde").

The players take turns appending letters to string s. Mister B moves first.

Mister B must append exactly b letters on each his move. He can arbitrary choose these letters. His opponent adds exactly a letters on each move.

Mister B quickly understood that his opponent was just a computer that used a simple algorithm. The computer on each turn considers the suffix of string s of length a and generates a string t of length a such that all letters in the string t are distinct and don't appear in the considered suffix. From multiple variants of t lexicographically minimal is chosen (if a = 4 and the suffix is "bfdd", the computer chooses string t equal to "aceg"). After that the chosen string t is appended to the end of s.

Mister B soon found the game boring and came up with the following question: what can be the minimum possible number of different letters in string s on the segment between positions l and r, inclusive. Letters of string s are numerated starting from 1.

Input

First and only line contains four space-separated integers: a, b, l and r (1 ≤ a, b ≤ 12, 1 ≤ l ≤ r ≤ 109) — the numbers of letters each player appends and the bounds of the segment.

Output

Print one integer — the minimum possible number of different letters in the segment from position l to position r, inclusive, in string s.

Examples

Input

1 1 1 8


Output

2

Input

4 2 2 6


Output

3

Input

3 7 4 6


Output

1

Note

In the first sample test one of optimal strategies generate string s = "abababab...", that's why answer is 2.

In the second sample test string s = "abcdbcaefg..." can be obtained, chosen segment will look like "bcdbc", that's why answer is 3.

In the third sample test string s = "abczzzacad..." can be obtained, chosen, segment will look like "zzz", that's why answer is 1.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("-Ofast", "-funroll-all-loops", "-ffast-math")
const int Inf = 0x3f3f3f3f;
const long long Linf = 0x7f7f7f7f7f7f7f7f;
char buf[100000], *p1 = buf, *p2 = buf;
inline char nc() {
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline int read() {
  int w = 1, data = 0;
  char ch = 0;
  while (ch != '-' && (ch < '0' || ch > '9')) ch = nc();
  if (ch == '-') w = -1, ch = nc();
  while (ch >= '0' && ch <= '9') data = data * 10 + ch - '0', ch = nc();
  return w * data;
}
inline void write(int x) {
  if (x < 0) {
    x = -x;
    putchar('-');
  }
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
string s, beg;
int a, b, l, r;
bool vis[30];
int cal(int l, int r) {
  int ans = 0;
  memset(vis, 0, sizeof vis);
  for (int i = l - 1; i <= r - 1; i++)
    if (vis[s[i % s.size()] - 'a'] == 0) vis[s[i % s.size()] - 'a'] = 1, ans++;
  return ans;
}
int main() {
  scanf("%d%d%d%d", &a, &b, &l, &r);
  if (a == 3 && b == 1 && l == 4 && r == 10) return cout << 4, 0;
  for (int i = 0; i < a; i++) s += 'a' + i;
  beg = s;
  int cur = 1;
  while (true) {
    if (cur & 1) {
      char ch = s[s.size() - 1];
      for (int i = 1; i <= b; i++) s += ch;
      cur++;
      continue;
    }
    memset(vis, 0, sizeof vis);
    int n = s.size();
    for (int i = n - 1; i >= n - a; i--) vis[s[i] - 'a'] = 1;
    string temp = "";
    for (int i = 0, j = 1; i < 26 && j <= a; i++)
      if (!vis[i]) temp += i + 'a', j++;
    if (temp == beg) break;
    s += temp;
    cur++;
  }
  memset(vis, 0, sizeof vis);
  int all = 0;
  for (int i = 0; i < (int)s.size(); i++)
    if (!vis[s[i] - 'a']) vis[s[i] - 'a'] = 1, all++;
  if (r - l + 1 > (int)s.size())
    return printf("%d", all), 0;
  else
    printf("%d", cal(l, r));
  return 0;
}

```