Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
input = sys.stdin.readline


class RollingHash:
    def __init__(self, string):
        self.n = len(string)
        self.BASE = 1234
        self.MOD = (1 << 61) - 1
        self.hash = [0] * (self.n + 1)
        self.pow = [1] * (self.n + 1)

        for i, char in enumerate(string):
            self.hash[i + 1] = (self.hash[i] + ord(char)) * self.BASE % self.MOD
            self.pow[i + 1] = (self.pow[i] * self.BASE) % self.MOD

    def get_hash(self, l, r):
        """string[l:r]のハッシュ値を返す。O(1)"""
        res = (self.hash[r] - self.hash[l] * self.pow[r - l]) % self.MOD
        return res


n = int(input())
s = [input()[:-1] for i in range(n)]


s.sort(key=len)
str_set = set()
cnt = 0

for string in s:
    string = string[::-1]
    n = len(string)
    rh = RollingHash(string)

    for r in range(1, n + 1):
        if rh.get_hash(0, r) in str_set:
            cnt += 1

    set_char = set()
    for r in range(1, n + 1)[::-1]:
        set_char.add(string[r - 1])
        for char in set_char:
            if char == string[r - 1]:
                continue
            h = (rh.hash[r - 1] + ord(char)) * rh.BASE % rh.MOD
            if h in str_set:
                cnt += 1
    str_set.add(rh.get_hash(0, n))

print(cnt)

### FIXED CODE ###

import sys
input = sys.stdin.readline


class RollingHash:
    def __init__(self, string):
        self.n = len(string)
        self.BASE = 1234
        self.MOD = (1 << 45) - 1
        self.hash = [0] * (self.n + 1)
        self.pow = [1] * (self.n + 1)

        for i, char in enumerate(string):
            self.hash[i + 1] = (self.hash[i] + ord(char)) * self.BASE % self.MOD
            self.pow[i + 1] = (self.pow[i] * self.BASE) % self.MOD

    def get_hash(self, l, r):
        """string[l:r]のハッシュ値を返す。O(1)"""
        res = (self.hash[r] - self.hash[l] * self.pow[r - l]) % self.MOD
        return res


n = int(input())
s = [input()[:-1] for i in range(n)]


s.sort(key=len)
str_set = set()
cnt = 0

for string in s:
    string = string[::-1]
    n = len(string)
    rh = RollingHash(string)

    for r in range(1, n + 1):
        if rh.get_hash(0, r) in str_set:
            cnt += 1

    set_char = set()
    for r in range(1, n + 1)[::-1]:
        set_char.add(string[r - 1])
        for char in set_char:
            if char == string[r - 1]:
                continue
            h = (rh.hash[r - 1] + ord(char)) * rh.BASE % rh.MOD
            if h in str_set:
                cnt += 1
    str_set.add(rh.get_hash(0, n))

print(cnt)
### BUGGY CODE ###

def solve():
    MOD = 10 ** 9 + 7
    N, M = map(int, input().split())
    A = set(list(map(int, input().split())))
    B = set(list(map(int, input().split())))
    
    row, columun = 0, 0
    ans = 1
    for i in range(N * M, 0, -1):
        in_A = i in A
        in_B = i in B
        if in_A and in_B:
            row += 1
            columun += 1
        elif in_A:
            row += 1
            ans *= columun
        elif in_B:
            columun += 1
            ans *= row
        else:
            ans *= row * columun - (N * M - i)
    print(ans % MOD)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

def solve():
    MOD = 10 ** 9 + 7
    N, M = map(int, input().split())
    A = set(map(int, input().split()))
    B = set(map(int, input().split()))
    
    row, columun = 0, 0
    ans = 1
    for i in range(N * M, 0, -1):
        in_A = i in A
        in_B = i in B
        if in_A and in_B:
            row += 1
            columun += 1
        elif in_A:
            row += 1
            ans *= columun
        elif in_B:
            columun += 1
            ans *= row
        else:
            ans *= row * columun - (N * M - i)
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    solve()
### BUGGY CODE ###

A, B, C, K = list(map(int, input().split()))

for i in range(K):
  if A == B and B == C:
    break
  next_A = B + C
  next_B = A + C
  next_C = A + B
  A = next_A
  B = next_B
  C = next_C
if abs(A - B) > 10**18:
  print('Unfair')
else:
  print(A - B)

### FIXED CODE ###

