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

const int INF = 1e9;

// ===================================================================
// 1) Core SAM structure and construction
//    This is the foundation. All other functions use this class.
// ===================================================================

// 1.1) SuffixAutomaton class
//      Purpose:
//        - Builds a SAM for a given string in O(n) time.
//        - Stores all necessary arrays (len, link, next) for the automaton.
//      Input:
//        - s : the input string (typically lowercase letters).
//      Output:
//        - An object that contains the SAM.
//      Time complexity:
//        - O(n * alphabet_size) with array transitions.
//      Constraints:
//        - The string length n must be known.
//        - The alphabet size is assumed constant (e.g., 26 for lowercase).
//      Notes:
//        - The number of states is at most 2*n.
//        - The root is state 0.
//        - The `extend` function adds one character at a time.
//        - This class is used as a black box by all other functions.
struct SuffixAutomaton {
    static const int ALPHABET = 26;          // for lowercase English letters
    vector<array<int, ALPHABET>> next;       // transitions
    vector<int> link;                        // suffix links
    vector<int> len;                         // longest length of strings in this state
    int last;                                // state corresponding to the whole current string

    // Extra members for advanced queries
    vector<bool> isClone;                    // true if state is a clone
    vector<int> occ;                         // occurrence count (will be computed)
    vector<int> firstPos;                    // earliest end position of substrings in this state
    vector<int> lastPos;                     // latest end position of substrings in this state

    SuffixAutomaton() {}
    SuffixAutomaton(const string& s) {
        init(s);
    }

    void init(const string& s) {
        next.clear();
        link.clear();
        len.clear();
        isClone.clear();
        occ.clear();
        firstPos.clear();
        lastPos.clear();

        // Root (state 0)
        next.push_back({});
        for (auto &a : next[0]) a = -1;
        link.push_back(-1);
        len.push_back(0);
        isClone.push_back(false);
        occ.push_back(0);
        firstPos.push_back(INF);
        lastPos.push_back(-INF);
        last = 0;

        for (char c : s) {
            extend(c - 'a');
        }
    }

    void extend(int c) {
        int cur = (int)next.size();
        next.push_back({});
        for (auto &a : next.back()) a = -1;
        len.push_back(len[last] + 1);
        link.push_back(0);
        isClone.push_back(false);
        occ.push_back(1);                     // new state represents a prefix
        firstPos.push_back(len.back() - 1);   // end position of this prefix
        lastPos.push_back(len.back() - 1);

        int p = last;
        while (p != -1 && next[p][c] == -1) {
            next[p][c] = cur;
            p = link[p];
        }
        if (p == -1) {
            link[cur] = 0;
        } else {
            int q = next[p][c];
            if (len[p] + 1 == len[q]) {
                link[cur] = q;
            } else {
                int clone = (int)next.size();
                next.push_back(next[q]);      // copy transitions
                len.push_back(len[p] + 1);
                link.push_back(link[q]);
                isClone.push_back(true);
                occ.push_back(0);
                firstPos.push_back(INF);
                lastPos.push_back(-INF);

                while (p != -1 && next[p][c] == q) {
                    next[p][c] = clone;
                    p = link[p];
                }
                link[q] = link[cur] = clone;
            }
        }
        last = cur;
    }

    // Returns the number of states (including root).
    int size() const {
        return (int)next.size();
    }
};

// ===================================================================
// 2) Basic queries on a SAM
// ===================================================================

// 2.1) Count the number of distinct substrings of the original string.
//      Input: sam (built)
//      Returns: long long number of distinct substrings.
//      Time: O(number of states) = O(n).
//      Formula: sum over all states (len[state] - len[link[state]]).
long long countDistinctSubstrings(const SuffixAutomaton& sam) {
    long long ans = 0;
    for (int i = 1; i < sam.size(); ++i) {
        ans += sam.len[i] - sam.len[sam.link[i]];
    }
    return ans;
}

