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

// ===================================================================
// This file contains a collection of Z-Algorithm and related string 
// matching algorithms. Each function is ready to be used as a "black box".
// Read the comments above each one to understand:
//   - What it solves
//   - What input it expects
//   - What it returns
//   - Time complexity
//   - Important constraints / assumptions
// ===================================================================


// ===================================================================
// 1) Z-Algorithm (Core)
//    The Z-array (or Z-function) of a string s is an array z where
//    z[i] = the length of the longest substring starting at i that 
//    matches the prefix of s.
// 
//    Example: s = "aaaaa"
//      z[1] = 4 (s[0..3] == s[1..4])
//      z[2] = 3 (s[0..2] == s[2..4])
//      z[3] = 2
//      z[4] = 1
//
//    Example: s = "abcab"
//      z[3] = 2 (s[0..1] == s[3..4] = "ab")
// ===================================================================

// 1.1) Compute the Z-array for a given string.
//      Parameters:
//        - s: the input string.
//      Returns:
//        - a vector<int> where z[i] is the Z-value at index i.
//          By definition, z[0] is usually set to 0 (or n, both are common;
//          here we set it to 0).
//      Time complexity: O(n) where n = s.length().
//      Constraint: none.
//      Note: This is the core function. All other functions in this file
//            build on top of it.
vector<int> zAlgorithm(const string& s) {
    int n = s.size();
    vector<int> z(n, 0);
    int l = 0, r = 0; // [l, r] is the current Z-box (the rightmost segment that matches the prefix)
    for (int i = 1; i < n; i++) {
        if (i <= r) {
            z[i] = min(r - i + 1, z[i - l]);
        }
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
    return z;
}

// ===================================================================
// 2) Pattern Matching using Z-Algorithm
//    The most common use of Z is to find all occurrences of a pattern
//    inside a text in O(n + m) time.
// ===================================================================

// 2.1) Find all starting positions where pattern 'pat' occurs in 'text'.
//      Parameters:
//        - text: the string to search in.
//        - pat: the pattern string to look for.
//      Returns:
//        - vector<int> containing all indices (0-based) in 'text' 
//          where 'pat' starts.
//      Time complexity: O(|text| + |pat|).
//      Constraint: none.
//      Note: This function uses the trick: concatenate pat + '#' + text,
//            where '#' is a character that does not appear in either.
//            Then z[i] == |pat| means that pat appears at position (i - |pat| - 1) in text.
vector<int> findPatternOccurrences(const string& text, const string& pat) {
    string combined = pat + "#" + text;
    vector<int> z = zAlgorithm(combined);
    int m = pat.size();
    vector<int> occurrences;
    for (int i = m + 1; i < (int)z.size(); i++) {
        if (z[i] == m) {
            // The pattern starts at this position in 'text'
            occurrences.push_back(i - m - 1);
        }
    }
    return occurrences;
}

// 2.2) Count how many times 'pat' appears in 'text' (non-overlapping occurrences).
//      Parameters:
//        - text: the string to search in.
//        - pat: the pattern string.
//      Returns:
//        - the number of times 'pat' appears as a substring (non-overlapping).
//      Time complexity: O(|text| + |pat|).
//      Constraint: none.
//      Note: This is different from just counting all occurrences because
//            it skips overlapping ones. For example, in "aaaa", pattern "aa"
//            appears 3 times overlapping, but non-overlapping only 2 times.
int countNonOverlappingOccurrences(const string& text, const string& pat) {
    vector<int> occ = findPatternOccurrences(text, pat);
    if (occ.empty()) return 0;
    int cnt = 0;
    int lastEnd = -1;
    for (int pos : occ) {
        if (pos >= lastEnd) {
            cnt++;
            lastEnd = pos + pat.size();
        }
    }
    return cnt;
}

// ===================================================================
// 3) Advanced Z-Algorithm Applications
//    These are common problems that can be solved with Z.
// ===================================================================

// 3.1) Find the longest substring that appears at least twice in a string.
//      Parameters:
//        - s: the input string.
//      Returns:
//        - the length of the longest substring that appears in at least two
//          different positions (overlapping allowed).
//      Time complexity: O(n).
//      Constraint: none.
//      Note: The answer is simply the maximum value in the Z-array (except z[0]).
int longestSubstringAppearingTwice(const string& s) {
    vector<int> z = zAlgorithm(s);
    int ans = 0;
    for (int i = 1; i < (int)z.size(); i++) {
        ans = max(ans, z[i]);
    }
    return ans;
}

// 3.2) Find the lexicographically smallest rotation of a string.
//      Parameters:
//        - s: the input string.
//      Returns:
//        - the lexicographically smallest rotation of s.
//      Time complexity: O(n) using Booth's algorithm.
//      Constraint: none.
//      Note: The previous Z-only implementation was incorrect for some cases.
//            This version is correct and still runs in O(n).
string lexicographicallySmallestRotation(const string& s) {
    // Booth's algorithm for minimal string rotation
    string doubled = s + s;
    int n = s.size();
    int i = 0, j = 1, k = 0;
    while (i < n && j < n && k < n) {
        char a = doubled[i + k];
        char b = doubled[j + k];
        if (a == b) {
            k++;
        } else if (a < b) {
            j += k + 1;
            if (j <= i) j = i + 1;
            k = 0;
        } else {
            i += k + 1;
            if (i <= j) i = j + 1;
            k = 0;
        }
    }
    int start = min(i, j);
    return s.substr(start) + s.substr(0, start);
}

// 3.3) Count the number of distinct substrings of a string.
//      Parameters:
//        - s: the input string.
//      Returns:
//        - the total number of distinct non-empty substrings of s.
//      Time complexity: O(n) with suffix automaton or O(n log n) with suffix array.
//      This placeholder returns 0. For large n, use suffix array + LCP (provided below).
//      An O(n^2) Z-based method exists but is too slow for n > 5000.
long long countDistinctSubstringsZ(const string& s) {
    // Not implemented – use the suffix array + LCP functions instead.
    return 0;
}

// ===================================================================
// 4) Z-Algorithm for Arrays (Generalization)
//    The Z-algorithm works on any sequence of comparable elements,
//    not just characters. Below is a generic version that works on vectors.
// ===================================================================

// 4.1) Compute Z-array for a vector of integers (or any comparable type).
//      Parameters:
//        - vec: a vector of elements (must support the == operator).
//      Returns:
//        - vector<int> z where z[i] is the Z-value for the vector.
//      Time complexity: O(n).
//      Constraint: The elements must be comparable with '=='.
//      Note: This is useful for pattern matching on arrays, e.g., finding
//            a subarray pattern inside an array.
template<typename T>
vector<int> zAlgorithmArray(const vector<T>& vec) {
    int n = vec.size();
    vector<int> z(n, 0);
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i <= r) {
            z[i] = min(r - i + 1, z[i - l]);
        }
        while (i + z[i] < n && vec[z[i]] == vec[i + z[i]]) {
            z[i]++;
        }
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
    return z;
}

