#include <bits/stdc++.h>
using namespace std;

using ll = long long;

// =============================================================================
// Suffix Array & LCP (Longest Common Prefix) – Collection of Algorithms
// =============================================================================
//
// This file contains a set of functions that work with Suffix Arrays and
// LCP arrays. Each function is explained with:
//   - What it does (Purpose)
//   - What it expects (Input)
//   - What it returns (Output)
//   - Time complexity
//   - Important notes and constraints
//
// TERMINOLOGY (in simple words):
//   - Suffix: a substring that starts at some position and goes to the end.
//   - Suffix Array (SA): the starting positions of all suffixes, sorted
//     lexicographically (dictionary order).
//   - Rank: the position (index) of a suffix inside the Suffix Array.
//   - LCP: Longest Common Prefix between two strings (or suffixes).
//   - LCP Array: `lcp[i]` = LCP of the suffixes at SA[i] and SA[i+1].
//   - RMQ: Range Minimum Query – quickly find the minimum value in a range.
//   - Sparse Table: a data structure that answers RMQ in O(1) after
//     O(n log n) preprocessing.
//   - Sentinel: a special unique character (here '$') added to the end of
//     the string to make suffix sorting easier. It is smaller than all
//     normal characters.
//   - Separator: a unique character used when joining several strings into
//     one; it must not appear in the original strings.
// =============================================================================


// =============================================================================
// 1) BUILD SUFFIX ARRAY – O(n log n)
// =============================================================================

/**
 * Purpose:
 *   Builds the suffix array of a given string.
 *
 * Input:
 *   s : the input string (can contain any printable ASCII characters except '$').
 *       A sentinel '$' is added automatically – do NOT include it yourself.
 * Output:
 *   A vector<int> containing the starting positions (0‑based) of all suffixes,
 *   sorted in lexicographical order. The sentinel's position is removed.
 * Time Complexity:
 *   O(n log n) where n = s.length().
 * Constraints:
 *   - The character '$' must NOT appear in s.
 *   - Works comfortably for strings up to ~2·10^5.
 * Notes:
 *   - The algorithm uses a standard counting‑sort / radix‑sort approach.
 *   - The returned SA size equals the length of the original string.
 */
vector<int> buildSuffixArray(const string& s) {
    string str = s;
    str.push_back('$');                // sentinel (smaller than any other char)
    int n = (int)str.size();
    vector<int> p(n), c(n);
    
    // k = 0 : sort single characters
    vector<pair<char,int>> a(n);
    for (int i = 0; i < n; i++) a[i] = {str[i], i};
    sort(a.begin(), a.end());
    for (int i = 0; i < n; i++) p[i] = a[i].second;
    c[p[0]] = 0;
    for (int i = 1; i < n; i++) {
        c[p[i]] = c[p[i-1]] + (a[i].first != a[i-1].first);
    }
    
    // transitions
    vector<int> pn(n), cn(n);
    for (int h = 0; (1 << h) < n; h++) {
        for (int i = 0; i < n; i++) {
            pn[i] = p[i] - (1 << h);
            if (pn[i] < 0) pn[i] += n;
        }
        vector<int> cnt(n, 0);
        for (int i = 0; i < n; i++) cnt[c[pn[i]]]++;
        vector<int> pos(n);
        pos[0] = 0;
        for (int i = 1; i < n; i++) pos[i] = pos[i-1] + cnt[i-1];
        for (int i = 0; i < n; i++) {
            int cl = c[pn[i]];
            p[pos[cl]++] = pn[i];
        }
        cn[p[0]] = 0;
        for (int i = 1; i < n; i++) {
            pair<int,int> cur = {c[p[i]], c[(p[i] + (1 << h)) % n]};
            pair<int,int> prev = {c[p[i-1]], c[(p[i-1] + (1 << h)) % n]};
            cn[p[i]] = cn[p[i-1]] + (cur != prev);
        }
        c.swap(cn);
    }
    
    // remove the sentinel position (it is always the last index n-1 after sorting)
    vector<int> sa;
    sa.reserve(n-1);
    for (int x : p) if (x != n-1) sa.push_back(x);
    return sa;
}