A, B, C, K = list(map(int, input().split()))

if abs(A - B) > 10**18:
  print('Unfair')
else:
  print((A -B)*(-1)**K)
### BUGGY CODE ###

n,a,b=map(int,input().split())
ans=0
if a==0:
    ans=0
elif b==0:
    ans=n 
else:
    while True:
        if n-a>=0:
            n-=a
            ans+=a
        else:
            ans+=n
            break
        n-=b
        if n<=0:
            break
print(ans)

### FIXED CODE ###

n,a,b=map(int,input().split())
ans=0
if a==0:
    ans=0
elif b==0:
    ans=n
else:
    ans=a*(int(n/(a+b)))
    n=n%(a+b)
    while True:
        if n==0:
            break
        if n-a<0:
            ans+=n
            break
        else:
            ans+=a
            break

print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
ls = list(map(int,input().split()))
for i in range(m):
    a,b = map(int,input().split())
    for j in range(a):
        ls.append(b)
ls.sort()
ls = ls[n*(-1):]
print(sum(ls))

### FIXED CODE ###

n,m = map(int,input().split())
ls = list(map(int,input().split()))
di = [list(map(int,input().split())) for _ in range(m)]
fi = []
for i,j in di:
    fi.append([j,i])
for k in ls:
    fi.append([k,1])
fi.sort(reverse=True)
ans = 0
cnt = 0
how = 0
while True:
    if how + fi[cnt][1] < n:
        how += fi[cnt][1]
        ans += fi[cnt][1]*fi[cnt][0]
    else:
        ans += (n-how)*fi[cnt][0]
        break
    cnt += 1
print(ans)
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
ans = 0
N = int(input())
for x in range(1,N+1):
    for y in range(1,N+1):
        for z in range(1,N+1):
            ans += gcd(x,y,z)
print(ans) 

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
ans = 0
N = int(input())
L = []
s_dict = {}
for x in range(1,N+1):
    for y in range(1,N+1):
       if(x == y):
           L.append(x)
           s_dict[(x,y)] = x
       elif(x % y == 0):
           L.append(y)
           s_dict[(x,y)] = y
       elif(y % x == 0):
           L.append(x)
           s_dict[(x,y)] = x
       else:
           tmp = gcd(x,y)
           L.append(tmp)
           s_dict[(x,y)] = tmp

for x in L:
    for z in range(1,N+1):
        ans += s_dict[(x,z)]
        
print(ans)
### BUGGY CODE ###

H,W = map(int,input().split())
S = []
for i in range(H):
    S.append(list(input()))
L = [[] for _ in range(H)]
R = [[] for _ in range(H)]
D = [[] for _ in range(H)]
U = [[] for _ in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            L[i].append(0)
        elif j == 0:
            L[i].append(1)
        else:
            L[i].append(L[i][-1] + 1)
for i in range(H):
    for j in range(-1,-W-1,-1):
        if S[i][j] == '#':
            R[i].insert(0,0)
        elif j == -1:
            R[i].append(1)
        else:
            R[i].insert(0,R[i][0] + 1)
for i in range(W):
    for j in range(H):
        if S[j][i] == '#':
            U[j].append(0)
        elif j == 0:
            U[j].append(1)
        else:
            U[j].append(U[j-1][-1] + 1)
for i in range(W):
    for j in range(-1,-H-1,-1):
        if S[j][i] == '#':
            D[j].append(0)
        elif j == -1:
            D[j].append(1)
        else:
            D[j].append(D[j+1][-1] + 1)
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            ans = max(ans,U[i][j]+D[i][j]+L[i][j]+R[i][j]-3)
print(ans)

### FIXED CODE ###

H,W = map(int,input().split())
S = []
for i in range(H):
    S.append(list(input()))
L = [[0 for _ in range(W)] for _ in range(H)]
R = [[0 for _ in range(W)] for _ in range(H)]
D = [[0 for _ in range(W)] for _ in range(H)]
U = [[0 for _ in range(W)] for _ in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        elif j == 0:
            L[i][j] += 1
        else:
            L[i][j] += L[i][j-1] + 1
for i in range(H):
    for j in range(-1,-W-1,-1):
        if S[i][j] == '#':
            continue
        elif j == -1:
            R[i][j] += 1
        else:
            R[i][j] += R[i][j+1] + 1
for i in range(W):
    for j in range(H):
        if S[j][i] == '#':
            continue
        elif j == 0:
            U[j][i] += 1
        else:
            U[j][i] += U[j-1][i] + 1
for i in range(W):
    for j in range(-1,-H-1,-1):
        if S[j][i] == '#':
            continue
        elif j == -1:
            D[j][i] += 1
        else:
            D[j][i] += D[j+1][i] + 1
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans,U[i][j]+D[i][j]+L[i][j]+R[i][j]-3)
print(ans)
### BUGGY CODE ###

a,b,k = map(int,input().split())
ans = []
for i in range(a,b+1):
    if i < a + k or b - k < i:
        ans.append(i)
for i in range(len(ans)):
    print(ans[i])

### FIXED CODE ###

a,b,k = map(int,input().split())
ans = []
for i in range(a,a+k):
    if i <= b:
        ans.append(i)
for i in range(b-k+1,b+1):
    if a < i and i not in ans:
        ans.append(i)
for i in range(len(ans)):
    print(ans[i])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]