// 4.2) Find all occurrences of a pattern array inside a text array.
//      Parameters:
//        - text: the vector to search in.
//        - pat: the pattern vector.
//      Returns:
//        - vector<int> of starting indices where 'pat' occurs in 'text'.
//      Time complexity: O(|text| + |pat|).
//      Constraint: The element types must be comparable with '=='.
//      Note: Uses a sentinel that must not appear in the data. Here we use -1,
//            change it if your arrays can contain -1.
vector<int> findPatternOccurrencesArray(const vector<int>& text, const vector<int>& pat) {
    vector<int> combined;
    combined.reserve(pat.size() + 1 + text.size());
    for (int x : pat) combined.push_back(x);
    combined.push_back(-1); // sentinel (must not appear in text or pat)
    for (int x : text) combined.push_back(x);
    vector<int> z = zAlgorithmArray(combined);
    int m = pat.size();
    vector<int> occ;
    for (int i = m + 1; i < (int)z.size(); i++) {
        if (z[i] == m) {
            occ.push_back(i - m - 1);
        }
    }
    return occ;
}

// ===================================================================
// 5) KMP (Knuth-Morris-Pratt) Algorithm
//    KMP is another linear-time string matching algorithm, similar to Z.
//    It uses a prefix function (pi) instead of Z.
//    I include it here because it is often used together with Z.
// ===================================================================

