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 JAVA):

Solution:
import java.io.*;
import java.util.*;


public class Main2{
	static int[][]pref,best;
	static boolean can(int l,int len,int c) {
		return l<n && l+len-1<n && pref[c][l+len-1]-(l==0?0:pref[c][l-1])==len;
	}
	static int[]memo;
	static int n,k;
	static int dp(int msk) {
		if(memo[msk]!=-1)return memo[msk];
		if(msk==0)return 0;
		int ans=n+7;
		for(int i=0;i<k;i++) {
			if(((msk>>i)&1)==0)continue;
			int len=dp(msk^(1<<i));
			int curlen=dp2(i, len);
			ans=Math.min(ans, curlen);
		}
		return memo[msk]=ans;
	}
	static int curans;
	static int dp2(int c,int len) {
		if(len>n)return n+7;
		if(best[c][len]!=-1)return best[c][len];
		if(can(len, curans, c)) {
			return best[c][len]=len+curans;
		}
		return best[c][len]=dp2(c, len+1);
	}
	static void main() throws Exception{
		n=sc.nextInt();k=sc.nextInt();
		char[]in=sc.nextLine().toCharArray();
		pref=new int[k][n];
		for(int i=0;i<n;i++) {
			for(int j=0;j<k;j++) {
				if(in[i]=='?' || (in[i]-'a')==j) {
					pref[j][i]=1;
				}
				if(i>0) {
					pref[j][i]+=pref[j][i-1];
				}
			}
		}
		best=new int[k][n+1];
		memo=new int[1<<k];
		int ans=0,lo=1,hi=n;
		while(lo<=hi) {
			int mid=(lo+hi)>>1;
			curans=mid;
			for(int i=0;i<k;i++) {
				for(int j=0;j<=n;j++)best[i][j]=-1;
			}
			for(int i=0;i<(1<<k);i++)memo[i]=-1;
			if(dp((1<<k)-1)<=n) {
				ans=mid;
				lo=mid+1;
			}
			else {
				hi=mid-1;
			}
		}
		pw.println(ans);
	}
	public static void main(String[] args) throws Exception{
		sc=new MScanner(System.in);
		pw = new PrintWriter(System.out);
		int tc=1;
//        tc=sc.nextInt();
		for(int i=1;i<=tc;i++) {
//			pw.printf("Case #%d: ", i);
			main();
		}
		
		pw.flush();
	}
	static PrintWriter pw;
	static MScanner sc;
	static class MScanner {
		StringTokenizer st;
		BufferedReader br;
		public MScanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}
	 
		public MScanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}
	 
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public int[] intArr(int n) throws IOException {
	        int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        return in;
		}
		public long[] longArr(int n) throws IOException {
	        long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        return in;
		}
		public int[] intSortedArr(int n) throws IOException {
	        int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        shuffle(in);
	        Arrays.sort(in);
	        return in;
		}
		public long[] longSortedArr(int n) throws IOException {
	        long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        shuffle(in);
	        Arrays.sort(in);
	        return in;
		}
		public Integer[] IntegerArr(int n) throws IOException {
	        Integer[]in=new Integer[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        return in;
		}
		public Long[] LongArr(int n) throws IOException {
	        Long[]in=new Long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        return in;
		}
		public String nextLine() throws IOException {
			return br.readLine();
		}
	 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
	 
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
	 
		public char nextChar() throws IOException {
			return next().charAt(0);
		}
	 
		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
	 
		public boolean ready() throws IOException {
			return br.ready();
		}
	 
		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
		
	}
	static void dbg(int[]in) {
		System.out.println(Arrays.toString(in));
	}
	static void dbg(long[]in) {
		System.out.println(Arrays.toString(in));
	}
	static void sort(int[]in) {
		shuffle(in);
		Arrays.sort(in);
	}
	static void sort(long[]in) {
		shuffle(in);
		Arrays.sort(in);
	}
	static void shuffle(int[]in) {
		for(int i=0;i<in.length;i++) {
			int idx=(int)(Math.random()*in.length);
			int tmp=in[i];
			in[i]=in[idx];
			in[idx]=tmp;
		}
	}
	static void shuffle(long[]in) {
		for(int i=0;i<in.length;i++) {
			int idx=(int)(Math.random()*in.length);
			long tmp=in[i];
			in[i]=in[idx];
			in[idx]=tmp;
		}
	}
}