// =============================================================================
// 2) BUILD LCP ARRAY – O(n) (Kasai's algorithm)
// =============================================================================

/**
 * Purpose:
 *   Builds the LCP array from the original string and its suffix array.
 *   lcp[i] = LCP of suffixes sa[i] and sa[i+1].
 *
 * Input:
 *   s  : the original string (without sentinel)
 *   sa : suffix array of s (from buildSuffixArray)
 * Output:
 *   A vector<int> of size n-1 (empty if n <= 1).
 * Time Complexity:
 *   O(n)
 * Constraints:
 *   sa must be a valid suffix array of s.
 */
vector<int> buildLCP(const string& s, const vector<int>& sa) {
    int n = (int)s.size();
    vector<int> rank(n, 0);
    for (int i = 0; i < n; i++) rank[sa[i]] = i;
    vector<int> lcp(max(0, n-1), 0);
    int k = 0;
    for (int i = 0; i < n; i++) {
        if (rank[i] == n-1) { k = 0; continue; }
        int j = sa[rank[i] + 1];
        while (i + k < n && j + k < n && s[i+k] == s[j+k]) k++;
        lcp[rank[i]] = k;
        if (k) k--;
    }
    return lcp;
}


// =============================================================================
// 3) SPARSE TABLE FOR RMQ ON LCP
// =============================================================================

/**
 * Purpose:
 *   Preprocesses the LCP array to answer Range Minimum Queries (RMQ) in O(1).
 *   This allows fast LCP queries between any two suffixes.
 *
 * Input:
 *   lcp : the LCP array (size n-1; may be empty if n <= 1).
 * Output:
 *   An object that can answer min(lcp[l..r]) in O(1).
 * Time Complexity:
 *   Preprocessing: O(m log m) where m = lcp.size().
 *   Query: O(1).
 */
class LCPRMQ {
private:
    vector<int> lg;
    vector<vector<int>> st;
public:
    LCPRMQ(const vector<int>& lcp) {
        int m = (int)lcp.size();
        lg.assign(m + 1, 0);
        for (int i = 2; i <= m; i++) lg[i] = lg[i/2] + 1;
        if (m == 0) return;
        st.assign(m, vector<int>(lg[m] + 1));
        for (int i = 0; i < m; i++) st[i][0] = lcp[i];
        for (int k = 1; (1 << k) <= m; k++) {
            for (int i = 0; i + (1 << k) <= m; i++) {
                st[i][k] = min(st[i][k-1], st[i + (1 << (k-1))][k-1]);
            }
        }
    }

    /**
     * Query the minimum LCP in the range [l, r] inclusive.
     * Requires 0 <= l <= r < lcp.size().
     */
    int query(int l, int r) const {
        if (l > r) return INT_MAX;   // empty range
        int len = r - l + 1;
        int k = lg[len];
        return min(st[l][k], st[r - (1 << k) + 1][k]);
    }
};


// =============================================================================
// 4) LCP BETWEEN ANY TWO POSITIONS – O(1)
// =============================================================================

/**
 * Purpose:
 *   Computes the LCP of the two suffixes starting at positions i and j
 *   in the original string.
 *
 * Input:
 *   s    : the original string
 *   sa   : suffix array of s
 *   rank : rank array (rank[pos] = index in SA)
 *   rmq  : LCPRMQ object built from the LCP array
 *   i, j : starting positions (0‑based) in the string
 * Output:
 *   Length of the longest common prefix of s[i..] and s[j..].
 * Time Complexity:
 *   O(1)
 * Notes:
 *   If i == j, the whole remaining length is returned.
 */