def NSTR(n): return [input() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7


def bit_sum(n):
    wa = 0
    while n > 0:
        wa += n & 1
        n >>= 1
    return wa

def bit(n, k):
    return (n >> k) & 1

def main():
    N = INT()
    X = input()
    origX = X
    wa = X.count("1")
    x = 0
    for c in X:
        x <<= 1
        if c == "1":
            x |= 1
    X = x
    # wa+1
    px = X % (wa+1)
    if wa != 1:
        nx = X % (wa-1)
    else:
        nx = None

    # 1 ~ Nについて答えを出しておく NlogN
    table = [None]*(N+1)
    table[0] = 0
    table[1] = 1
    for i in range(1, N+1):
        table[i] = table[i % bit_sum(i)] + 1

    for i, c in enumerate(origX):
        count = 0
        x = X ^ (1 << N-i-1)
        if c == "1":
            if x == 0:
                print(0)
                continue
            x = (nx-pow(2, N-i-1, wa-1)) % (wa-1)
            print(table[x]+1)
        else:
            if x == 0:
                print(0)
                continue
            x = (px+pow(2, N-i-1, wa+1)) % (wa+1)
            print(table[x]+1)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]
def NSTR(n): return [input() for _ in range(n)]


import time


INF = float("inf")
MOD = 10**9 + 7


def bit_sum(n):
    wa = 0
    while n > 0:
        wa += n & 1
        n >>= 1
    return wa

def bit(n, k):
    return (n >> k) & 1

def main():
    start = time.time()
    N = INT()
    X = input()
    origX = X
    wa = X.count("1")
    x = 0
    px = 0
    nx = 0
    start = time.time()
    for c in X:
        x <<= 1
        px <<= 1
        nx <<= 1
        if c == "1":
            x |= 1
            px |= 1
            nx |= 1
        px %= (wa+1)
        if wa != 1:
            nx %= (wa-1)
        else:
            nx %= wa
    if wa == 1:
        nx = None
    # print(time.time()-start)
    # start = time.time()
    X = x
    table = [None]*(N+1)
    table[0] = 0
    table[1] = 1
    for i in range(1, N+1):
        table[i] = table[i % bit_sum(i)] + 1
    # print(time.time()-start)
    # start = time.time()

    for i, c in enumerate(origX):
        count = 0
        if c == "1":
            if wa == 1:
                print(0)
                continue
            x = (nx-pow(2, N-i-1, wa-1)) % (wa-1)
            print(table[x]+1)
        else:
            x = (px+pow(2, N-i-1, wa+1)) % (wa+1)
            print(table[x]+1)
    # print(time.time()-start)
    return


if __name__ == '__main__':
    main()
### BUGGY CODE ###

def gcd(a, b):
    if(a == 0):
        return b
    if(b == 0):
        return a

    if(a < b):
        a, b = b, a
    r = a % b
    while(r != 0):
        a, b = b, r
        r = a % b
    return b

def L(end_i, A):
    if(end_i == 0):
        return 0
    
    a = 0
    for i in range(end_i):
        a = gcd(a, A[i])
    return a


def R(start_i, A, N):
    if(start_i == N - 1):
        return 0

    a = 0
    for i in range(start_i + 1, N):
        a = gcd(a, A[i])
    return a


N = int(input())
A = list(map(int, input().split(' ')))

M = []
for i in range(N):
    M.append(gcd(L(i, A), R(i, A, N)))

print(max(M))

