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:
﻿#pragma GCC optimize("Ofast,unroll-all-loops")
#pragma GCC optimize("O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
//#pragma GCC target("popcnt")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long double ld;

#define sz(a) (ll)((a).size())
#define fixed cout << setprecision(25) << fixed;
#define all(v) (v).begin(), (v).end()
#define rall(v) v.rbegin(), v.rend()
#define debug(x) cerr << #x << " = " << x << endl;
#define debug2(x, y) cerr << #x << " = " << x <<", "<< #y << " = " << y << endl;
#define debug3(x, y, z) cerr << #x << " = " << x << ", "<< #y << " = " << y << ", "<< #z << " = " << z << endl;
#define debug4(x, y, z, u) cerr << #x << " = " << x << ", "<< #y << " = " << y << ", "<< #z << " = " << z << ", "<< #u << " = " << u << endl;
#define debug_a(x) cerr << #x << endl; for (auto e : (x)) cerr << e << ' '; cerr << endl;
#define debug_b(x) cerr << #x << endl; for (auto e : (x)) cerr << " ( " << e.st << ' ' << e.nd << " ) "; cerr << endl;
#define debug_c(x) cerr << #x << endl; for (auto e : (x)) cerr << " ( " << e[0] << ' ' << e[1] << ' ' << e[2] << " ) "; cerr << endl;
#define pikachu push_back
#define mp make_pair
#define st first
#define nd second
#define i128 __int128
#define pt(s) (s)[sz((s)) - 2]
#define pll pair<ll, ll>

const ll INF = (is_same<int, ll>::value ? 1e9 + 666 : 1e18l + 666);
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

template<class t1, class t2>
inline bool cmin(t1 &a, const t2 &b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class t1, class t2>
inline bool cmax(t1 &a, const t2 &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

inline ll bpow(ll a, ll b, ll mod) {
    ll res = 1;
    for (; b; b >>= 1) {
        if (b & 1) {
            res *= a;
            res %= mod;
        }
        a *= a;
        a %= mod;
    }
    return res;
}

#ifndef LOCAL
void UseFiles(const string &s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
#else

void UseFiles(const string &) {}

#endif

void run();

signed main() {
    iostream::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    run();
}

const ll MOD = 1e9 + 7;
ll n, k;
string s;

bool check(ll x) {
    vector<vector<ll>> pref(n + 2, vector<ll>(k, n + 1));
    vector<pll > bit(k, mp(n + 1, 0));
    for (ll i = n - 1; i >= 0; i--) {
        for (ll c = 0; c < k; c++) {
            if (s[i] == '?' || s[i] == c + 'a') {
                bit[c].nd++;
                if (bit[c].nd >= x) bit[c].st = i + x;
            } else {
                bit[c].nd = 0;
            }
            pref[i][c] = bit[c].st;
        }
    }
    vector<ll> dp((1 << k), n + 1);
    dp[0] = 0;
    for (ll mask = 1; mask < (1 << k); mask++) {
        for (ll p = 0; p < k; p++)
            if ((1 << p) & mask) {
                ll nmask = mask ^ (1 << p);
                cmin(dp[mask], pref[dp[nmask]][p]);
            }
    }
    if (dp[(1 << k) - 1] != n + 1) return true;
    return false;
}

void run() {
    cin >> n >> k >> s;
    ll l = 0, r = n + 1;
    while (r - l > 1) {
        ll m = (r + l) / 2;
        if (check(m)) l = m;
        else r = m;
    }
    cout << l;
}