// 2.2) Check if a pattern exists as a substring.
//      Input: sam, pattern p
//      Returns: true if p is a substring, false otherwise.
//      Time: O(|p|).
bool substringExists(const SuffixAutomaton& sam, const string& p) {
    int state = 0;
    for (char ch : p) {
        int c = ch - 'a';
        if (sam.next[state][c] == -1) return false;
        state = sam.next[state][c];
    }
    return true;
}

// 2.3) Get the occurrence count of a given pattern.
//      Requires pre‑computed occ vector.
//      Input: sam, occ, pattern p
//      Returns: int number of occurrences.
//      Time: O(|p|).
int getOccurrenceCount(const SuffixAutomaton& sam, const vector<int>& occ, const string& p) {
    int state = 0;
    for (char ch : p) {
        int c = ch - 'a';
        if (sam.next[state][c] == -1) return 0;
        state = sam.next[state][c];
    }
    return occ[state];
}

// 2.4) Compute occurrence counts for all states.
//      Input: sam
//      Returns: vector<int> occ where occ[state] = number of occurrences.
//      Time: O(number of states).
//      Note: Uses isClone to identify non‑clone states (initially 1).
vector<int> computeOccurrences(const SuffixAutomaton& sam) {
    int n = sam.size();
    vector<int> occ(n, 0);
    for (int i = 1; i < n; ++i) {
        if (!sam.isClone[i]) occ[i] = 1;
    }
    // Order states by length descending.
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b) {
        return sam.len[a] > sam.len[b];
    });
    for (int v : order) {
        if (sam.link[v] != -1) {
            occ[sam.link[v]] += occ[v];
        }
    }
    return occ;
}

// ===================================================================
// 3) Advanced queries on a SAM
// ===================================================================

// 3.1) Longest common substring between two strings.
//      Input: SAM built from s, second string t
//      Returns: int length of the longest common substring.
//      Time: O(|t|).
int longestCommonSubstring(const SuffixAutomaton& sam, const string& t) {
    int state = 0;
    int curLen = 0;
    int best = 0;
    for (char ch : t) {
        int c = ch - 'a';
        if (sam.next[state][c] != -1) {
            state = sam.next[state][c];
            curLen++;
        } else {
            while (state != -1 && sam.next[state][c] == -1) {
                state = sam.link[state];
            }
            if (state == -1) {
                state = 0;
                curLen = 0;
            } else {
                curLen = sam.len[state] + 1;
                state = sam.next[state][c];
            }
        }
        best = max(best, curLen);
    }
    return best;
}

// 3.2) Longest repeated substring (at least twice, can overlap).
//      Input: sam, occ (from computeOccurrences)
//      Returns: int length of the longest repeated substring.
//      Time: O(number of states).
int longestRepeatedSubstring(const SuffixAutomaton& sam, const vector<int>& occ) {
    int ans = 0;
    for (int i = 1; i < sam.size(); ++i) {
        if (occ[i] >= 2) {
            ans = max(ans, sam.len[i]);
        }
    }
    return ans;
}

// 3.3) Compute first and last occurrence positions for each state.
//      Input: sam
//      Returns: pair<vector<int>, vector<int>> (firstPos, lastPos)
//      Time: O(number of states).
//      Note: Initial positions are set for non‑clone states (len[state]-1),
//            then propagated along suffix links.
pair<vector<int>, vector<int>> computeFirstLastPos(const SuffixAutomaton& sam) {
    int n = sam.size();
    vector<int> firstPos(n, INF);
    vector<int> lastPos(n, -INF);
    for (int i = 1; i < n; ++i) {
        if (!sam.isClone[i]) {
            firstPos[i] = lastPos[i] = sam.len[i] - 1;
        }
    }
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b) {
        return sam.len[a] > sam.len[b];
    });
    for (int v : order) {
        if (sam.link[v] != -1) {
            int p = sam.link[v];
            firstPos[p] = min(firstPos[p], firstPos[v]);
            lastPos[p] = max(lastPos[p], lastPos[v]);
        }
    }
    return {firstPos, lastPos};
}

