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

n,s,*a=map(int,open(0).read().split());d=[0]*-~s;m=998244353;v=pow(2,m-2,m);d[0]=pow(2,n,m)
for i in a:
  for j in range(s,i-1,-1):d[j]+=(d[j-i]*v)%m
print(d[s]%m)

### FIXED CODE ###

n,s=map(int,input().split())
dp=[0]*(s+1)
mod=998244353
inv=pow(2,mod-2,mod)
dp[0]=pow(2,n,mod)
for i in list(map(int,input().split())):
  for j in range(s,i-1,-1):
    dp[j]=(dp[j]+dp[j-i]*inv)%mod
print(dp[s])
### BUGGY CODE ###

def cnt(a, b):
    cnt = 0
    while a%b != 0:
        a += 1
        cnt += 1
    return cnt


n = int(input())
al = []
bl = []

for _ in range(n):
    a, b = map(int, input().split())
    al.append(a)
    bl.append(b)

ans = 0
for i in range(n-1, -1, -1):
    ans += cnt(al[i]+ans, bl[i])
    # ans += bl[i] % (al[i]+ans)

print(ans)




### FIXED CODE ###

n = int(input())
a = [0]*n
b = [0]*n

for i in range(n):
    a[i], b[i] = map(int, input().split())

ans = 0
for i in range(n-1, -1, -1):
    if (a[i]+ans) % b[i] != 0:
        ans += b[i] - (a[i]+ans) % b[i]

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

N, H = map(int, input().split())
a, b = [0] * N, [0] * N
for i in range(N):
    a[i], b[i] = map(int, input().split())
a.sort(reverse=True)
b.sort(reverse=True)
ans = 0
while len(b) > 0 and b[0] > a[0]:
    H -= b[0]
    b = b[1:]
    ans += 1
ans += (H + a[0] - 1) // a[0]
print(ans)


### FIXED CODE ###

N, H = map(int, input().split())
a, b = [0] * N, [0] * N
for i in range(N):
    a[i], b[i] = map(int, input().split())
ma = max(a)
b.sort(reverse=True)
ans = 0
index = 0
while H > 0 and len(b) > index and b[index] > ma:
    H -= b[index]
    index += 1
    ans += 1
if H > 0:
    ans += (H + ma - 1) // ma
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

S = list(input())
del S[-1]
Surpus = [-1 for i in range(2019)]
Surpus[0] = 0

T = 0
for count, i in enumerate(S):
    T += int(S[-1 - count]) * (10 ** count)
    Surpus[T % 2019] += 1

ans = 0
for i in Surpus:
    ans += int(i * (i + 1) / 2)

print(ans)

### FIXED CODE ###

S = input()[::-1]
Surpus = [0] * 2019
Surpus[0] = 1

sum = 0
x = 1
for i in S:
    sum += int(i) * x
    Surpus[sum % 2019] += 1
    x *= 10
    x %= 2019

ans = 0
for i in Surpus:
    ans += i * (i - 1) // 2

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

prime=[]
n=10**5
is_prime=True
for i in range(2,n+1):
    is_prime=True
    for p in prime:
        if i%p==0:
            is_prime=False
            break
    if is_prime:
        prime.append(i)
