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

// ===================================================================
// This file contains a collection of functions based on Manacher's
// algorithm for palindromic substrings. 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
// ===================================================================

// ===================================================================
// TERMINOLOGY EXPLANATION:
//   - d1[i] : number of odd-length palindromes with center at index i.
//             It includes the single character itself.
//             The maximum palindrome radius (in characters) is d1[i],
//             and the length of that longest palindrome is 2*d1[i] - 1.
//             For example, d1[i] = 3 means the palindrome of length 5
//             centered at i exists.
//   - d2[i] : number of even-length palindromes centered between
//             index i-1 and index i. (For i from 0 to n-1, we consider
//             the gap before index i.) If d2[i] > 0, there is at least
//             one even palindrome with that center. The maximum radius
//             (in characters) is d2[i], and length is 2*d2[i].
//             Example: d2[2] = 2 means the palindrome of length 4
//             centered between indices 1 and 2 exists.
// ===================================================================

// ===================================================================
// 1) Core Manacher algorithm
//    Computes the two radius arrays d1 and d2 for a given string.
// ===================================================================

// 1.1) manacher
// ============================================================================
// PURPOSE:
//   Computes the Manacher arrays for the input string. These arrays allow
//   O(1) checks for palindromic substrings and are the basis for all other
//   functions in this file.
//
// INPUT:
//   s : a string (can contain any characters, including spaces if handled).
//
// OUTPUT:
//   Returns a pair of vectors of integers:
//     - first  : d1, size n (n = s.length())
//     - second : d2, size n
//
// TIME COMPLEXITY:
//   O(n) where n = s.length().
//
// CONSTRAINTS / PRECONDITIONS:
//   - The string can be empty (then both vectors are empty).
//   - Works for any character type (char, wchar_t, etc.) as long as
//     equality is defined.
//
// NOTES:
//   - This function is used internally by most other functions.
//   - The arrays d1 and d2 are explained in the terminology section above.
// ============================================================================
pair<vector<int>, vector<int>> manacher(const string& s) {
    int n = (int)s.size();
    vector<int> d1(n), d2(n);

    // Odd-length palindromes (d1)
    for (int i = 0, l = 0, r = -1; i < n; i++) {
        int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
        while (i - k >= 0 && i + k < n && s[i - k] == s[i + k]) {
            k++;
        }
        d1[i] = k--;
        if (i + k > r) {
            l = i - k;
            r = i + k;
        }
    }

    // Even-length palindromes (d2)
    for (int i = 0, l = 0, r = -1; i < n; i++) {
        int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
        while (i - k - 1 >= 0 && i + k < n && s[i - k - 1] == s[i + k]) {
            k++;
        }
        d2[i] = k--;
        if (i + k > r) {
            l = i - k - 1;
            r = i + k;
        }
    }

    return {d1, d2};
}

// ===================================================================
// 2) Basic Queries using Manacher arrays
//    These functions rely on precomputed d1 and d2.
// ===================================================================

// 2.1) isPalSubstring
// ============================================================================
// PURPOSE:
//   Checks whether the substring s[l..r] (inclusive) is a palindrome.
//
// INPUT:
//   l, r : 0-based indices (l <= r).
//   d1, d2 : Manacher arrays (obtained from manacher(s)).
//
// OUTPUT:
//   Returns true if s[l..r] is a palindrome, false otherwise.
//
// TIME COMPLEXITY:
//   O(1)
//
// CONSTRAINTS / PRECONDITIONS:
//   - l and r must be valid indices (0 <= l <= r < n).
//   - d1 and d2 must correspond to the same string s.
//
// NOTES:
//   - This function does not need the original string, only the Manacher arrays.
//   - For odd length, it checks the required radius at the center.
//   - For even length, it checks the required radius at the gap center.
// ============================================================================
bool isPalSubstring(int l, int r, const vector<int>& d1, const vector<int>& d2) {
    int len = r - l + 1;
    if (len <= 0) return false;
    if (len % 2 == 1) {
        int center = (l + r) / 2;
        int radius = (len + 1) / 2;
        return d1[center] >= radius;
    } else {
        // center is between index c-1 and c, where c = (l+r)/2 + 1
        int center = (l + r) / 2 + 1;
        int radius = len / 2;
        return d2[center] >= radius;
    }
}

// ===================================================================
// 3) Longest Palindrome Substring
//    Finds the longest palindromic substring (by length or the actual string).
// ===================================================================