// 5.1) Compute the prefix function (pi) for a string.
//      Parameters:
//        - s: the input string.
//      Returns:
//        - vector<int> pi where pi[i] = the length of the longest proper
//          prefix of s[0..i] that is also a suffix of s[0..i].
//      Time complexity: O(n).
//      Constraint: none.
//      Note: pi[0] is always 0.
vector<int> computePrefixFunction(const string& s) {
    int n = s.size();
    vector<int> pi(n, 0);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) {
            j = pi[j - 1];
        }
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }
    return pi;
}

// 5.2) Find all occurrences of a pattern in a text using KMP.
//      Parameters:
//        - text: the string to search in.
//        - pat: the pattern string.
//      Returns:
//        - vector<int> of starting indices.
//      Time complexity: O(|text| + |pat|).
//      Constraint: none.
//      Note: This is an alternative to Z-based matching. KMP can be more
//            memory-efficient because it does not need to store the full Z-array.
vector<int> kmpPatternOccurrences(const string& text, const string& pat) {
    if (pat.empty()) return {};
    string combined = pat + "#" + text;
    vector<int> pi = computePrefixFunction(combined);
    int m = pat.size();
    vector<int> occ;
    for (int i = m + 1; i < (int)pi.size(); i++) {
        if (pi[i] == m) {
            occ.push_back(i - 2 * m);
        }
    }
    return occ;
}

// 5.3) Find the period of a string (the smallest period).
//      Parameters:
//        - s: the input string.
//      Returns:
//        - the length of the smallest period.
//        - The period p means s[i] = s[i + p] for all i < n - p.
//      Time complexity: O(n).
//      Constraint: none.
//      Note: If the string has no period, the answer is n.
//            For example, "abcabc" has period 3.
//            "aaaa" has period 1.
int smallestPeriodKMP(const string& s) {
    int n = s.size();
    vector<int> pi = computePrefixFunction(s);
    int p = n - pi[n - 1];
    if (n % p == 0) return p;
    return n;
}

// ===================================================================
// 6) Manacher's Algorithm (Palindromic Substrings)
//    While not Z, Manacher is another linear-time string algorithm that
//    is often needed in the same problems. I include it here for completeness.
// ===================================================================

// 6.1) Manacher's algorithm to find the longest palindromic substring.
//      Parameters:
//        - s: the input string.
//      Returns:
//        - the longest palindromic substring.
//      Time complexity: O(n).
//      Constraint: none.
//      Note: This algorithm also gives the radius of all palindromes.
string longestPalindromeManacher(const string& s) {
    // Transform s: insert '#' between characters and at ends.
    // e.g., "abc" -> "#a#b#c#"
    string t = "#";
    for (char c : s) {
        t += c;
        t += '#';
    }
    int n = t.size();
    vector<int> p(n, 0); // p[i] = radius of the palindrome centered at i
    int center = 0, right = 0;
    for (int i = 0; i < n; i++) {
        int mirror = 2 * center - i;
        if (i < right) {
            p[i] = min(right - i, p[mirror]);
        }
        // Expand
        while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n && t[i - p[i] - 1] == t[i + p[i] + 1]) {
            p[i]++;
        }
        // Update center and right
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
    }
    // Find the maximum radius
    int maxLen = 0;
    int bestCenter = 0;
    for (int i = 0; i < n; i++) {
        if (p[i] > maxLen) {
            maxLen = p[i];
            bestCenter = i;
        }
    }
    // Recover the original string
    int start = (bestCenter - maxLen) / 2;
    return s.substr(start, maxLen);
}

// ===================================================================
// 7) Rolling Hash (Rabin-Karp)
//    Not strictly Z, but it is a very common technique for string matching
//    and is often used in ECPC/ACPC problems.
// ===================================================================

// 7.1) Compute the hash of a string using a rolling hash technique.
//      Parameters:
//        - s: the input string.
//      Returns:
//        - a vector of long long hashes (prefix hashes).
//      Time complexity: O(n).
//      Constraint: Uses two moduli to reduce collisions. Assumes lowercase letters.
//      Note: This is a double-hash implementation. Change the base or moduli if needed.
struct RollingHash {
    static const long long BASE = 31;
    static const long long MOD1 = 1000000007;
    static const long long MOD2 = 1000000009;
    vector<long long> pow1, pow2, hash1, hash2;