int lcpBetweenPositions(const string& s, const vector<int>& sa,
                        const vector<int>& rank, const LCPRMQ& rmq,
                        int i, int j) {
    int n = (int)s.size();
    if (i == j) return n - i;
    int l = rank[i], r = rank[j];
    if (l > r) swap(l, r);
    // LCP of SA[l] and SA[r] is the minimum in lcp[l .. r-1]
    return rmq.query(l, r-1);
}


// =============================================================================
// 5) PATTERN SEARCH (count / find occurrences)
// =============================================================================

/**
 * Purpose:
 *   Count how many times a pattern occurs as a substring in the text.
 *
 * Input:
 *   s       : the text
 *   sa      : suffix array of s
 *   pattern : the pattern to search for
 * Output:
 *   Number of starting positions where pattern appears.
 * Time Complexity:
 *   O(|pattern| * log n) using two binary searches.
 * Notes:
 *   If the pattern is empty, it returns n+1 (all positions + empty suffix).
 */
int countOccurrences(const string& s, const vector<int>& sa, const string& pattern) {
    int n = (int)s.size();
    int m = (int)pattern.size();
    if (m == 0) return n + 1;

    // compare a suffix starting at 'pos' with the pattern
    auto suffixCmp = [&](int pos, const string& pat) -> int {
        int len = min((int)pat.size(), n - pos);
        int cmp = s.compare(pos, len, pat, 0, len);
        if (cmp != 0) return cmp;
        if (len == (int)pat.size()) return 0;       // strings equal up to pat length
        return (n - pos < (int)pat.size()) ? -1 : 1; // shorter suffix < pattern
    };

    // lower bound: first index where suffix >= pattern
    int lo = 0, hi = n;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (suffixCmp(sa[mid], pattern) < 0)
            lo = mid + 1;
        else
            hi = mid;
    }
    int first = lo;

    // upper bound: first index where suffix > pattern
    lo = 0; hi = n;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (suffixCmp(sa[mid], pattern) <= 0)
            lo = mid + 1;
        else
            hi = mid;
    }
    int last = lo;

    return last - first;
}

/**
 * Purpose:
 *   Returns all starting positions where the pattern occurs in the text.
 *
 * Input:
 *   s, sa, pattern : same as countOccurrences
 * Output:
 *   A vector<int> of starting indices (0‑based). Sorted ascending.
 * Time Complexity:
 *   O(|pattern| * log n + occ), occ = number of occurrences.
 */
vector<int> findOccurrences(const string& s, const vector<int>& sa, const string& pattern) {
    int n = (int)s.size();
    int m = (int)pattern.size();
    vector<int> res;
    if (m == 0) {
        for (int i = 0; i <= n; i++) res.push_back(i);
        return res;
    }

    auto suffixCmp = [&](int pos, const string& pat) -> int {
        int len = min((int)pat.size(), n - pos);
        int cmp = s.compare(pos, len, pat, 0, len);
        if (cmp != 0) return cmp;
        if (len == (int)pat.size()) return 0;
        return (n - pos < (int)pat.size()) ? -1 : 1;
    };

    int lo = 0, hi = n;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (suffixCmp(sa[mid], pattern) < 0)
            lo = mid + 1;
        else
            hi = mid;
    }
    int first = lo;

    lo = 0; hi = n;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (suffixCmp(sa[mid], pattern) <= 0)
            lo = mid + 1;
        else
            hi = mid;
    }
    int last = lo;

    for (int i = first; i < last; i++) res.push_back(sa[i]);
    return res;
}


// =============================================================================
// 6) COUNT DISTINCT SUBSTRINGS
// =============================================================================

/**
 * Purpose:
 *   Count the number of distinct non‑empty substrings of a string.
 *
 * Input:
 *   s : the string.
 * Output:
 *   A 64‑bit integer: total distinct substrings.
 * Time Complexity:
 *   O(n log n) (SA construction) + O(n) (LCP).
 * Formula:
 *   Total possible substrings = n*(n+1)/2, subtract sum(LCP) because each
 *   LCP value counts duplicate prefixes between adjacent suffixes.
 */