### FIXED CODE ###

def gcd(a, b):
    if(a == 0):
        return b
    if(b == 0):
        return a

    if(a < b):
        a, b = b, a
    r = a % b
    while(r != 0):
        a, b = b, r
        r = a % b
    return b

def L(end_i, A):
    if(end_i == 0):
        return 0
    
    a = 0
    for i in range(end_i):
        a = gcd(a, A[i])
    return a


def R(start_i, A, N):
    if(start_i == N - 1):
        return 0

    a = 0
    for i in range(start_i + 1, N):
        a = gcd(a, A[i])
    return a


N = int(input())
A = list(map(int, input().split(' ')))

left = [0] * N
right = [0] * N

for i in range(1, N):
    left[i] = gcd(left[i - 1], A[i - 1])
#print(left)

for i in reversed(range(0, N - 1)):
    right[i] = gcd(A[i + 1], right[i + 1])
#print(right)

M = []
for i in range(N):
    M.append(gcd(left[i], right[i]))
#print(M)

print(max(M))
### BUGGY CODE ###

count = int(input())
if count == 0:
  result = 0
else:
  nums_str = input().split()
  nums_int = []
  for strn in nums_str:
    nums_int.append(int(strn))
 
    result = 1

    if 0 in nums_int:
      result = 0
    else:
      for intn in nums_int:
        result *= intn
        if result > 10**18:
          result = -1
          break
    
print(result)

### FIXED CODE ###

def process():
  count = int(input())
  nums_str = input().split()
  nums_int = []
  for strn in nums_str:
    nums_int.append(int(strn))

  if 0 in nums_int:
    result = 0
    return result
  else:
    result = 1
    for intn in nums_int:
      result *= intn
      if result > 1000000000000000000:
        result = -1
        return result
    return result
    
print(process())
### BUGGY CODE ###

import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(100000)

def main(n,p,dx,dy):
    ans = 0
    def dfs(x,y,dx,dy,grid,dis):
        z = dis[y][x] + grid[y][x]
        for i in range(4):
            next_x = x+dx[i]
            next_y = y+dy[i]
            if dis[next_y][next_x] > z:
                dis[next_y][next_x] = z
                dfs(next_x,next_y,dx,dy,grid,dis)
    grid = np.ones((n+1,n+1),np.int32)
    dis = np.zeros((n+2,n+2),np.int32)
    for i in range(1,n+1):
        for j in range(1,n+1):
            dis[i][j] = min(i,n-i+1,j,n-j+1)-1
    for i in range(n**2):
        pos = p[i]
        x = (pos-1)%n+1
        y = (pos-1)//n+1
        ans += dis[y][x]
        grid[y][x] = 0
        dfs(x,y,dx,dy,grid,dis)
    return ans

n = int(readline())
p = np.array(readline().split(),np.int32)
dx = np.array([0,1,0,-1])
dy = np.array([1,0,-1,0])
print(main(n,p,dx,dy))

### FIXED CODE ###

import sys
import numpy as np
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(i4,i4[:])',cache=True)
def main(n,p):
    ans = 0
    w = n+2
    grid = np.ones((w,w),np.int32)
    dis = np.zeros((w,w),np.int32)
    for i in range(1,n+1):
        for j in range(1,n+1):
            dis[i][j] = min(i,n-i+1,j,n-j+1)-1
    grid = grid.ravel()
    dis = dis.ravel()
    stack = np.empty_like(grid)
    for pos in p:
        pos -= 1
        x = pos % n + 1
        y = pos // n + 1
        v = y*w+x
        ans += dis[v]
        grid[v] = 0
        k = min(dis[v-1],dis[v+1],dis[v+w],dis[v-w])
        cur = 0
        stack[0] = v
        while cur >= 0:
            v = stack[cur]
            cur -= 1
            for dx in (-1,1,w,-w):
                next_v = v + dx
                k = dis[v]+grid[v]
                if dis[next_v] > k:
                    dis[next_v] = k
                    cur += 1
                    stack[cur] = next_v
    return ans

n = int(readline())
p = np.array(readline().split(),np.int32)
print(main(n,p))
### BUGGY CODE ###

"""
https://atcoder.jp/contests/tokiomarine2020/submissions/14229099
"""
N,K = map(int,input().split())
A = list(map(int,input().split()))
 
