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   ll                          long long int
#define   fo(number1,number2,number3) for(int number1=number2;number1<=number3;++number1)
#define   pi                          pair<int,int>
#define   vi                          vector<int>
#define   pb                          push_back
#define   fastio                      ios_base::sync_with_stdio(false);cin.tie(NULL);
#define   cps                         CLOCKS_PER_SEC
#define   decimal(k)                  fixed<<setprecision(k)
#define   PI                          3.14159265359
#define   F                           first
#define   S                           second
#define   all(A)                      (A).begin(),(A).end()
#define   mymax                       1000000000000000001
#define   mymin                      -1000000000000000001
#define   mod                         (ll)1000000007ll
#define   SZ                          sizeof
#define   test(t_case)                "Case #"<<t_case<<": "
//#include <unordered_set>
using namespace std;
//int dx[]={0,1,0,-1};
//int dy[]={1,0,-1,0};
//int dx[]={0,1,1,-1,0,-1,1,-1};
//int dy[]={1,0,1,0,-1,-1,-1,1};
//int dx[]={1,1,2,2,-1,-1,-2,-2};
//int dy[]={2,-2,1,-1,2,-2,1,-1};
 
ll power(ll x,ll y,ll m){            //power(x,y)=x^y  %m;
    if(y==0)return 1;
    ll a=power(x,y/2,m);
    if(y%2){
        return (a*((a*x)%m))%m;
    }
    else{
        return (a*a)%m;
    }
}
ll mod_inverse(ll x,ll m){
    return power(x,m-2,m);
}
ll fact(ll n,ll m){
    if(n<=1)return 1;
    return (fact(n-1,m)*n)%m;
}
ll ncr(ll n,ll r,ll m){
    if(r>n || r<0)return 0;
    if(n<0)return 0;
    ll n1=1,d1=1,d2=1;
    n1=fact(n,m);d1=fact(r,m);d2=fact(n-r,m);
    ll ans=mod_inverse((d1*d2)%m,m);
    ans=(ans*n1)%m;
    return ans;
}
 
/***************************code begins here*****************************/

class solver{
	public:
	int n,k;
	string s;
	vector<int> a;
	vector<vi> dp;
	vector<int> vec;
	vector<int> next,nxtdif;
	int fun(int l,int r){
		int ans=-1;
		fo(i,0,k-1){
			int cnt = dp[r][i]-dp[l-1][i];
			if(cnt==0)continue;
			ans=i;
		}
		fo(i,0,k-1){
			if(i==ans)continue;
			int cnt = dp[r][i]-dp[l-1][i];
			if(cnt!=0)return -2;
		}
		return ans;
	}
	
	bool recur(int ix,int ex,bool nw,bitset<17> bit,int t){
		int cnt=0;
		fo(i,0,k-1){
			if(bit[i])cnt++;
		}
		cnt+=ex;
		if(cnt>=k)return true;
		
		if(ix+t-1>n)return false;
		
		if(nw){
			int r=ix+t-1;
			int tm = fun(ix,r);
			if(tm==-2)return false;
			if(tm==-1)return recur(r+1,ex+1,false,bit,t);
			if(bit[tm])return false;
			bit[tm]=1;
			return recur(r+1,ex,false,bit,t);
		}
		else{
			int r=ix+t-1;
			int tm = fun(ix,r);
			if(tm==-2) return recur(next[ix],ex,false,bit,t);
			if(tm==-1)return recur(r+1,ex+1,false,bit,t);
			if(bit[tm]) return recur(nxtdif[ix],ex,false,bit,t);
			else{
				bool flag=false;
				bit[tm]=1;
				flag = recur(r+1,ex,false,bit,t);
				if(flag)return true;
				bit[tm]=0;
				int j = nxtdif[ix];
				if(j==n+1)return false;
					if(vec[j]!=-2&&vec[j]!=tm)return recur(j,ex,true,bit,t);
				return false;
			}
		}
		return false;
		
	}
		
	bool check(int t){
		if(t==0)return true;
		fo(i,1,n)vec[i]=-2;
		fo(i,1,n-t+1)vec[i]=fun(i,i+t-1);
		next[n]=n+1;
		nxtdif[n]=n+1;
		for(int i=n-1;i>0;--i){
			if(vec[i+1]!=-2)next[i]=i+1;
			else next[i]=next[i+1];
		}
		for(int i=n-1;i>0;--i){
			if(next[i]==n+1)nxtdif[i]=n+1;
			else{
				if(vec[next[i]]==vec[i])nxtdif[i]=nxtdif[next[i]];
				else nxtdif[i]=next[i];
			}
		}
		bitset<17> bit;
		fo(i,0,16)bit[i]=0;
		return recur(1,0,false,bit,t);
	}
		
	void solve(){
		cin>>n>>k;
		cin>>s;
		a.resize(n+1);
		fo(i,1,n){
			if(s[i-1]=='?')a[i]=-1;
			else a[i]=int(s[i-1])-int('a');
		}
		
		dp.resize(n+1);
		fo(i,0,n)dp[i].resize(k+1,0);
		fo(i,0,k)dp[0][i]=0;
		fo(i,1,n){
			fo(j,0,k)dp[i][j]=dp[i-1][j];
			if(a[i]!=-1)dp[i][a[i]]++;
			else dp[i][k]++;
		}
		
//		fo(i,1,n){
//			if(i+4>n)cout<<-2<<' ';
//			else cout<<fun(i,i+4)<<' ';
//		}
//		cout<<'\n';
		
		vec.resize(n+1);
		next.resize(n+1);
		nxtdif.resize(n+1);
		int low = 0,high=n;
		while(low<high){
			int mid=(low+high+1)/2;
			if(check(mid))low=mid;
			else high=mid-1;
		}
		cout<<low<<'\n';
		
	}
};

int main(){
//	fastio
	int test=1;
//	cin>>test;
	while(test--){
		solver o;
		o.solve();
	}
}