    RollingHash(const string& s) {
        int n = s.size();
        pow1.resize(n + 1);
        pow2.resize(n + 1);
        hash1.resize(n + 1);
        hash2.resize(n + 1);
        pow1[0] = pow2[0] = 1;
        for (int i = 0; i < n; i++) {
            pow1[i + 1] = (pow1[i] * BASE) % MOD1;
            pow2[i + 1] = (pow2[i] * BASE) % MOD2;
            hash1[i + 1] = (hash1[i] * BASE + (s[i] - 'a' + 1)) % MOD1;
            hash2[i + 1] = (hash2[i] * BASE + (s[i] - 'a' + 1)) % MOD2;
        }
    }

    // Returns the pair of hashes for substring s[l..r] (0-based, inclusive).
    pair<long long, long long> getHash(int l, int r) {
        long long h1 = (hash1[r + 1] - (hash1[l] * pow1[r - l + 1]) % MOD1 + MOD1) % MOD1;
        long long h2 = (hash2[r + 1] - (hash2[l] * pow2[r - l + 1]) % MOD2 + MOD2) % MOD2;
        return {h1, h2};
    }
};

// ===================================================================
// 8) Suffix Array (with LCP)
//    This is a more advanced data structure, but it is very powerful.
//    I include the basics here for reference.
// ===================================================================

// 8.1) Build a suffix array for a string.
//      Parameters:
//        - s: the input string.
//      Returns:
//        - vector<int> sa where sa[i] is the starting index of the i-th suffix
//          in lexicographic order.
//      Time complexity: O(n log n) using the doubling algorithm.
//      Constraint: none.
//      Note: This is a simplified version using sorting with pairs.
//            For ECPC/ACPC, O(n log^2 n) might be acceptable for n up to 1e5.
vector<int> buildSuffixArray(const string& s) {
    int n = s.size();
    vector<int> sa(n), rank(n), tmp(n);
    for (int i = 0; i < n; i++) {
        sa[i] = i;
        rank[i] = s[i];
    }
    for (int k = 1; k < n; k <<= 1) {
        auto cmp = [&](int i, int j) {
            if (rank[i] != rank[j]) return rank[i] < rank[j];
            int ri = (i + k < n) ? rank[i + k] : -1;
            int rj = (j + k < n) ? rank[j + k] : -1;
            return ri < rj;
        };
        sort(sa.begin(), sa.end(), cmp);
        tmp[sa[0]] = 0;
        for (int i = 1; i < n; i++) {
            tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0);
        }
        rank = tmp;
        if (rank[sa[n - 1]] == n - 1) break;
    }
    return sa;
}

// 8.2) Build the LCP (Longest Common Prefix) array for a suffix array.
//      Parameters:
//        - s: the original string.
//        - sa: the suffix array.
//      Returns:
//        - vector<int> lcp where lcp[i] = LCP of sa[i] and sa[i+1].
//      Time complexity: O(n).
//      Constraint: The suffix array must be valid.
vector<int> buildLCPArray(const string& s, const vector<int>& sa) {
    int n = s.size();
    vector<int> rank(n);
    for (int i = 0; i < n; i++) {
        rank[sa[i]] = i;
    }
    vector<int> lcp(n - 1);
    int h = 0;
    for (int i = 0; i < n; i++) {
        if (rank[i] == 0) continue;
        int j = sa[rank[i] - 1];
        while (i + h < n && j + h < n && s[i + h] == s[j + h]) h++;
        lcp[rank[i] - 1] = h;
        if (h > 0) h--;
    }
    return lcp;
}

// ===================================================================
// 9) Tricks & Patterns that appeared in ECPC/ACPC
//    These are common ideas that use Z or related algorithms.
// ===================================================================