// 3.4) Longest repeated substring that does NOT overlap.
//      Input: sam, firstPos, lastPos (from computeFirstLastPos)
//      Returns: int length of the longest non‑overlapping repeated substring.
//      Time: O(number of states).
int longestNonOverlappingRepeated(const SuffixAutomaton& sam,
                                  const vector<int>& firstPos,
                                  const vector<int>& lastPos) {
    int ans = 0;
    for (int v = 1; v < sam.size(); ++v) {
        if (firstPos[v] + sam.len[v] <= lastPos[v]) {
            ans = max(ans, sam.len[v]);
        }
    }
    return ans;
}

// ===================================================================
// 4) Lexicographical queries on a SAM
// ===================================================================

// 4.1) Count the number of distinct substrings that start from each state.
//      Input: sam
//      Returns: vector<long long> dp where dp[state] = number of distinct
//               substrings (including the empty string) starting from state.
//      Time: O(number of states + transitions).
vector<long long> computeDP(const SuffixAutomaton& sam) {
    int n = sam.size();
    vector<long long> dp(n, 0);
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b) {
        return sam.len[a] > sam.len[b];
    });
    for (int v : order) {
        dp[v] = 1; // empty string
        for (int c = 0; c < sam.ALPHABET; ++c) {
            if (sam.next[v][c] != -1) {
                dp[v] += dp[sam.next[v][c]];
            }
        }
    }
    return dp;
}

// 4.2) Find the k‑th lexicographically smallest distinct substring (1‑indexed).
//      Input: sam, dp (from computeDP), k (1‑based)
//      Returns: string – the k‑th distinct substring.
//      Time: O(answer length * alphabet).
//      Note: dp includes the empty string; we skip it.
string kthSmallestSubstring(const SuffixAutomaton& sam, const vector<long long>& dp, long long k) {
    string ans;
    int state = 0;
    while (k > 0) {
        for (int c = 0; c < sam.ALPHABET; ++c) {
            if (sam.next[state][c] != -1) {
                int nxt = sam.next[state][c];
                if (dp[nxt] >= k) {
                    ans.push_back(char('a' + c));
                    state = nxt;
                    k--; // consumed the empty continuation of this branch
                    break;
                } else {
                    k -= dp[nxt];
                }
            }
        }
    }
    return ans;
}

// ===================================================================
// 5) Advanced tricks and patterns that appeared in ECPC/ACPC
// ===================================================================

// 5.1) Minimum lexicographic rotation of a string.
//      Input: s
//      Returns: string – the smallest rotation.
//      Time: O(n) using SAM on s+s.
//      Note: We greedily follow the smallest transition for n steps.
string minLexicographicRotation(const string& s) {
    string ss = s + s;
    SuffixAutomaton sam(ss);
    string ans;
    int state = 0;
    for (int i = 0; i < (int)s.size(); ++i) {
        for (int c = 0; c < sam.ALPHABET; ++c) {
            if (sam.next[state][c] != -1) {
                ans.push_back(char('a' + c));
                state = sam.next[state][c];
                break;
            }
        }
    }
    return ans;
}

// 5.2) Generalized Suffix Automaton (for multiple strings).
//      Input: vector of strings
//      Returns: SuffixAutomaton built from all strings.
//      Time: O(total length * alphabet).
//      Note: Resets `last` to 0 before each string.
SuffixAutomaton buildGeneralizedSAM(const vector<string>& strings) {
    SuffixAutomaton sam;
    sam.next.push_back({});
    for (auto &a : sam.next[0]) a = -1;
    sam.link.push_back(-1);
    sam.len.push_back(0);
    sam.isClone.push_back(false);
    sam.occ.push_back(0);
    sam.firstPos.push_back(INF);
    sam.lastPos.push_back(-INF);
    sam.last = 0;

    for (const string& s : strings) {
        sam.last = 0;
        for (char ch : s) {
            sam.extend(ch - 'a');
        }
    }
    return sam;
}

