
# iを中心とする回文の半径を記録した配列
# 間に#を挟めば偶数長の回文へも使える
def manacher(s):
    n = len(s)
    a = [0] * n
    i = 0
    j = 0
    while i < n:
        while i - j >= 0 and i + j < n and s[i - j] == s[i + j]:
            j += 1
        a[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i - k >= 0 and i + k < n and k + a[i - k] < j:
            a[i + k] = a[i - k]
            k += 1
        i += k
        j -= k
    return a