// 3.1) longestPalSubstringLength
// ============================================================================
// PURPOSE:
//   Returns the length of the longest palindromic substring of the given string.
//
// INPUT:
//   s : the input string.
//
// OUTPUT:
//   An integer: the maximum length.
//
// TIME COMPLEXITY:
//   O(n) because it calls manacher(s) once.
//
// CONSTRAINTS / PRECONDITIONS:
//   - Works for any string length (including empty, returns 0).
//
// NOTES:
//   - If you also need the substring itself, use longestPalSubstring().
// ============================================================================
int longestPalSubstringLength(const string& s) {
    int n = (int)s.size();
    if (n == 0) return 0;
    auto [d1, d2] = manacher(s);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, 2 * d1[i] - 1);
        if (d2[i] > 0) ans = max(ans, 2 * d2[i]);
    }
    return ans;
}

// 3.2) longestPalSubstring
// ============================================================================
// PURPOSE:
//   Returns the actual longest palindromic substring itself.
//   If multiple have the same maximum length, the first one (by start index)
//   is returned.
//
// INPUT:
//   s : the input string.
//
// OUTPUT:
//   A string: the longest palindromic substring.
//
// TIME COMPLEXITY:
//   O(n) (manacher + one pass).
//
// CONSTRAINTS / PRECONDITIONS:
//   - If the string is empty, returns an empty string.
//
// NOTES:
//   - The function finds the start index and length of the longest palindrome.
// ============================================================================
string longestPalSubstring(const string& s) {
    int n = (int)s.size();
    if (n == 0) return "";
    auto [d1, d2] = manacher(s);
    int bestLen = 0, bestStart = 0;

    for (int i = 0; i < n; i++) {
        // odd length
        int len = 2 * d1[i] - 1;
        if (len > bestLen) {
            bestLen = len;
            bestStart = i - d1[i] + 1;
        }
        // even length
        if (d2[i] > 0) {
            len = 2 * d2[i];
            if (len > bestLen) {
                bestLen = len;
                bestStart = i - d2[i];
            }
        }
    }
    return s.substr(bestStart, bestLen);
}

// ===================================================================
// 4) Counting Palindromic Substrings
//    Returns the total number of palindromic substrings (including single chars).
// ===================================================================

// 4.1) countPalSubstrings
// ============================================================================
// PURPOSE:
//   Counts all palindromic substrings (contiguous) in the given string.
//
// INPUT:
//   s : the input string.
//
// OUTPUT:
//   A long long integer: the total number of palindromic substrings.
//
// TIME COMPLEXITY:
//   O(n) (manacher).
//
// CONSTRAINTS / PRECONDITIONS:
//   - Works for any string; for empty returns 0.
//
// NOTES:
//   - The number can be large (up to n*(n+1)/2), so long long is used.
//   - Single characters are always palindromes.
// ============================================================================
long long countPalSubstrings(const string& s) {
    int n = (int)s.size();
    if (n == 0) return 0;
    auto [d1, d2] = manacher(s);
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        ans += d1[i];          // each d1[i] is number of odd palindromes centered at i
        ans += d2[i];          // each d2[i] is number of even palindromes centered at i
    }
    return ans;
}

// 4.2) countOddPalSubstrings
// ============================================================================
// PURPOSE:
//   Counts only the odd-length palindromic substrings.
//
// INPUT:
//   s : input string.
//
// OUTPUT:
//   long long count.
//
// TIME COMPLEXITY:
//   O(n).
//
// NOTES:
//   - Equivalent to sum of d1[i].
// ============================================================================
long long countOddPalSubstrings(const string& s) {
    int n = (int)s.size();
    if (n == 0) return 0;
    auto [d1, d2] = manacher(s);
    long long ans = 0;
    for (int x : d1) ans += x;
    return ans;
}

// 4.3) countEvenPalSubstrings
// ============================================================================
// PURPOSE:
//   Counts only the even-length palindromic substrings.
//
// INPUT:
//   s : input string.
//
// OUTPUT:
//   long long count.
//
// TIME COMPLEXITY:
//   O(n).
//
// NOTES:
//   - Equivalent to sum of d2[i].
// ============================================================================
long long countEvenPalSubstrings(const string& s) {
    int n = (int)s.size();
    if (n == 0) return 0;
    auto [d1, d2] = manacher(s);
    long long ans = 0;
    for (int x : d2) ans += x;
    return ans;
}

// ===================================================================
// 5) Longest Palindrome Ending at Each Index (and Starting at Each Index)
//    These are useful for problems that split the string into parts.
// ===================================================================