// 5.3) Count substrings that appear in at least K of the given strings.
//      Input: vector of strings, K
//      Returns: long long number of distinct substrings appearing in >= K strings.
//      Time: O(total length * alphabet + states * number_of_strings).
//      Note: Uses masks (sets) for each state and propagates along suffix links.
long long countSubstringsInAtLeastK(const vector<string>& strings, int K) {
    SuffixAutomaton sam = buildGeneralizedSAM(strings);
    int n_states = sam.size();
    int m = strings.size();

    vector<set<int>> masks(n_states);
    // For each string, mark the states visited by its prefixes.
    for (int idx = 0; idx < m; ++idx) {
        int state = 0;
        for (char ch : strings[idx]) {
            int c = ch - 'a';
            if (sam.next[state][c] == -1) break; // should not happen
            state = sam.next[state][c];
            masks[state].insert(idx);
        }
    }

    // Propagate masks along suffix links.
    vector<int> order(n_states);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b) {
        return sam.len[a] > sam.len[b];
    });
    for (int v : order) {
        if (sam.link[v] != -1) {
            int p = sam.link[v];
            // Union (small-to-large)
            if (masks[v].size() > masks[p].size()) swap(masks[v], masks[p]);
            for (int x : masks[v]) masks[p].insert(x);
        }
    }

    long long ans = 0;
    for (int i = 1; i < n_states; ++i) {
        if ((int)masks[i].size() >= K) {
            ans += sam.len[i] - sam.len[sam.link[i]];
        }
    }
    return ans;
}

// ===================================================================
// 6) Helper: topological order of states by length
// ===================================================================

// 6.1) Get states sorted by length (descending).
//      Input: sam
//      Returns: vector<int> states in decreasing order of len.
vector<int> getStatesByLengthDesc(const SuffixAutomaton& sam) {
    int n = sam.size();
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b) {
        return sam.len[a] > sam.len[b];
    });
    return order;
}

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

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

    string s = "ababa";
    SuffixAutomaton sam(s);

    // Count distinct substrings
    cout << "Distinct substrings: " << countDistinctSubstrings(sam) << '\n'; // 9

    // Check existence
    cout << "Contains 'aba'? " << substringExists(sam, "aba") << '\n'; // 1

    // Compute occurrences
    vector<int> occ = computeOccurrences(sam);
    cout << "Occurrences of 'ba': " << getOccurrenceCount(sam, occ, "ba") << '\n'; // 2

    // Longest common substring with another string
    string t = "bab";
    cout << "LCS length: " << longestCommonSubstring(sam, t) << '\n'; // 2

    // Longest repeated substring
    cout << "Longest repeated: " << longestRepeatedSubstring(sam, occ) << '\n'; // 3

    // Non‑overlapping repeated
    auto [firstPos, lastPos] = computeFirstLastPos(sam);
    cout << "Longest non‑overlapping repeated: " << longestNonOverlappingRepeated(sam, firstPos, lastPos) << '\n'; // e.g., 1

    // k‑th smallest substring
    vector<long long> dp = computeDP(sam);
    cout << "3rd smallest substring: " << kthSmallestSubstring(sam, dp, 3) << '\n'; // "ab"

    // Minimum rotation
    string rot = "bca";
    cout << "Min rotation of " << rot << ": " << minLexicographicRotation(rot) << '\n'; // "abc"

    // Count substrings in at least K strings
    vector<string> strs = {"ab", "bc", "abc"};
    cout << "Substrings appearing in at least 2 strings: " << countSubstringsInAtLeastK(strs, 2) << '\n'; // e.g., "b", "bc", "c"?

    return 0;
}