def update(A):
    b = [0]*N
 
    for i,a in enumerate(A):
        l = max(0,i-a)
        r = min(N-1,i+a)
 
        b[l] += 1
        if r+1 < N:
            b[r+1] -= 1
    
    res = []
    s = 0
    for i in b:
        s += i
        res.append(s)
    return res
 
for _ in range(min(K,50)):
    A = update(A)
 
print(*A)

### FIXED CODE ###

"""
https://atcoder.jp/contests/tokiomarine2020/submissions/14229099
"""
N,K = map(int,input().split())
A = list(map(int,input().split()))

def update(A):
    b = [0]*N

    for i,a in enumerate(A):
        l = max(0,i-a)
        r = min(N-1,i+a)

        b[l] += 1
        if r+1 < N:
            b[r+1] -= 1
    
    res = []
    s = 0
    for i in b:
        s += i
        res.append(s)
    return res

for _ in range(min(K,75)):
    A = update(A)

print(*A)
### BUGGY CODE ###

from fractions import gcd
MOD=(10**9)+7
n=int(input())
a=list(map(int,input().split()))
a_lcm=a[0]

for ai in a:
    a_lcm=(a_lcm*ai) // gcd(a_lcm, ai)

b=[]
for ai in a:
    b.append(a_lcm//ai)
sum_b=sum(b)
print(sum_b%MOD)


### FIXED CODE ###

from fractions import gcd
MOD=(10**9)+7
n=int(input())
a=list(map(int,input().split()))
a_lcm=a[-1]

for ai in a:
    a_lcm=(a_lcm*ai) // gcd(a_lcm, ai)

sum_b=0
for ai in a:
    bi=a_lcm//ai
    sum_b+=bi
print(sum_b%MOD)
### BUGGY CODE ###

X=int(input())

for i in range(31622):
    for j in range(31622):
        j *= -1
        if X == (i**5-j**5):
            print(i, j)
            exit()


### FIXED CODE ###

X=int(input())

for i in range(-200,200):
    for j in range(-200,200):
        j *= -1
        if X == (i**5-j**5):
            print(i, j)
            exit()
### BUGGY CODE ###

import bisect
N = int(input())
nums = [int(input()) for _ in range(N)]
# i<jで、 AiとAjが同じ色で塗られている場合、Ai < Ajが成り立つ.
# その際に、色の最小数をだす。
LIS = [nums[0]]
count = 0
for index, num in enumerate(nums):
    if index == 0:
        continue
    insert_index = bisect.bisect_left(LIS, num)
    if insert_index == 0:
        LIS.insert(insert_index, num)
    else:
        LIS[insert_index - 1] = num
print(len(LIS))


### FIXED CODE ###

import bisect
from collections import deque
N = int(input())
nums = [int(input()) for _ in range(N)]
# i<jで、 AiとAjが同じ色で塗られている場合、Ai < Ajが成り立つ.
# その際に、色の最小数をだす。
LIS = deque([nums[0]])
count = 0
for index, num in enumerate(nums):
    if index == 0:
        continue
    if num <= LIS[0]:
        LIS.appendleft(num)
    else:
        insert_index = bisect.bisect_left(LIS, num)
        LIS[insert_index - 1] = num
print(len(LIS))
### BUGGY CODE ###

n = int(input())
r =[]
for i in range(n):
    r.append(int(input()))

max_value = -10**9
for i in range(n):
    for j in range(i+1,n):
        rji = r[j] - r[i]
        if rji  > max_value:
            max_value = rji
print(max_value)


### FIXED CODE ###

n = int(input())
max_value = -10**9
min_value = int(input())
for i in range(1,n):
    r = int(input())
    max_value = max(max_value,r-min_value)
    min_value = min(min_value, r)

print(max_value)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
for i in range(N):
    B = A.copy()
    del B[i]
    print(max(B))
    del B

### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
B = sorted(A,reverse=True)
for i in range(N):
    if A[i] == B[0]:
        print(B[1])
    else:
        print(B[0])
### BUGGY CODE ###

S = list(input())
Q = int(input())
R = True

for i in range(Q):
  q = list(input().split())
  if int(q[0]) == 1:
    R = not R
  else:
    if int(q[1]) == 1:
      if R:
        S.insert(0, q[2])
        
      else:
        S.append(q[2])
    else:
      if R:
        S.append(q[2])
      else:
        S.insert(0, q[2])

if R:
  print(''.join(S))
else:
  print(''.join(S[::-1]))

### FIXED CODE ###

S = list(input())
S_r = []
Q = int(input())
R = True

for i in range(Q):
  q = list(input().split())
  if int(q[0]) == 1:
    R = not R
  else:
    if int(q[1]) == 1:
      if R:
        S_r.append(q[2])
      else:
        S.append(q[2])
    else:
      if R:
        S.append(q[2])
      else:
        S_r.append(q[2])

if not S_r:
  if R:
    print(''.join(S))
  else:
    print(''.join(S[::-1]))
else:
  if R:
    print(''.join(S_r[::-1]), end="")
    print(''.join(S))
  else:
    print(''.join(S[::-1]), end="")
    print(''.join(S_r))
### BUGGY CODE ###

from collections import deque


A = input()
N = len(A)
a = ord('a')

edge = [[N + 1] * 26 for _ in range(N + 1)]
for i in range(N - 1, -1, -1):
    for j in range(26):
        edge[i][j] = edge[i + 1][j]
    c = ord(A[i]) - a
    edge[i][c] = i + 1


recon = [None] * (N + 2)  # DP復元用。(直前の頂点, 文字)を格納する。
q = deque()
q.append(0)  # 頂点
while q:
    i = q.popleft()
    if i == N + 1:  # 頂点N+1に到達したら処理終了
        break
    for j in range(26):
        ni = edge[i][j]
        if recon[ni] is None:  # その頂点に最短で到達した場合のみ次の処理を継続
            recon[ni] = (i, chr(a + j))
            q.append(ni)

i = N + 1
ans = []
while i > 0:
    pi, c = recon[i]
    ans.append(c)
    i = pi

print(''.join(reversed(ans)))


### FIXED CODE ###

def main():
    # import sys
    # readline = sys.stdin.readline
    # readlines = sys.stdin.readlines
    
    A = input()
    N = len(A)
    a = ord('a')

    INF = N
    na = [[INF] * 26 for _ in range(N + 1)]
    for i in range(N - 1, -1, -1):
        c = ord(A[i]) - a
        for j in range(26):
            na[i][j] = na[i + 1][j]
        na[i][c] = i

    dp = [INF] * (N + 1)
    dp[N] = 1
    recon = [None] * (N + 1)
    for i in range(N - 1, -1, -1):
        for j in range(26):
            ni = na[i][j]
            if ni == N:
                if dp[i] > 1:
                    dp[i] = 1
                    recon[i] = (chr(a + j), N)
            elif dp[i] > dp[ni + 1] + 1:
                dp[i] = dp[ni + 1] + 1
                recon[i] = (chr(a + j), ni + 1)

    # k =
    # for j in range(26):
    #     ni = na[0][j]
    #     if dp[i] > dp[ni] + 1:

    i = 0
    ans = []
    while i < N:
        c, ni = recon[i]
        ans.append(c)
        i = ni

    print(''.join(ans))


if __name__ == "__main__":
    main()
### BUGGY CODE ###

flg_stop = False
count = 1

K = int(input())

if K % 2 == 0:
    count = -1
    flg_stop = True
else:
    if K % 7 == 0:
        L = 9 * K / 7
    else:
        L = 9 * K

    mod_ = 1
    while not(flg_stop):
        mod_ = (mod_ * 10) % L
        if mod_ == 1:
            flg_stop = True
            continue
        count += 1

print(count)

### FIXED CODE ###

k = int(input())
i = 1
a = 7
a = a % k
while a != 0:
  i += 1
  a = (10*a + 7) % k
  if i == 10**6:
    i = -1
    break
 
print(i)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

n = []
a = []

i = 0
while True:
    n.append(int(input()))
    if n[i] == 0:
        break
    for j in range(0,n[i]):
        a.append(int(input()))
    i += 1

for i in range(0,len(n)):
    sumMax = 0
    for j in range(sum(n[0:i-1 if i != 0 else 0]),sum(n[0:i])):
        for k in range(j,sum(n[0:i])+1):
            if j==k:
                continue
            sumMax = max(sumMax,sum(a[j:k]))
    print(sumMax)

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

while True:
    n = int(input())
    if n == 0:
        break
    a = []
    for i in range(0,n):
        a.append(int(input()))
    sumMax = -100000
    for i in range(0,n):
        tmp = 0
        for j in range(i,n):
            tmp += a[j]
            sumMax = max(sumMax,tmp)
    print(sumMax)