ll countDistinctSubstrings(const string& s) {
    int n = (int)s.size();
    vector<int> sa = buildSuffixArray(s);
    vector<int> lcp = buildLCP(s, sa);
    ll total = 1LL * n * (n + 1) / 2;
    ll sumLCP = 0;
    for (int x : lcp) sumLCP += x;
    return total - sumLCP;
}


// =============================================================================
// 7) LONGEST REPEATED SUBSTRING
// =============================================================================

/**
 * Purpose:
 *   Find the length of the longest substring that appears at least twice
 *   (overlapping allowed).
 *
 * Input:
 *   s : the string.
 * Output:
 *   Length of the longest repeated substring, or 0 if none.
 * Time Complexity:
 *   O(n log n) (SA) + O(n) (LCP). The answer is simply max(LCP array).
 * Notes:
 *   To obtain the actual substring, use sa[i] and lcp[i] at the maximum index.
 */
int longestRepeatedSubstring(const string& s) {
    int n = (int)s.size();
    if (n < 2) return 0;
    vector<int> sa = buildSuffixArray(s);
    vector<int> lcp = buildLCP(s, sa);
    int best = 0;
    for (int x : lcp) best = max(best, x);
    return best;
}


// =============================================================================
// 8) LONGEST COMMON SUBSTRING BETWEEN TWO STRINGS
// =============================================================================

/**
 * Purpose:
 *   Find the length of the longest substring that appears in both s1 and s2.
 *
 * Input:
 *   s1, s2 : two strings.
 * Output:
 *   Length of the longest common substring (0 if none).
 * Time Complexity:
 *   O((n+m) log(n+m)) for SA + LCP.
 * Constraints:
 *   The separator character '#' must NOT appear in s1 or s2.
 * Notes:
 *   The two strings are concatenated as s1 + '#' + s2. The suffix array of
 *   this combined string is built (with an automatic sentinel). Then we scan
 *   the LCP array and consider only pairs of suffixes where one comes from s1
 *   and the other from s2.
 */
int longestCommonSubstring(const string& s1, const string& s2) {
    string comb = s1 + "#" + s2;          // sentinel will be added internally
    int n1 = s1.size();
    vector<int> sa = buildSuffixArray(comb);
    vector<int> lcp = buildLCP(comb, sa);
    int best = 0;
    for (int i = 0; i < (int)lcp.size(); i++) {
        int pos1 = sa[i];
        int pos2 = sa[i+1];
        bool in1_first  = (pos1 < n1);
        bool in2_first  = (pos1 > n1);    // > because separator is at n1
        bool in1_second = (pos2 < n1);
        bool in2_second = (pos2 > n1);
        if ((in1_first && in2_second) || (in2_first && in1_second)) {
            best = max(best, lcp[i]);
        }
    }
    return best;
}


// =============================================================================
// 9) LONGEST COMMON SUBSTRING AMONG MULTIPLE STRINGS
// =============================================================================

/**
 * Purpose:
 *   Find the length of the longest substring that appears in ALL given strings.
 *
 * Input:
 *   strs : vector of strings.
 * Output:
 *   Length of the longest common substring (0 if none).
 * Time Complexity:
 *   O(N log N + N log L) where N = total length of all strings + separators,
 *   L = maximum possible answer.
 * Method:
 *   1. Concatenate all strings with unique separators (characters from ASCII 1
 *      upwards, which are not printable – safe because inputs are printable ASCII).
 *   2. Build SA and LCP of the combined string.
 *   3. Binary search on the answer length. For a given length `len`, check if
 *      there exists a block of suffixes in the SA such that:
 *         - every adjacent LCP inside the block is >= len,
 *         - the block contains suffixes from every original string.
 *
 * Constraints:
 *   - Strings must consist of printable ASCII characters (32‑126).
 *   - k >= 1 (if k == 1 the whole string is the answer).
 */
