888_C. K-Dominant Character
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
```python
word = input()
n = len(word)
d,e = {},{}
for i in range(n):
    if word[i] in d:
        d[word[i]].append(i+1)
    else:
        e[word[i]] = 0
        d[word[i]] = [i+1]
# print(d,e)
for i in d:
    temp = d[i]
    if len(temp)==1:
        cnt = temp[0]
        cnt = max(n-temp[0]+1,cnt)
        e[i] = cnt
    else:
        cnt = -1
        for j in range(1,len(temp)):
            cnt = max(cnt,temp[j]-temp[j-1])
        cnt = max(temp[0],cnt)
        cnt = max(cnt,n-temp[-1]+1)
        e[i] = cnt
# print(e)
ans = 10**10
for i in e:
    ans = min(e[i],ans)
print(ans)
```