// 5.1) longestPalEndingAt
// ============================================================================
// PURPOSE:
//   For each index i, computes the length of the longest palindromic substring
//   that ends at i.
//
// INPUT:
//   s : input string.
//
// OUTPUT:
//   A vector<int> of size n, where res[i] = length of the longest palindrome
//   ending at i. The answer is at least 1 (the character itself).
//
// TIME COMPLEXITY:
//   O(n) (Manacher + O(n) pass with a monotonic deque).
//
// CONSTRAINTS / PRECONDITIONS:
//   - If the string is empty, returns an empty vector.
//
// NOTES:
//   - This is often used when you need to split the string into two palindromes.
//   - The algorithm uses the Manacher radii and a sliding window technique.
//   - The implementation below correctly handles centers with equal right ends.
// ============================================================================
vector<int> longestPalEndingAt(const string& s) {
    int n = (int)s.size();
    if (n == 0) return {};
    auto [d1, d2] = manacher(s);
    vector<int> ends(n, 1); // at least the single character

    // ---- Odd palindromes ----
    deque<int> q; // stores indices of centers, with strictly increasing right end
    for (int j = 0; j < n; ++j) {
        int i = j;
        int end = i + d1[i] - 1;
        // Add center only if its right end is strictly greater than the last one.
        // This keeps centers with increasing right ends; the leftmost center always gives the longest length.
        if (q.empty() || end > q.back() + d1[q.back()] - 1) {
            q.push_back(i);
        }
        // Remove centers that can no longer reach position j
        while (!q.empty() && q.front() + d1[q.front()] - 1 < j) {
            q.pop_front();
        }
        if (!q.empty()) {
            int best_i = q.front();
            ends[j] = max(ends[j], 2 * j - 2 * best_i + 1);
        }
    }

    // ---- Even palindromes ----
    q.clear();
    for (int j = 0; j < n; ++j) {
        if (d2[j] > 0) {
            int i = j;
            int end = i + d2[i] - 1;
            if (q.empty() || end > q.back() + d2[q.back()] - 1) {
                q.push_back(i);
            }
        }
        while (!q.empty() && q.front() + d2[q.front()] - 1 < j) {
            q.pop_front();
        }
        if (!q.empty()) {
            int best_i = q.front();
            ends[j] = max(ends[j], 2 * j - 2 * best_i + 2);
        }
    }

    return ends;
}

// 5.2) longestPalStartingAt
// ============================================================================
// PURPOSE:
//   For each index i, computes the length of the longest palindromic substring
//   that starts at i.
//
// INPUT:
//   s : input string.
//
// OUTPUT:
//   A vector<int> of size n, where res[i] = length of the longest palindrome
//   starting at i.
//
// TIME COMPLEXITY:
//   O(n) (calls longestPalEndingAt on reversed string).
//
// CONSTRAINTS / PRECONDITIONS:
//   - Empty string returns empty vector.
//
// NOTES:
//   - A palindrome starting at i in s corresponds to a palindrome ending at
//     position (n-1-i) in the reversed string. So this function uses that fact.
// ============================================================================
vector<int> longestPalStartingAt(const string& s) {
    int n = (int)s.size();
    if (n == 0) return {};
    string rs = s;
    reverse(rs.begin(), rs.end());
    vector<int> endsRev = longestPalEndingAt(rs);
    vector<int> starts(n);
    for (int i = 0; i < n; ++i) {
        starts[i] = endsRev[n - 1 - i];
    }
    return starts;
}

// ===================================================================
// 6) Advanced Trick: Maximum Sum of Two Non-overlapping Palindromes
//    This appeared in ECPC/ACPC problems.
// ===================================================================