// 9.1) Check if a string is a concatenation of multiple copies of a pattern.
//      Parameters:
//        - s: the input string.
//      Returns:
//        - true if s can be written as p + p + ... + p for some pattern p.
//      Time complexity: O(n).
//      Constraint: none.
//      Note: This uses the prefix function to find the period.
bool isPowerOfString(const string& s) {
    int n = s.size();
    vector<int> pi = computePrefixFunction(s);
    int p = n - pi[n - 1];
    return (n % p == 0);
}

// 9.2) Find the number of times a string is repeated in a pattern.
//      Parameters:
//        - s: the input string.
//      Returns:
//        - the maximum k such that s is a repetition of some string p, k times.
//      Time complexity: O(n).
//      Constraint: none.
//      Note: For "abcabcabc", answer is 3 (p = "abc").
int maxRepetitions(const string& s) {
    int n = s.size();
    vector<int> pi = computePrefixFunction(s);
    int p = n - pi[n - 1];
    if (n % p == 0) return n / p;
    return 1;
}

// 9.3) Z-algorithm on prefix sums? Not exactly, but sometimes we use Z on
//      transformed arrays. For example, comparing differences between elements.
//      Problem: Find the longest subarray that is a "mountain" or matches a pattern.
//      We can use Z on an array of differences (s[i+1] - s[i]) to find
//      matching patterns.
//
//      Example: Given an array, find the longest subarray that is a repeating
//               pattern of "up, down, up, down...".
//      We can encode the array as a string of '+' and '-' signs and use Z.
//      But that is problem-specific.
//      I will not implement it generically, but mention it.

// ===================================================================
// 10) Advanced: Counting substrings where no character appears more than
//     k times (using two pointers + hash) – not Z, but common in ECPC.
//     I include it because it is a common trick.
// ===================================================================

// 10.1) Count substrings with at most K distinct characters.
//       This is already covered in the Two Pointers template, but I include
//       it here for reference.
long long countSubstringsAtMostKDistinct(const string& s, int k) {
    int n = s.size();
    unordered_map<char, int> freq;
    int l = 0;
    long long ans = 0;
    for (int r = 0; r < n; r++) {
        freq[s[r]]++;
        while ((int)freq.size() > k) {
            freq[s[l]]--;
            if (freq[s[l]] == 0) freq.erase(s[l]);
            l++;
        }
        ans += (r - l + 1);
    }
    return ans;
}

// ===================================================================
// 11) Helper: Z-array for string with wildcard matching? (Advanced)
//     Sometimes problems ask to match patterns with '?' wildcard.
//     We can use Z with a custom comparator that treats '?' as matching any char.
//     This is not implemented here because it requires a modified Z algorithm.
// ===================================================================

// ===================================================================
// 12) "MUBIS" – This term is not standard. Perhaps it refers to "Multiplicative"?
//     Or it could be an acronym from a specific contest.
//     I will assume you meant "Multiplicative" or "Minimum Unique Prefix"?
//     If it's an ECPC-specific term, please clarify. I will add a placeholder.
// ===================================================================

// 12.1) Placeholder for MUBIS-related function.
//       If you provide more details, I can implement it.
int mubisFunction(const string& s) {
    // TODO: Implement MUBIS if you provide more details.
    return 0;
}

// ===================================================================
// main() with example usage (you can ignore this part)
// ===================================================================

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

    // Example 1: Z-algorithm
    string s = "ababab";
    vector<int> z = zAlgorithm(s);
    cout << "Z-array for " << s << ": ";
    for (int x : z) cout << x << " ";
    cout << "\n";

    // Example 2: Pattern matching
    string text = "abababab";
    string pat = "aba";
    vector<int> occ = findPatternOccurrences(text, pat);
    cout << "Occurrences of '" << pat << "' in '" << text << "': ";
    for (int pos : occ) cout << pos << " ";
    cout << "\n";

    // Example 3: Longest palindrome
    string pal = "babad";
    cout << "Longest palindrome in " << pal << ": " << longestPalindromeManacher(pal) << "\n";

    // Example 4: Lexicographically smallest rotation
    string rot = "bca";
    cout << "Smallest rotation of " << rot << ": " << lexicographicallySmallestRotation(rot) << "\n";

    // Example 5: KMP period
    string period = "abcabcabc";
    cout << "Smallest period of " << period << ": " << smallestPeriodKMP(period) << "\n";

    return 0;
}