q=int(input())
query=[[int(i) for i in input().split()] for j in range(q)]
for qu in query:
    cnt=0
    for j in range(qu[0], qu[1]+1, 2):
        if (j in prime) and (((j+1)//2) in prime):
            cnt+=1
    print(cnt)        


### FIXED CODE ###

def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

num = 10**5+10
Q = int(input())
prime_numbers = primes(num)
prime_set = set(prime_numbers)
prime_count = [0]*(num+1)
for pi in prime_numbers:
    if (pi+1)//2 in prime_set:
        prime_count[pi]+=1
for i in range(num):
    prime_count[i+1]+=prime_count[i]
for i in range(Q):
    l, r = map(int, input().split())
    print(prime_count[r]-prime_count[l-1])
### BUGGY CODE ###

S=input()
s=int(S)

c=[0]*(len(S)+1)
c[0]=0
for i in range(len(S)):
  c[i+1]=(c[i]+int(S[-1-i])*10**i)%2019

#print(c)  
d=[0]*2019
m=0
for i in range(2019):
  d[i]=c.count(i)
  m+=d[i]*(d[i]-1)//2
#print(d)
print(m)

### FIXED CODE ###

S=input()
s=int(S)
mod=2019
c=[0]*(len(S)+1)
d=[0]*2019


c[0]=0
d[0]=1
for i in range(len(S)):
  c[i+1]=(c[i]+int(S[-i-1])*pow(10,i,mod))%mod
  d[c[i+1]]+=1
  
m=0
for i in range(2019):
  m+=d[i]*(d[i]-1)//2

print(m)
### BUGGY CODE ###

N = int(input())

def f():
    lb = 0
    ub = N - 1
    
    print(lb, flush=True)
    lba = input()
    if lba == 'Vacant': return
    
    print(ub, flush=True)
    uba = input()
    if uba == 'Vacant': return
    
    while lb < ub:
        qry = (lb + ub) // 2
        print(qry, flush=True)
        qa = input()
        if qa == 'Vacant': return
        if (not ((lb ^ qry) & 1) and lba == qa) or (((lb ^ qry) & 1) and lba != qa):
            lb = qry
            lba = qa
        else:
            ub = qa

f()

### FIXED CODE ###

N = int(input())

def f():
    lb = 0
    ub = N - 1
    
    print(lb, flush=True)
    lba = input()
    if lba == 'Vacant': return
    
    print(ub, flush=True)
    uba = input()
    if uba == 'Vacant': return
    
    while lb < ub:
        qry = (lb + ub) // 2
        print(qry, flush=True)
        qa = input()
        if qa == 'Vacant': return
        if (not ((lb ^ qry) & 1) and lba == qa) or (((lb ^ qry) & 1) and lba != qa):
            lb = qry
            lba = qa
        else:
            ub = qry

f()
### BUGGY CODE ###

import numpy as np
N, A, B = map(int,input().split())
h = []
for _ in range(N):
    h.append(int(input()))

def solve(n):
    H = np.array(h)
    H -= B * n
    cnt = 0
    for i in H:
        cnt += (i - 1) // (A - B) + 1
    return cnt <= n

left = 0
right = 10 ** 9

while left + 1 < right:
    mid = (left + right) // 2
    if solve(mid):
        right = mid
    else:
        left = mid

print(right)

### FIXED CODE ###

N, A, B = map(int,input().split())
h = []
for _ in range(N):
    h.append(int(input()))
 
def solve(n):
    cnt = 0
    for i in h:
        i -= B * n
        cnt += max((i - 1) // (A - B) + 1, 0)
    return cnt <= n
 
left = 0
right = 10 ** 9

while left + 1 < right:
    mid = (left + right) // 2
    if solve(mid):
        right = mid
    else:
        left = mid
 
print(right)
### BUGGY CODE ###

def ints():
  return [int(x) for x in input().split()]
def readi():
  return int(input())

H, W = ints()
A = [ints() for _ in range(H)]
B = [ints() for _ in range(H)]
D = [[abs(A[h][w]-B[h][w]) for w in range(W)] for h in range(H)]

memo = {}

memo[(0, 0)] = {D[0][0]}

for h in range(H):
  for w in range(W):
    if h==0 and w==0:
      continue 

    d = D[h][w]
    ss = set()
    if h>0:
      s = memo[(h-1, w)]
      ss |= { x+d for x in s }
      ss |= { abs(x-d) for x in s }
    if w>0:
      s = memo[(h, w-1)]
      ss |= { x+d for x in s }
      ss |= { abs(x-d) for x in s }

    memo[(h, w)] = ss

print(min(memo[(H-1, W-1)]))


### FIXED CODE ###

def ints():
  return [int(x) for x in input().split()]
def readi():
  return int(input())

H, W = ints()
A = [ints() for _ in range(H)]
B = [ints() for _ in range(H)]
D = [[abs(A[h][w]-B[h][w]) for w in range(W)] for h in range(H)]

memo = {}
memo = {}


N=80*60
memo[(0, 0)] = 1 << (D[0][0]+N)

for h in range(H):
  for w in range(W):
    if h==0 and w==0:
      continue 

    d = D[h][w]
    f = 0
    if h>0:
      s = memo[(h-1, w)]
      f |= s<<d 
      f |= s>>d
    if w>0:
      s = memo[(h, w-1)]
      f |= s<<d
      f |= s>>d

    memo[(h, w)] = f

def min_keta(n):
  b = bin(n>>N)
  for i in range(len(b)):
    if b[-i-1]=='1':
      return i

print(min_keta(memo[(H-1, W-1)]))
### BUGGY CODE ###

import sys

# input処理を高速化する
input = sys.stdin.readline

def main(n, lst_p):
    # dp[j] := 表が j 枚となる確率
    # dp[j] = dp[j-1]*p[i] + dp[j]*(1-p[i])
    dp = [0.0] * (N+1)
    # 初期条件
    dp[0]= 1.0

    for i in range(N):
        # 更新前のdpを更新に使う。
        dp_before_update = dp[:]
        for j in range(N+1):
            dp[j] = (dp_before_update[j-1] * lst_p[i]) + (dp_before_update[j] * (1 - lst_p[i]))
    
    ans = sum(dp[(N//2+1):])

    print(ans)

N = int(input())
lst_p = list(map(float, input().split()))

main(N, lst_p)

### FIXED CODE ###

import sys

# input処理を高速化する
input = sys.stdin.readline

def main():
    N = int(input())
    lst_p = list(map(float, input().split()))

    # dp[i][j] := 最初の i 枚のコインを投げたときに、表が j 枚となる確率
    # 次のコインが表: dp[i+1][j+1] += dp[i][j]∗p[i]
    # 次のコインが裏: dp[i+1][j] += dp[i][j]∗(1.0−p[i])
    dp = [[0] * (N+1) for i in range(N+1)]

    # 初期条件
    dp[0][0] = 1.0

    for i in range(N):
        for j in range(N):
            dp[i+1][j+1] += dp[i][j] * lst_p[i]
            dp[i+1][j] += dp[i][j] * (1.0 - lst_p[i])
    
    ans = 0
    for i in range((N+1)//2, N+1):
        ans += dp[N][i]

    print(ans)

main()
### BUGGY CODE ###

a, b = map(int, input().split())

for i in range(10**9):
    a_ans = abs(a-i)
    b_ans = abs(b-i)
    if a_ans == b_ans:
        ans = i
        flag = 1
        break

if flag == 1:
    print(ans)
else:
    print('IMPOSSIBLE')

### FIXED CODE ###

a, b = map(int, input().split())
def kansu_return_flag(a,b):
    ans = 0
    flag = 0

    if abs(a-b)%2 != 0:
        flag = 0
    else:
        ans = (a+b)/2
        flag = 1
    return flag,ans

flag,ans = kansu_return_flag(a,b)

if flag == 1:
    print(int(ans))
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

import re
import numpy as np
import math

#a = int(input())
#b, c = map(int, input().split())
#l = list(map(int, input().split()))


n = int(input())
s=[]
c=[]
for i in range(0,n):
  ns=input()
  if ns in s:
    c[s.index(ns)] += 1
  else:
    #new
    s.append(ns)
    c.append(1)

cmax=max(c)
anss=[]
for i in range(0,len(c)):
  if c[i]==cmax:
    anss.append(s[i])

anss.sort()
print("\n".join(anss))


### FIXED CODE ###

# -*- coding: utf-8 -*-
# 整数の入力
#a = int(input())
# スペース区切りの整数の入力
#b, c = map(int, input().split())
# 文字列の入力
#s = input()
# 出力
#print("{} {}".format(a+b+c, s))

from collections import Counter

n = int(input())
s=[input() for i in range(n)]
l=Counter(s)
m=0
for i in l.values():
  m=max(m,i)
ans=[]
for k,v in l.items():
  if v==m:
    ans.append(k)
ans.sort()
print(*ans,sep='\n')
### BUGGY CODE ###

#!/usr/bin/python3
import sys
def left(i):
    return i * 2

def right(i):
    return i * 2 + 1

def parent(i):
    return i // 2

def heap_increase_key(A, key):
    i = len(A) - 1
    A[i] = key
    while i > 1 and A[parent(i)] < A[i]:
        A[i], A[parent(i)] = A[parent(i)], A[i]
        i = parent(i)

def insert(A, key):
    A.append(-float('inf'))
    heap_increase_key(A, key)

def max_heapify(A, i):
    H = len(A) - 1
    if H == 0:
        return
    l = left(i)
    r = right(i)

    child = {}
    child[i] = A[i] 
    if l <= H:
        child[l] = A[l]
    if r <= H:
        child[r] = A[r]
    largest = max(child.items(), key=lambda x:x[1])[0]

    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        max_heapify(A, largest)

def heap_extract_max(A):
    H = len(A) - 1
    m = A[1]
    A[1] = A[H]
    del A[H]
    max_heapify(A, 1)
    return m

# main
A = [0]
while True:
    s = sys.stdin.readline().split()
    if s[0].startswith('i'):
        insert(A, int(s[1]))
    elif s[0].startswith('ex'):
        print(heap_extract_max(A))
    if s[0] == 'end':
        exit()

### FIXED CODE ###

#!/usr/bin/python3
import sys
import heapq

# main
q = []
S = sys.stdin.readlines()
for line in S:
    if line[0].startswith('i'):
        heapq.heappush(q, -int(line.split()[1]))
    elif line[1] == 'x':
        print(-heapq.heappop(q))
    else:
        exit()
### BUGGY CODE ###

# ?´???°?????°?????¨?????????????????°??????

import sys

prim_no = {}

def is_prime(no):
    if no == 2:
        return True
    
    if no % 2 == 0:
        return False

    if prim_no.get(no) is not None:
        return prim_no.get(no)
    
    for i in range(3, no // 2):
        if no % i == 0:
            prim_no[no] = False
            return False

    prim_no[no] = True
    return True

while True:
    num = sys.stdin.readline()
    if num is None or num.strip() == '':
        break

    num = int(num.strip())
    cnt = 0
    for i in range(2, num + 1):
        if is_prime(i):
            cnt += 1

    print(cnt)

### FIXED CODE ###

# ?´???°?????°?????¨?????????????????°??????

import sys
import math

prim_no = {2: True}                    # ????????°????´???°??§??????????????????????????????

def is_prime(no):
    if no == 2 or no == 1:
        return True
    
    if no % 2 == 0:
        return False

    if prim_no.get(no) is not None:
        return prim_no.get(no)

    max_check = int(math.sqrt(no))
    for i in range(3, max_check+1, 2):
        if no % i == 0:
            prim_no[no] = False
            return False

    prim_no[no] = True
    return True

def main():
    prim_vals = {}                         # ????????°?????§????´???°????????°
    num_data = []                          # ?????????????????????
    
    while True:
        num = sys.stdin.readline()
        if num is None or num.strip() == '':
            break

        num = int(num.strip())
        num_data.append(num)

    sorted_num_data = sorted(num_data)
    prim_num = {}
    
    for num in sorted_num_data:
        if prim_vals.get(num) is not None:
            cnt = prim_vals.get(num)
        else:
            if num == 1:
                cnt = 0
            else:
                cnt = 0

                if num % 2 == 0:
                    start_num = num -1
                else:
                    start_num = num
                    
                for i in range(start_num, 0, -2):
                    if prim_vals.get(i) is not None:
                        cnt += prim_vals.get(i)
                        break
                    
                    if is_prime(i):
                        cnt += 1
                        
                prim_vals[num] = cnt # ????????°?????§????´???°????????°????????????
        prim_num[num] = cnt

    for num in num_data:
        print(prim_num[num])

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

N, K = map(int, input().split())
h = list(map(int, input().split()))
 
DP = [0]
for i in range(N-1):
    act = float("inf")
    for k in range(K):
        if i-k < 0 : continue
        act = min(DP[-1-k] + abs(h[i-k]-h[i+1]) , act)
    DP += [act]
 
print(DP[-1])

### FIXED CODE ###

# EDPC B Frog 2
N, K = map(int, input().split())
H = list(map(int,input().split()))

cost = [float("inf")]*N
cost[0] = 0
cost[1] = abs(H[1]-H[0])

for i in range(2,N):
    for k in range(1,min(K,i)+1):
        cost[i] = min(cost[i], cost[i-k]+abs(H[i]-H[i-k]))

print(cost[N-1])
### BUGGY CODE ###

S = input()

L = []
for i in range(len(S)+1):
  for j in range(len(S)+1):
    if i<j:
      L.append(S[i:j])
B = list(map(int,L))
A = list(filter(lambda x:x%2019==0,B))
print(len(A))

### FIXED CODE ###

S = input()[::-1]
n = len(S)

cnt = [0] * 2019
cnt[0] = 1
m = 0
d = 1
for i in S:
  m += int(i) * d
  m %= 2019
  cnt[m] += 1
  d *= 10
  d %= 2019

ans=0
for i in cnt:
  ans += int(i*(i-1)/2)
print(ans)
### BUGGY CODE ###

import heapq
inf = 10**11
def dijkstra(v0):
    d = [(inf, inf)] * N
    d[v0] = (0, L)
    edgelist = []
    for v, c in G[v0]:
        if c<=L:
            heapq.heappush(edgelist,(0, -(L-c), v))
    while len(edgelist):
        c, r, v = heapq.heappop(edgelist)
        r = -r
        if d[v][0] != inf:
            continue
        d[v] = (c, r)
        for nv, nr in G[v]:
            if d[nv][0] == inf:
                if nr<=r:
                    heapq.heappush(edgelist,(c, -(r-nr), nv))
                elif nr<L:
                    heapq.heappush(edgelist,(c+1,-(L-nr), nv))
    return d
N, M, L = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    G[a-1].append((b-1, c))
    G[b-1].append((a-1, c))
ans = []
for i in range(N):
    ans.append(dijkstra(i))
Q = int(input())
for _ in range(Q):
    a, b = map(int, input().split())
    res = ans[a-1][b-1][0]
    print(res if res<10**10 else -1)

### FIXED CODE ###

inf = 10**10
def warshall_floyd(d):#d[u][v]:辺uvのコスト.存在しなければinf.d[i][i]は0
    for i in range(N):#0~iとa, bのみを使う最短経路を考える
        for a in range(N):
            for b in range(N):
                d[a][b] = min(d[a][b], d[a][i]+ d[i][b])#頂点iを使う場合と使わない場合
    return d
N, M, L = map(int, input().split())
G = [[inf]*N for _ in range(N)]
for i in range(N):
    G[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    G[a-1][b-1] = c
    G[b-1][a-1] = c
G = warshall_floyd(G)
G2 = [[0]*N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j:
            G2[i][j] = 0
        elif G[i][j]<=L:
            G2[i][j] = 1
        else:
            G2[i][j] = inf
d = warshall_floyd(G2)
Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    ans = d[s-1][t-1]-1
    print(ans if ans < 10**9 else -1)
### BUGGY CODE ###

def have_loop(G, V):
    #Gに閉路があるかを判定 Gは隣接グラフによる表現. 0-based Vは頂点数
    parent = [{v} for v in range(V)] #各頂点の親集合
    reached = [False] * V
    for v in range(V):
        stack = []
        if not reached[v]:
            stack.append(v)
            while stack:
                u = stack.pop()
                reached[u] = True
                for w in G[u]:
                    if w in parent[u]:
                        return True
                    elif not reached[w]:
                        parent[w] |= parent[u]
                        stack.append(w)
    return False

N, M = map(int, input().split())
s = input()
G = [[] for _ in range(2 * N)]
for _ in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    if s[a] == s[b]:
        G[a].append(b + N)
        G[b].append(a + N)
    else:
        G[a + N].append(b)
        G[b + N].append(a)
if have_loop(G, 2 * N):
    print('Yes')
else:
    print('No')


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
s = input()
G = [[] for _ in range(2 * N)]
for _ in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    if s[a] == s[b]:
        G[a].append(b + N)
        G[b].append(a + N)
    else:
        G[a + N].append(b)
        G[b + N].append(a)

status = [0] * (2 * N) #0 = 未訪問　1 = 訪問中 2 = 訪問済
def dfs(v):
    if status[v] == 1:
        print('Yes')
        exit()
    elif status[v] == 0:
        status[v] = 1
        for u in G[v]:
            dfs(u)
        status[v] = 2

for v in range(2 * N):
    dfs(v)
print('No')
### BUGGY CODE ###

n = int(input())
p_list = list(map(int, input().split()))
ans = 1
for i in range(1, n):
    if all([p_list[i] <= p_list[j] for j in range(i)]):
        ans += 1
print(ans)


### FIXED CODE ###

n = int(input())
p_list = list(map(int, input().split()))
ans = 1
min = p_list[0]
for i in range(1, n):
    if min >= p_list[i]:
        ans += 1
        min = p_list[i]
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
pList = list(map(int, input().split()))
max_sumK = 0
max_start = 0
max_end = 0
for i in range(N-K+1):
  start = i
  end = i+K
  sumK = sum(pList[start:end])
  if (sumK > max_sumK):
    max_sumK = sumK
    max_start = start
    max_end = end
answer = 0
#print("s"+str(max_start)+"g"+str(max_end))
for num in pList[max_start:max_end]:
  answer += sum(list(range(1, (num+1))))/num
print(answer)

### FIXED CODE ###

N, K = map(int, input().split())
pList = list(map(int, input().split()))
#範囲内の和を求めるには累積和とういうのを使う
#事前準備
cum_sum_list = [0]*(N+1)
cum_sum = 0
pListLen = len(pList)
for i in range(pListLen):
  cum_sum += pList[i]
  cum_sum_list[i+1] = cum_sum
#範囲内の和を比べていく
max_sumK = 0
max_start = 0
max_end = 0
for i in range(N-K+1):
  start = i
  end = (i+K)
  sumK = cum_sum_list[end] - cum_sum_list[start]
  if (sumK > max_sumK):
    max_sumK = sumK
    max_start = start
    max_end = end
#最大の期待値を計算して出力
answer = 0
for num in pList[max_start:max_end]:
  answer += sum(list(range(1, (num+1))))/num
print(answer)
### BUGGY CODE ###

n, q = map(int,input().split())
s = input()
#cnt = 0
for i in range(q):
  l, r = map(int,input().split())
  #print(s[l-1:r])
  if 'AC' not in s[l-1:r]:
    print(0)
  else:
    print(s[l-1:r].count('AC'))

### FIXED CODE ###

n, q = map(int,input().split())
s = input()
li = [0]*(n+1)
for i in range(n):
  li[i+1] = li[i] + (1 if s[i:i+2]=='AC' else 0)
#print(li)
for i in range(q):
  l, r = map(int,input().split())
  print(li[r-1]-li[l-1])
### BUGGY CODE ###

from sys import stdin
N = int(stdin.readline().rstrip())
num_line = [stdin.readline().rstrip() for _ in range(N)]
for i in range(N):
    save_num = num_line[i]
    num_line.pop(i)
    print(max(num_line))
    num_line.insert(i, save_num)

### FIXED CODE ###

N = int(input())
num_line = [int(input()) for _ in range(N)]
sort_line = sorted(num_line)
for i in num_line:
    if i == sort_line[N-1]:
        print(sort_line[N-2])
    else:
        print(sort_line[N-1])
### BUGGY CODE ###

def main():
    S = input()
    T = input()
    N = len(S)
    M = len(T)
    dp = [[0] * (M+1) for _ in range(N+1)]
    
    for i in range(1, N+1):
        for j in range(1, M+1):
            p = (S[i-1] == T[j-1])
            dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + p)
            
    ans = []
    x, y = N, M
    while x and y:
        if dp[x][y] == dp[x-1][y]:
            x -= 1
        elif dp[x][y] == dp[x][y-1]:
            y -= 1
        else:
            x -= 1
            y -= 1
            ans.append(S[x])
        
    print(''.join(ans[::-1]))


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    S = input()
    T = input()
    N = len(S)
    M = len(T)
    dp = [[0] * (M+1) for _ in range(N+1)]
    
    for i in range(1, N+1):
        for j in range(1, M+1):
            p = (S[i-1] == T[j-1])
            dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + p)
            
    ans = []
    x, y = N, M
    while x and y:
        if dp[x][y] == dp[x-1][y]:
            x -= 1
        elif dp[x][y] == dp[x][y-1]:
            y -= 1
        else:
            x -= 1
            y -= 1
            ans.append(S[x])
        
    print(''.join(ans[::-1]))


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

N, K = map(int, input().split())
ans = 0
for i in range(1, N+1):
    for j in range(1, N+1):
        if i % j >= K:
            ans += 1
print(ans)


### FIXED CODE ###

N,K=map(int,input().split())
ans=0
for i in range(K+1,N+1):
  ans += (i-K) * (N//i) + (max(0,N%i - max(K-1,0)))
print(ans)
### BUGGY CODE ###

n,*a=map(int,open(0).read().split())
b=[]
for i in range(n):b=(b+[a[i]])[::-1]
print(*b)

### FIXED CODE ###

n,*a=map(int,open(0).read().split())
b=a[1::2][::-1]+a[::2]
print(*b[::n%2<1or-1])
### BUGGY CODE ###

from collections import deque


h, w = map(int, input().split())
grid = [input() for _ in range(h)]
cost = [[-1] * w for _ in range(h)]
nb = [(-1, 0), (0, -1), (1, 0), (0, 1)]

q = deque()
for i in range(h):
    for j in range(w):
        if grid[i][j] == "#":
            q.append((i, j))
            cost[i][j] = 0

while q:
    x, y = q.popleft()
    for dx, dy in nb:
        nx = x + dx
        ny = y + dy
        if 0 <= nx and nx < h and 0 <= ny and ny < w and cost[nx][ny] == -1:
            cost[nx][ny] = cost[x][y] + 1
            q.append((nx, ny))


print(max([max(c) for c in cost]))

### FIXED CODE ###

from collections import deque
 
H, W = map(int, input().split())
A = [input() for i in range(H)]
q = deque()
c = [[-1] * W for i in range(H)]
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            q.append((i, j))
            c[i][j] = 0
D = [[0, 1], [1, 0], [0, -1], [-1, 0]]
while q:
    y, x = q.popleft()
    for dy, dx in D:
        ny, nx = y+dy, x+dx
        if 0 <= ny < H and 0 <= nx < W and c[ny][nx] == -1:
            q.append((ny, nx))
            c[ny][nx] = c[y][x]+1
print(max([max(l) for l in c]))
### BUGGY CODE ###

n = int(input())
s = input()

ans = 0
for i in range(1, n):
    cnt = 0
    for j in range(n-i):
        if s[i+j] == s[j]:
            cnt += 1
        else:
            if cnt >= i:
                ans = max(ans, i)
                break
            else:
                ans = max(ans, cnt)
                cnt = 0

    ans = max(ans, min(cnt, i))

print(ans)


### FIXED CODE ###

n = int(input())
s = input()

n += 1
s += "#"

ans = 0
for i in range(1, n):
    cnt = 0
    for j in range(n-i):
        if s[i+j] == s[j]:
            cnt += 1
        else:
            ans = max(ans, min(cnt, i))
            cnt = 0

print(ans)