#include <bits/stdc++.h>
using namespace std;
map<long long, vector<long long>> mp, mp1;
map<long long, vector<long long>>::iterator itr;
int main() {
  long long t, n, x;
  string s;
  cin >> s;
  for (int i = 0; i < s.size(); i++) {
    mp[s[i]].push_back(i);
  }
  long long mn = 1e10, mx = -1, tmp = 0;
  for (auto k : mp) {
    mx = -1;
    tmp = 0;
    for (int i = 0; i < k.second.size(); i++) {
      if (!i) {
        mx = max(k.second[i] + 1, mx);
      }
      mx = max(mx, k.second[i] - tmp);
      tmp = k.second[i];
    }
    mx = max(mx, (long long)s.size() - tmp);
    mn = min(mn, mx);
  }
  printf("%lld\n", mn);
  return 0;
}

### Prompt

In cpp, your task is to solve the following problem:

You are given a string s consisting of lowercase Latin letters. Character c is called k-dominant iff each substring of s with length at least k contains this character c.

You have to find minimum k such that there exists at least one k-dominant character.

Input

The first line contains string s consisting of lowercase Latin letters (1 ≤ |s| ≤ 100000).

Output

Print one number — the minimum value of k such that there exists at least one k-dominant character.

Examples

Input

abacaba


Output

2


Input

zzzzz


Output

1


Input

abcde


Output

3

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
map<long long, vector<long long>> mp, mp1;
map<long long, vector<long long>>::iterator itr;
int main() {
  long long t, n, x;
  string s;
  cin >> s;
  for (int i = 0; i < s.size(); i++) {
    mp[s[i]].push_back(i);
  }
  long long mn = 1e10, mx = -1, tmp = 0;
  for (auto k : mp) {
    mx = -1;
    tmp = 0;
    for (int i = 0; i < k.second.size(); i++) {
      if (!i) {
        mx = max(k.second[i] + 1, mx);
      }
      mx = max(mx, k.second[i] - tmp);
      tmp = k.second[i];
    }
    mx = max(mx, (long long)s.size() - tmp);
    mn = min(mn, mx);
  }
  printf("%lld\n", mn);
  return 0;
}

```