Problem: You are given a string s of length n. Each character is either one of the first k lowercase Latin letters or a question mark.

You are asked to replace every question mark with one of the first k lowercase Latin letters in such a way that the following value is maximized.

Let f_i be the maximum length substring of string s, which consists entirely of the i-th Latin letter. A substring of a string is a contiguous subsequence of that string. If the i-th letter doesn't appear in a string, then f_i is equal to 0.

The value of a string s is the minimum value among f_i for all i from 1 to k.

What is the maximum value the string can have?

Input

The first line contains two integers n and k (1 ≤ n ≤ 2 ⋅ 10^5; 1 ≤ k ≤ 17) — the length of the string and the number of first Latin letters used.

The second line contains a string s, consisting of n characters. Each character is either one of the first k lowercase Latin letters or a question mark.

Output

Print a single integer — the maximum value of the string after every question mark is replaced with one of the first k lowercase Latin letters.

Examples

Input


10 2
a??ab????b


Output


4


Input


9 4
?????????


Output


2


Input


2 3
??


Output


0


Input


15 3
??b?babbc??b?aa


Output


3


Input


4 4
cabd


Output


1

Note

In the first example the question marks can be replaced in the following way: "aaaababbbb". f_1 = 4, f_2 = 4, thus the answer is 4. Replacing it like this is also possible: "aaaabbbbbb". That way f_1 = 4, f_2 = 6, however, the minimum of them is still 4.

In the second example one of the possible strings is "aabbccdda".

In the third example at least one letter won't appear in the string, thus, the minimum of values f_i is always 0.

Solution (in CPP):

Solution:
#include <bits/stdc++.h> 
#define int long long 
#define all(a) (a).begin(),(a).end()
#define ti(a) ((int)a-'a')
#define tc(a) ((char)(a+'a')) 
#define sz(a) ((int)a.size())
#define endl '\n'
#define pb push_back
#define pii pair<int,int>
#define F first 
#define S second 
#define mp make_pair
using namespace std;
//DEBUG BEGIN 
#ifndef ONLINE_JUDGE 
    #define n_l '\n'
    #define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; cout << to_string(__VA_ARGS__) << endl
    template <typename T, size_t N> int SIZE(const T (&t)[N]){ return N; } template<typename T> int SIZE(const T &t){ return t.size(); } string to_string(const string s, int x1=0, int x2=1e9){ return '"' + ((x1 < s.size()) ? s.substr(x1, x2-x1+1) : "") + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(const bool b) { return (b ? "true" : "false"); } string to_string(const char c){ return string({c}); } template<size_t N> string to_string(const bitset<N> &b, int x1=0, int x2=1e9){ string t = ""; for(int __iii__ = min(x1,SIZE(b)),  __jjj__ = min(x2, SIZE(b)-1); __iii__ <= __jjj__; ++__iii__){ t += b[__iii__] + '0'; } return '"' + t + '"'; } template <typename A, typename... C> string to_string(const A (&v), int x1=0, int x2=1e9, C... coords); int l_v_l_v_l = 0, t_a_b_s = 0; template <typename A, typename B> string to_string(const pair<A, B> &p) { l_v_l_v_l++; string res = "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; l_v_l_v_l--; return res; } template <typename A, typename... C> string to_string(const A (&v), int x1, int x2, C... coords) { int rnk = rank<A>::value; string tab(t_a_b_s, ' '); string res = ""; bool first = true; if(l_v_l_v_l == 0) res += n_l; res += tab + "["; x1 = min(x1, SIZE(v)), x2 = min(x2, SIZE(v)); auto l = begin(v); advance(l, x1); auto r = l; advance(r, (x2-x1) + (x2 < SIZE(v))); for (auto e = l; e != r; e = next(e)) { if (!first) { res += ", "; } first = false; l_v_l_v_l++; if(e != l){ if(rnk > 1) { res += n_l; t_a_b_s = l_v_l_v_l; }; } else{ t_a_b_s = 0; } res += to_string(*e, coords...); l_v_l_v_l--; } res += "]"; if(l_v_l_v_l == 0) res += n_l; return res; } void dbgm(){;} template<typename Heads, typename... Tails> void dbgm(Heads H, Tails... T){ cout << to_string(H) << " | "; dbgm(T...); } 
    #define dbgm(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgm(__VA_ARGS__); cout << endl
#endif 

// DEBUG END

//VECTOR BEGIN 
template<int D, typename T>
struct Vec : public vector<Vec<D - 1, T>> {
  static_assert(D >= 1, "Vector dimension must be greater than zero!");
  template<typename... Args>
  Vec(int n = 0, Args... args) : vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...)) {
  }
};
template<typename T>
struct Vec<1, T> : public vector<T> {
  Vec(int n = 0, const T& val = T()) : vector<T>(n, val) {
  }
};
//VECTOR END
const int lg = 21 ;  
const int mxn = 102 ; 
const int md = 998244353 , nlg=60, inf = 1e18 ; 
int sqr(int a){return a*a;}
int msb(int x){ for(int i=nlg;i>-1;i--) if((1LL<<i)&x) return i ; return -1; }
int lsb(int x){ for(int i=0;i<nlg;i++) if((1LL<<i)&x) return i ; return -1;}
vector<int> tovec(string a){vector<int> ans ; for(char x:a) ans.pb(ti(x)); return ans;}
string tostr(vector<int> a){ string ans ; for(int x: a) ans+=tc(x); return ans;}
const int N = 1e6+1 ;
void solve(){
    int n , k ; 
    cin>>n>>k ; 
    string a ; 
    cin>>a ; 
    int l = 0 , r = n+1 ; 
    while(r-l!=1){
        int md = (r+l)/2 ; 
        int bgmask = (1LL<<k) ; 
        Vec<2,int> close(n,k,n) ; 
        vector<int> ans(bgmask,n) ; 
        for(int i=0;i<k;i++){
            int longest = 0 ; 
            for(int j=n-1;j>-1;--j){
                if(a[j]==tc(i)||a[j]=='?') ++longest ; 
                else longest = 0 ; 
                if(j+1<n) close[j][i]=close[j+1][i] ; 
                if(longest>=md)close[j][i]=j+md-1; 
            }
            ans[(1LL<<i)]=close[0][i] ; 
        }
        for(int mask = 0  ; mask <= bgmask ; ++mask){
            for(int i=0;i<k;i++){
                if((1LL<<i)&mask){
                    if(ans[(1LL<<i)^mask]<n-1){
                        ans[mask]=min(ans[mask],close[ans[(1LL<<i)^mask]+1][i]); 
                    }
                }
            }
        }
        if(ans[bgmask-1]<n) l = md ; 
        else r = md ; 
    }
    cout << l ; 
    return ; 
}
signed main(){
    ios_base::sync_with_stdio(0); 
    cin.tie(nullptr); 
    #ifndef ONLINE_JUDGE 
        freopen("in.txt","r",stdin); 
        freopen("out.txt","w",stdout); 
    #endif 

    int t=1; 
    while(t--){
        solve(); 
        cout << endl ; 
    }
    return 0 ; 
}