int longestCommonSubstringMultiple(vector<string>& strs) {
    int k = (int)strs.size();
    if (k == 0) return 0;
    if (k == 1) return (int)strs[0].size();

    // Build the concatenated string and an owner array for every position.
    string combined;
    vector<int> owner;   // owner[i] = index of the string this character belongs to,
                         // -1 for separators.
    for (int i = 0; i < k; i++) {
        if (i > 0) {
            // Use ASCII codes 1,2,3... as unique separators.
            // They are guaranteed not to appear in the original strings.
            combined.push_back(char(1 + i));   // separator for string i
            owner.push_back(-1);
        }
        for (char c : strs[i]) {
            combined.push_back(c);
            owner.push_back(i);
        }
    }

    int n = combined.size();
    vector<int> sa = buildSuffixArray(combined);
    vector<int> lcp = buildLCP(combined, sa);

    // Map each suffix (by its SA index) to its owner.
    vector<int> saOwner(n, -1);
    for (int i = 0; i < n; i++) {
        int pos = sa[i];
        if (pos < (int)owner.size())
            saOwner[i] = owner[pos];
    }

    // Check if a common substring of length `len` exists.
    auto check = [&](int len) -> bool {
        vector<int> cnt(k, 0);
        int distinct = 0;
        for (int i = 0; i < n; i++) {
            int own = saOwner[i];
            if (own != -1) {
                if (cnt[own] == 0) distinct++;
                cnt[own]++;
            }

            // End of a block when we are at the last suffix or the LCP to the
            // next suffix is smaller than `len`.
            if (i == n-1 || lcp[i] < len) {
                if (distinct == k) return true;
                // reset for next block
                fill(cnt.begin(), cnt.end(), 0);
                distinct = 0;
            }
        }
        return false;
    };

    // Binary search for the maximum possible length.
    int lo = 0, hi = n + 1;
    while (lo < hi) {
        int mid = (lo + hi + 1) / 2;
        if (check(mid))
            lo = mid;
        else
            hi = mid - 1;
    }
    return lo;
}


// =============================================================================
// 10) MINIMUM LEXICOGRAPHIC ROTATION
// =============================================================================

/**
 * Purpose:
 *   Find the starting index of the lexicographically smallest rotation
 *   of a string.
 *
 * Input:
 *   s : the string (non‑empty).
 * Output:
 *   The 0‑based index where the smallest rotation begins.
 * Time Complexity:
 *   O(n log n) (by building the suffix array of s+s).
 * How it works:
 *   Build the string t = s + s. The smallest rotation is the prefix of length n
 *   of the smallest suffix of t that starts at a position < n.
 */
int minRotation(const string& s) {
    int n = (int)s.size();
    string t = s + s;
    vector<int> sa = buildSuffixArray(t);
    for (int pos : sa) {
        if (pos < n) return pos;
    }
    return 0; // never reached
}


// =============================================================================
// 11) COMPARE TWO SUBSTRINGS IN O(1)
// =============================================================================

/**
 * Purpose:
 *   Compare two substrings of the same string (both of equal length)
 *   lexicographically.
 *
 * Input:
 *   s    : the original string
 *   sa   : suffix array of s
 *   rank : rank array (rank[pos] = index in SA)
 *   rmq  : LCPRMQ object built from the LCP array
 *   i, j : starting positions (0‑based)
 *   len  : length of both substrings (i+len <= n, j+len <= n)
 * Output:
 *   -1 if s[i..i+len-1] < s[j..j+len-1]
 *    0 if equal
 *   +1 if greater.
 * Time Complexity:
 *   O(1)
 */
int compareSubstrings(const string& s, const vector<int>& sa,
                      const vector<int>& rank, const LCPRMQ& rmq,
                      int i, int j, int len) {
    int n = (int)s.size();
    if (i == j) return 0;
    int common = lcpBetweenPositions(s, sa, rank, rmq, i, j);
    if (common >= len) return 0;
    return (s[i + common] < s[j + common]) ? -1 : 1;
}