// 6.1) maxSumTwoPalindromes
// ============================================================================
// PURPOSE:
//   Finds the maximum possible sum of lengths of two non-overlapping
//   palindromic substrings. The two palindromes must not overlap and must
//   be non-empty. They can be adjacent.
//
// INPUT:
//   s : input string.
//
// OUTPUT:
//   An integer: the maximum sum. Returns 0 if no such split possible
//   (e.g., string length < 2).
//
// TIME COMPLEXITY:
//   O(n) (computes ending and starting arrays, then prefix/suffix maxima).
//
// CONSTRAINTS / PRECONDITIONS:
//   - Works for any string; for n<2 returns 0.
//
// NOTES:
//   - The idea: for each split position i (between i and i+1), we take the
//     longest palindrome ending at or before i (prefix) and the longest
//     palindrome starting at i+1 or later (suffix). Their sum is considered.
//     We precompute prefix maxima of ends and suffix maxima of starts.
// ============================================================================
int maxSumTwoPalindromes(const string& s) {
    int n = (int)s.size();
    if (n < 2) return 0;

    vector<int> endLen = longestPalEndingAt(s);
    vector<int> startLen = longestPalStartingAt(s);

    vector<int> pref(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        pref[i + 1] = max(pref[i], endLen[i]);
    }

    vector<int> suff(n + 1, 0);
    for (int i = n - 1; i >= 0; --i) {
        suff[i] = max(suff[i + 1], startLen[i]);
    }

    int ans = 0;
    for (int i = 0; i < n - 1; ++i) {
        // first palindrome ends at or before i, second starts at i+1 or later
        ans = max(ans, pref[i + 1] + suff[i + 1]);
    }
    return ans;
}

// ===================================================================
// 7) Extra: Quick check if a string can be made palindrome by removing
//    at most one character.
//    A two-pointer solution is simpler and O(n); we implement it here.
// ===================================================================

// 7.1) canBePalindromeAfterOneDeletion
// ============================================================================
// PURPOSE:
//   Checks if the string can become a palindrome by deleting at most one
//   character.
//
// INPUT:
//   s : input string.
//
// OUTPUT:
//   Returns true if we can delete at most one character to get a palindrome.
//
// TIME COMPLEXITY:
//   O(n) (two-pointer).
//
// CONSTRAINTS / PRECONDITIONS:
//   - Works for any string; empty string is trivially true.
//
// NOTES:
//   - This function does NOT use Manacher; it uses a simpler two-pointer
//     approach which is more direct for this specific problem.
// ============================================================================
bool canBePalindromeAfterOneDeletion(const string& s) {
    int n = (int)s.size();
    int l = 0, r = n - 1;
    while (l < r && s[l] == s[r]) {
        ++l;
        --r;
    }
    if (l >= r) return true; // already palindrome

    // Try deleting s[l] and check if s[l+1..r] is palindrome
    int l1 = l + 1, r1 = r;
    bool ok1 = true;
    while (l1 < r1 && s[l1] == s[r1]) {
        ++l1;
        --r1;
    }
    if (l1 >= r1) return true;

    // Try deleting s[r] and check if s[l..r-1] is palindrome
    int l2 = l, r2 = r - 1;
    bool ok2 = true;
    while (l2 < r2 && s[l2] == s[r2]) {
        ++l2;
        --r2;
    }
    if (l2 >= r2) return true;

    return false;
}

// ===================================================================
// main() – Example usage (you can ignore or modify this part)
// ===================================================================
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s = "abac";
    cout << "String: " << s << "\n";

    // Manacher
    auto [d1, d2] = manacher(s);
    cout << "d1: ";
    for (int x : d1) cout << x << " ";
    cout << "\nd2: ";
    for (int x : d2) cout << x << " ";
    cout << "\n";

    // Longest palindrome substring
    cout << "Longest palindrome substring: " << longestPalSubstring(s) << "\n";
    cout << "Length: " << longestPalSubstringLength(s) << "\n";

    // Count palindromes
    cout << "Total palindromic substrings: " << countPalSubstrings(s) << "\n";
    cout << "Odd palindromes: " << countOddPalSubstrings(s) << "\n";
    cout << "Even palindromes: " << countEvenPalSubstrings(s) << "\n";

    // Check if substring [1,3] is palindrome (s[1..3] = "bac" -> false)
    cout << "Is substring [1,3] palindrome? " << (isPalSubstring(1, 3, d1, d2) ? "Yes" : "No") << "\n";

    // Longest palindrome ending at each index
    vector<int> ends = longestPalEndingAt(s);
    cout << "Longest palindrome ending at each index: ";
    for (int x : ends) cout << x << " ";
    cout << "\n";

    // Longest palindrome starting at each index
    vector<int> starts = longestPalStartingAt(s);
    cout << "Longest palindrome starting at each index: ";
    for (int x : starts) cout << x << " ";
    cout << "\n";

    // Max sum of two non-overlapping palindromes
    cout << "Max sum of two non-overlapping palindromes: " << maxSumTwoPalindromes(s) << "\n";

    // Check if can be palindrome after one deletion
    cout << "Can be palindrome after one deletion? " << (canBePalindromeAfterOneDeletion(s) ? "Yes" : "No") << "\n";

    return 0;
}