// =============================================================================
// 12) LONGEST SUBSTRING WITH AT LEAST K OCCURRENCES
// =============================================================================

/**
 * Purpose:
 *   Find the length of the longest substring that appears at least k times
 *   in the string (overlapping occurrences are allowed).
 *
 * Input:
 *   s : the string
 *   k : minimum number of occurrences required (k >= 2)
 * Output:
 *   Maximum length of such a substring, or 0 if none.
 * Time Complexity:
 *   O(n log n) for SA+LCP, then O(n) using a sliding window (deque) over
 *   the LCP array.
 * Notes:
 *   The answer is the maximum, over all windows of k-1 consecutive LCP values,
 *   of the minimum LCP in that window.
 */
int longestSubstringWithAtLeastKOccurrences(const string& s, int k) {
    int n = (int)s.size();
    if (k <= 1) return n;
    if (k > n) return 0;
    vector<int> sa = buildSuffixArray(s);
    vector<int> lcp = buildLCP(s, sa);
    int m = (int)lcp.size();
    if (m < k-1) return 0;

    deque<int> dq;
    int ans = 0;
    for (int i = 0; i < m; i++) {
        // maintain deque with increasing values of LCP
        while (!dq.empty() && lcp[dq.back()] >= lcp[i]) dq.pop_back();
        dq.push_back(i);
        // remove elements that fall out of the window of size k-1
        if (dq.front() <= i - (k-1)) dq.pop_front();
        // when we have processed at least k-1 elements, the front is the minimum
        if (i >= k-2) {
            ans = max(ans, lcp[dq.front()]);
        }
    }
    return ans;
}


// =============================================================================
// 13) BUILD BOTH SUFFIX ARRAY AND LCP TOGETHER (convenience)
// =============================================================================

/**
 * Purpose:
 *   Builds the suffix array and the LCP array in one call.
 *
 * Input:
 *   s : the string.
 * Output:
 *   A pair {sa, lcp}.
 * Time Complexity:
 *   O(n log n) for SA, O(n) for LCP.
 */
pair<vector<int>, vector<int>> buildSAandLCP(const string& s) {
    vector<int> sa = buildSuffixArray(s);
    vector<int> lcp = buildLCP(s, sa);
    return {sa, lcp};
}


// =============================================================================
// 14) EXAMPLE USAGE (main)
// =============================================================================

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s = "banana";
    vector<int> sa = buildSuffixArray(s);
    cout << "Suffix Array:\n";
    for (int pos : sa) cout << pos << " ";
    cout << "\n";

    vector<int> lcp = buildLCP(s, sa);
    cout << "LCP Array:\n";
    for (int x : lcp) cout << x << " ";
    cout << "\n";

    cout << "Distinct substrings: " << countDistinctSubstrings(s) << "\n";
    cout << "Longest repeated: " << longestRepeatedSubstring(s) << "\n";
    cout << "Occurrences of 'ana': " << countOccurrences(s, sa, "ana") << "\n";
    auto occ = findOccurrences(s, sa, "ana");
    cout << "Positions: ";
    for (int p : occ) cout << p << " ";
    cout << "\n";

    // LCP between suffixes at positions 1 and 3
    vector<int> rank(s.size());
    for (int i = 0; i < (int)sa.size(); i++) rank[sa[i]] = i;
    LCPRMQ rmq(lcp);
    cout << "LCP(1,3) = " << lcpBetweenPositions(s, sa, rank, rmq, 1, 3) << "\n";

    cout << "Minimum rotation of 'banana': " << minRotation(s) << "\n";

    string s1 = "abcdef", s2 = "zcdemf";
    cout << "LCS between abcdef and zcdemf: " << longestCommonSubstring(s1, s2) << "\n";

    cout << "Longest substring with at least 2 occurrences in 'banana': "
         << longestSubstringWithAtLeastKOccurrences(s, 2) << "\n";

    return 0;
}