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

N, X = map(int, input().split())
L = list(map(int, input().split()))
L.append(X)
L.sort()
cand = []
def gcd(x, y):
    if x > y:
        small = y
    else:
        small = x
    for i in range(1, small + 1):
        if ((x % i == 0) and (y % i == 0)):
            gcd = i
    return gcd

for i in range(N):
    cand.append(abs(L[i] - L[i+1]))

for i, can in enumerate(cand):
    if i == 0:
        tmp = can
        continue
    tmp = gcd(tmp, can)
print(tmp)


### FIXED CODE ###

N, X = map(int, input().split())
L = list(map(int, input().split()))
L.append(X)
L.sort()
cand = []
def gcd(x, y):
    while y != 0:
        (x, y) = (y, x % y)
    return x

for i in range(N):
    cand.append(abs(L[i] - L[i+1]))

for i, can in enumerate(cand):
    if i == 0:
        tmp = can
        continue
    tmp = gcd(tmp, can)
print(tmp)
### BUGGY CODE ###

N = int(input())
X = str(input())
X_list = list(X)
X_list = list(map(int, X_list))

X10 = int(X,2)
one_num = sum(X_list)
#%%
for i in range(N):
    target = X_list[i]
    if target == 0:
        plus = pow(2,N-i-1)
        ones = one_num + 1
    else:
        plus = -pow(2,N-i-1)
        ones = one_num-1
    
    Xnow = X10+plus
    count = 0
    if Xnow == 0:
        print(count)
        continue
    else:
        Xnow = Xnow%ones
        count+=1
        while Xnow > 0:
            Xnow2 = format(Xnow, 'b')
            ones = Xnow2.count("1")
            Xnow = Xnow%ones
            count+=1
        print(count)

### FIXED CODE ###

N = int(input())
x2 = input()
x10 = int(x2, 2)
popc =  x2.count("1")
#print("x10", x10)
#print("popc", popc)
#popc: Nを2進数で表したときの1の個数

#以下で1つフリップさせた時の入力に対する余りを事前に計算
if popc <= 1:
    xp = x10%(popc+1)
    xm = 0
else:
    xp = x10%(popc+1)
    xm = x10%(popc-1)
#print("xp", xp)
#print("xm", xm)

#以下でフリップさせた場所のみを計算
for i in range(N):
    if x2[i] == "1":
        if popc == 1:
            print(0)
            continue
        tmp = (xm - pow(2, N-i-1, popc-1))%(popc-1)
    else:
        tmp = (xp + pow(2, N-i-1, popc+1))%(popc+1)
        
    #print("tmp", tmp)
    ans = 1
    while tmp > 0:
        tmp %= bin(tmp).count("1")
        ans += 1
    print(ans)
### BUGGY CODE ###

A, B, C, D = map(int, input().split())
cnt = 0
i = A

while A <= i and i <= B:
    if i%C != 0 and i%D != 0:
        cnt +=1
    i +=1

print(cnt)

### FIXED CODE ###

from fractions import gcd

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

cnt = B//C -(A - 1)//C + B//D - (A - 1)//D - ((B//((C * D) // gcd(C, D))) - (A - 1)//((C * D) // gcd(C, D)))
cnt1 = B - (A - 1) -cnt

print(cnt1)
### BUGGY CODE ###

n = int(input())
A = [int(i) for i in input().split()]
ans = 1
for i in range(n):
    ans = ans * A[i]
if ans >pow(10,18):
        print(-1)
else:
    print(ans)
    

### FIXED CODE ###

n = int(input())
A = [int(i) for i in input().split()]
the = pow(10,18)
ans = 1

if 0 in A:
    print(0)
else:
    for i in range(n):
        ans *= A[i]
        if ans >the:
            print(-1)
            break
        else:
            continue
    if ans <= the:
        print(ans)
### BUGGY CODE ###


N,K=map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
B=[]
D=[]
A.sort(reverse=True)
F.sort()
max=A[0]*F[0]-1
for i in range(N):
  B.append(A[i]*F[i])
  if(max<A[i]*F[i]):
    max=A[i]*F[i]
    D.clear()
  if(max==A[i]*F[i]):
    D.append(i)
while(K>=len(D)):
  for i in D:
    B[i]-=F[i]
    K-=1
  max=B[0]-1
  for i in range(N):
    if(max<B[i]):
      max=B[i]
      D.clear()
    if(max==B[i]):
      D.append(i)
print(max)

### FIXED CODE ###

import numpy as np
 
a,b=map(int,input().split())
A=np.array(sorted(list(map(int,input().split()))))
F=np.array(sorted(list(map(int,input().split())),reverse=True))
 
s=A.sum()
 
x=-1
y=10**12
while x+1<y:
  mid=(x+y)//2
  if s-np.minimum(A,mid//F).sum()<=b:
    y=mid
  else:
    x=mid
print(y)
### BUGGY CODE ###

import numpy as np

n, m, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A.insert(0, 0)
B.insert(0, 0)

A = np.array(A)
B = np.array(B)

A_cumsum = np.cumsum(A)
B_cumsum = np.cumsum(B)

ans = 0

for i, a in enumerate(A_cumsum):
    for j, b in enumerate(B_cumsum):
        n = i + j
        if n > ans:
            if a + b <= k:
                ans = n
            else:
                break

print(ans)

### FIXED CODE ###

n, m, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A_cumsum, B_cumsum = [0], [0]

for i in range(n):
    A_cumsum.append(A_cumsum[i] + A[i])
    
for j in range(m):
    B_cumsum.append(B_cumsum[j] + B[j])
    
ans, j = 0, m

for i in range(n + 1): # 0を最初に代入した分
    if A_cumsum[i] > k:
        break
    while A_cumsum[i] + B_cumsum[j] > k:
        j -= 1
    ans = max(ans, i + j)

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

import sys
sys.setrecursionlimit(10**7)

n,q = map(int,input().split())
costs = [0]*n
net = [[] for _ in range(n)]
for _ in range(1,n):
	a,b = map(int,input().split())	
	a -= 1
	b -= 1
	net[a].append(b)
	net[b].append(a)
	
for _ in range (q):
	p,x = map(int,input().split())
	costs[p-1] += x

def dfs(parents,checked_par):
	for children in net[parents]:
		if children == checked_par:
			continue
		costs[children] += costs[parents]
		dfs(children,parents)
dfs(0,-1)

print(*costs)


### FIXED CODE ###

from collections import deque
n,q = map(int,input().split())
graph = [[] for _ in range(n)]
cnt = [0] * n
already = [False] * n

for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    
for i in range(q):
    p,x = map(int,input().split())
    cnt[p-1] += x
wait_q = deque()
wait_q.append(0)

while len(wait_q) > 0:
    parent = wait_q.popleft()
    for child in graph[parent]:
        if child == 0:continue
        if already[child] == True:continue
        already[child] = True
        cnt[child] += cnt[parent]
        wait_q.append(child)
print(*cnt)
### BUGGY CODE ###

K, S = input().strip().split()
K, S = int(K), int(S)

NUMS = list(range(K+1))

count = 0

for x in NUMS:
  for y in NUMS:
    for z in NUMS:
      if x + y + z == S:
        count += 1
print(count)

### FIXED CODE ###

K, S = input().strip().split()
K, S = int(K), int(S)

NUMS = list(range(K+1))

sums = {}

count = 0

for x in NUMS:
  for y in NUMS:
    if x+y not in sums:
      sums[x+y] = 0
    sums[x+y] += 1
for k, v in sums.items():
  z = S - k
  if z in NUMS:
    count += v
print(count)
### BUGGY CODE ###

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

d = [0]*(n+1)
for i in range(1,n+1):
  d[i] = i
  
s = [0] + [1]*n

g=[ [0] ]*(n+1)
for i in range(1,n+1):
  g[i] = [i]
g[0] = []
#print(g)
#quit()

c = n*(n-1)//2
ans = []
ans.append(c)

for i in range(1,m)[::-1]:
  x = d[a[i]]
  y = d[b[i]]
  if x == y:
    ans.append(c)
    continue
  c -= s[x]*s[y]
  #print(c, "x")
  ans.append(c)
  s[x] += s[y]
  s[y] = 0
  for i in g[y]:
    d[i] = x
  g[x] = g[x] + g[y]
  g[y] = []
for t in ans[::-1]:
  print(t)
  

### FIXED CODE ###

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

d = [0]*(n+1)
for i in range(1,n+1):
  d[i] = i
  
s = [0] + [1]*n

g=[ [0] ]*(n+1)
for i in range(1,n+1):
  g[i] = [i]
g[0] = []
#print(g)
#quit()

c = n*(n-1)//2
ans = []
ans.append(c)

for i in range(1,m)[::-1]:
  x = d[a[i]]
  y = d[b[i]]
  x,y = max(x,y),min(x,y)
  if x == y:
    ans.append(c)
    continue
  c -= s[x]*s[y]
  #print(c, "x")
  ans.append(c)
  s[x] += s[y]
  #s[y] = 0
  for i in g[y]:
    d[i] = x
  g[x] += g[y]
  #g[y] = []
for t in ans[::-1]:
  print(t)
### BUGGY CODE ###

import bisect

n = int(input())
s = list(map(int, input().split()))
a = [s[1]]
ans = s[2]
p = 0

for i in range(n-1):
    q = list(map(int,input().split()))
    if q[0]==1:
        ans += q[2]
        if len(a)%2==1:
            ans+=abs(a[p]-q[1])
            bisect.insort(a,q[1])
        else:
            p+=1
            bisect.insort(a,q[1])
            ans+=abs(a[p]-q[1])
    if q[0]==2:
        print(a[p], ans)

### FIXED CODE ###

import heapq

n = int(input())
s = list(map(int, input().split()))

# 中央値より左・右の管理
l=[]
r=[]
heapq.heapify(l)
heapq.heapify(r)
lenl=0
lenr=0
# 中央値
x = s[1]

# b含めた答え
ans = s[2]

for i in range(n-1):
    q = list(map(int,input().split()))
    if q[0]==1:
        ans += q[2]
        if (lenl+lenr)%2==0:
            lenr+=1
            ans+=abs(x-q[1])
            if x<=q[1]:
                heapq.heappush(r,q[1])
            else:
                heapq.heappush(l,-q[1])
                heapq.heappush(r,x)
                x = -heapq.heappop(l)
        else:
            lenl+=1
            if x<q[1]:
                heapq.heappush(l,-x)
                heapq.heappush(r,q[1])
                x=heapq.heappop(r)
            else:
                heapq.heappush(l,-q[1])
            ans+=abs(x-q[1])
    if q[0]==2:
        print(x, ans)
### BUGGY CODE ###

s=int(input())
S=[0] * (len(str(s))+1)
ans=0
for i in range(len(str(s))):
    S[-i-1]=int(str(s)[i:])
for i in range(len(str(s))+1):
    for j in range(i+5, len(str(s))+1):
        if (S[j]-S[i])%2019==0:
            ans+=1
print(ans)

### FIXED CODE ###

s=input()
p=2019
ans=0
M=[0]*p
M[0]=1
tmp=0
for i in range(len(s)):
    tmp+=(int(s[-i-1])*pow(10,i,p))
    tmp%=p
    ans+=M[tmp]
    M[tmp]+=1
print(ans)
### BUGGY CODE ###

import collections

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

for i in range(n):
    s[i] = [s[i][j] for j in range(10)]
    s[i] = collections.Counter(s[i])

count = 0

for i in range(n):
    for j in range(n):
        if s[i] == s[j]:
            count += 1

count = (count - n)//2

print(count)



### FIXED CODE ###

import collections
n = int(input())

s = ["".join(sorted(input())) for i in range(n)]

a = collections.Counter(s)

ans = 0

for i in a.values():
    ans += i*(i-1)//2

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

from numba import njit
import numpy as np

@njit('i4, i4, i4, i4[:,:], i4[:,:]')
def dfs(N, h, w, minDist, isFilled):
    dist = minDist[h][w] + isFilled[h][w]

    if h + 1 < N and minDist[h + 1][w] > dist:
        minDist[h + 1][w] = dist
        dfs(N, h + 1, w, minDist, isFilled)
    if h - 1 >= 0 and minDist[h - 1][w] > dist:
        minDist[h - 1][w] = dist
        dfs(N, h - 1, w, minDist, isFilled)
    if w + 1 < N and minDist[h][w + 1] > dist:
        minDist[h][w + 1] = dist
        dfs(N, h, w + 1, minDist, isFilled)
    if w - 1 < N and minDist[h][w - 1] > dist:
        minDist[h][w - 1] = dist
        dfs(N, h, w - 1, minDist, isFilled)

@njit('i4(i4, i4[:])')
def solve(N, P):
    minDist = np.ones((N, N), dtype=np.int32)
    isFilled = np.ones((N, N), dtype=np.int32)

    for h in range(N):
        for w in range(N):
            minDist[h][w] = min(h, N - h - 1, w, N - w - 1)

    ans = 0
    for p in P:
        h, w = divmod(p, N)
        ans += minDist[h][w]
        isFilled[h][w] = False
        dfs(N, h, w, minDist, isFilled)
    return ans

N = int(input())
P = np.asarray(list(map(lambda a: int(a) - 1, input().split())), dtype=np.int32)

print(solve(N, P))


### FIXED CODE ###

import sys
import numpy as np

if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    cc = CC('my_module')

    @cc.export('solve', 'i4(i4, i4[:])')
    def solve(N, P):
        minDist = np.ones((N, N), dtype=np.int32)
        isFilled = np.ones((N, N), dtype=np.int32)

        for h in range(N):
            for w in range(N):
                minDist[h][w] = min(h, N - h - 1, w, N - w - 1)

        ans = 0
        for p in P:
            h, w = divmod(p, N)
            ans += minDist[h][w]
            isFilled[h][w] = False

            st = [(h, w)]
            while st:
                h, w = st.pop()
                dist = minDist[h][w] + isFilled[h][w]

                if h + 1 < N and minDist[h + 1][w] > dist:
                    minDist[h + 1][w] = dist
                    st.append((h + 1, w))
                if h - 1 >= 0 and minDist[h - 1][w] > dist:
                    minDist[h - 1][w] = dist
                    st.append((h - 1, w))
                if w + 1 < N and minDist[h][w + 1] > dist:
                    minDist[h][w + 1] = dist
                    st.append((h, w + 1))
                if w - 1 < N and minDist[h][w - 1] > dist:
                    minDist[h][w - 1] = dist
                    st.append((h, w - 1))
        return ans

    cc.compile()
    exit(0)

from my_module import solve

N = int(input())
P = np.asarray(list(map(lambda a: int(a) - 1, input().split())), dtype=np.int32)

print(solve(N, P))
### BUGGY CODE ###

n = int(input())

num = []
cnt = 0

for i in range(n):
    a = int(input())
    if a in num:
        num.pop(num.index(a))
        cnt -= 1
    else:
        num.append(a)
        cnt += 1

print(cnt)


### FIXED CODE ###

n = int(input())
A = []

for i in range(n):
    a = int(input())
    A.append(a)

A.sort()

odd = 0
prev = A[0]
cnt = 1

for i in range(1,n):
    if A[i] != prev:
        if cnt % 2 == 1:
            odd += 1
        cnt = 1
        prev = A[i]
    else:
        cnt += 1

if cnt % 2 == 1:
    odd += 1

print(odd)
### BUGGY CODE ###

n = int(input())
a = list(map(str,input().split()))
ans = 'YES'
for i in range(n):
    if a.count(a[i]) != 1:
        ans = 'NO'
        break
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(str,input().split()))
a.sort()
ans = 'YES'
for i in range(n-1):
    if a[i] == a[i+1]:
        ans = 'NO'
        break
print(ans)
### BUGGY CODE ###

n = int(input())
numlist = []
for i in range(n):
    numlist.append(int(input()))
for i in range(n):
    tmplist = numlist.copy()
    del tmplist[i]
    print (max(tmplist))

### FIXED CODE ###

n = int(input())
numlist = []
for i in range(n):
    numlist.append(int(input()))
argmax = numlist.index(max(numlist))
maxnum = max(numlist)
del numlist[argmax]
secondnum = max(numlist)
                       
for i in range(argmax):
    print (maxnum)
print (secondnum)
for i in range(argmax+1,n):
    print (maxnum)
### BUGGY CODE ###


import heapq
dif = 10 ** 6
initial = 10 ** 15

def di(links, s):
    costs = [initial] * n
    costs[s] = 0
    node_list = []
    serched_node = set()
    heapq.heappush(node_list, s)
    while(len(node_list) != 0 and len(serched_node) != n):
        index = heapq.heappop(node_list) % dif
        if index in serched_node:
            continue
        serched_node.add(index)
        link = links[index]
        for j in range(n):
            if j in serched_node or link[j] == -1:
                continue
        
            cost = link[j]
            newcost =  costs[index] + cost
            if newcost < costs[j]:
                costs[j] = newcost
                heapq.heappush(node_list, newcost * dif + j)
    return costs
    
n, m, s, t  = list(map(int, input().split()))
s -= 1
t -= 1
links_en = [[-1 for j in range(n)] for i in range(n)]
links_sn = [[-1 for j in range(n)] for i in range(n)]

for i in range(m):
    u, v, a, b  = list(map(int, input().split()))
    links_en[u - 1][v - 1] = a
    links_en[v - 1][u - 1] = a
    links_sn[v - 1][u - 1] = b
    links_sn[u - 1][v - 1] = b

cost_en_from_s = di(links_en, s)
cost_sn_to_t = di(links_sn, t)

trans = n - 1
costs = [0] * n
for i in range(n - 1, -1, -1):
    if i == n - 1:
        costs[n-1] = cost_en_from_s[n-1] + cost_sn_to_t[n-1]
        continue
    
    newcost = cost_en_from_s[i] + cost_sn_to_t[i]
    if newcost < costs[trans]:
        trans = i
        costs[i] = newcost
        continue
    
    costs[i] = costs[trans]
    
for cost in costs:
    print(initial - cost)

### FIXED CODE ###

import heapq
initial_cost = 10 ** 9
initial = 10 ** 15

def di(link_costs, s):
    costs = [initial] * n
    costs[s] = 0
    q = []
    heapq.heappush(q, (0, s))
    
    while(len(q) != 0):
        index_cost, index = heapq.heappop(q)
        if costs[index] < index_cost:
            continue

        for j in link_costs[index]:
            newcost = costs[index] + link_costs[index][j]
            if newcost < costs[j]:
                costs[j] = newcost
                heapq.heappush(q, (newcost, j))
    return costs
    
n, m, s, t  = list(map(int, input().split()))
s -= 1
t -= 1
links_cost_en = [{} for _ in range(n)]
links_cost_sn = [{} for _ in range(n)]

for _ in range(m):
    u, v, a, b  = list(map(int, input().split()))
    u -= 1
    v -= 1
    links_cost_en[u][v] = a
    links_cost_en[v][u] = a
    links_cost_sn[u][v] = b
    links_cost_sn[v][u] = b

cost_en_from_s = di(links_cost_en, s)
cost_sn_to_t = di(links_cost_sn, t)
cost_list = [cost_en_from_s[i] + cost_sn_to_t[i] for i in range(n)]

ans = [initial] * n
ans[-1] = cost_list[-1]
for i in list(range(n - 1))[::-1]:
    ans[i] = min(ans[i + 1], cost_list[i])
for i in range(n):
    print(initial - ans[i])
### BUGGY CODE ###

N, M = map(int,input().split())
m=[list(map(int, input().split())) for _ in range(M)]
m=sorted(m, key=lambda x: x[1])
p=0
while m!=[]:
    tmp=max(m)[0]
    while m!=[] and m[-1][1]>tmp:
        m.pop()
    p+=1
print(p)

### FIXED CODE ###

N, M = map(int,input().split())
m=[list(map(int, input().split()))[::-1] for _ in range(M)]
m.sort()

b=[]
for i in m:
    if len([tmp for tmp in b if tmp>=i[1]])==0:
        b.append(i[0]-1)
print(len(b))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
A = []
cnt = 0

for i in range(n-1):
    A.append(a[i])
    if sum(A) > 0 and sum(A) + a[i+1] > 0:
        cnt += abs(sum(A) + a[i+1])+1
        a[i+1] -= abs(sum(A) + a[i+1])+1

    elif sum(A) < 0 and sum(A) + a[i+1] < 0:
        cnt += abs(sum(A) - a[i+1])-1
        a[i+1] += abs(sum(A) - a[i+1])-1

if sum(a) == 0:
    cnt += 1

print(cnt)

### FIXED CODE ###

n = input()
A = list(map(int, input().split()))

def Chk(a, pos):
    cnt = 0
    tmp = 0

    for a in A:
        tmp += a

        if pos and tmp < 1:
            cnt += 1 - tmp
            tmp = 1
        elif not pos and tmp > -1:
            cnt += 1 + tmp
            tmp = -1

        pos = not pos
    return cnt

print(min(Chk(A, True), Chk(A, False)))
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return float(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()



def main():
	nn=II()
	A=LI()
	ans="pairwise coprime"

	n = 1000050
	primes = set(range(2, n+1))
	for i in range(2, int(n**0.5+1)):
		primes.difference_update(range(i*2, n+1, i))
	primes=list(primes)

	#print(primes)


	B=set(range(1,10**6+2))
	C=set()
	for i in A:
		a=set()
		while i%2==0:
			a.add(2)
			i//=2
		f=3
		while f*f<=i:
			if i in primes:
				break
			elif i%f==0:
				a.add(f)
				i//=f
			else:
				f+=2
		if i!=1:
			a.add(i)
		B&=a
		if C&a:
			ans="setwise coprime"
		C|=a
		#print(a)


	if B:
		ans="not coprime"

	print(ans)





















if __name__ == "__main__":
	main()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return float(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()



def main():
	nn=II()
	A=LI()
	ans="pairwise coprime"

	n = 500005
	primes = set(range(2, n+1))
	for i in range(2, int(n**0.5+1)):
		primes.difference_update(range(i*2, n+1, i))
	primes=set(primes)

	#print(primes)


	B=set(range(1,5*10**5+5))
	C=set()
	for i in A:
		a=set()
		while i%2==0:
			a.add(2)
			i//=2
		f=3
		while f*f<=i:
			if i in primes:
				break
			elif i%f==0:
				a.add(f)
				i//=f
			else:
				f+=2
		if i!=1:
			a.add(i)
		B&=a
		if C&a:
			ans="setwise coprime"
		C|=a

	if B:
		ans="not coprime"

	print(ans)





















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

S = input()
T = input()
dp = [[-1 for i in range(len(S)+1)] for j in range(len(T)+1)]
sub = [["" for i in range(len(S)+1)] for j in range(len(T)+1)]
for a in range(len(S)+1):
	dp[0][a] = 0
for b in range(len(T)+1):
	dp[b][0] = 0
for p in range(1, len(T)+1):
	for q in range(1, len(S)+1):
		if T[p-1] == S[q-1]:
			dp[p][q] = 1 + dp[p-1][q-1]
			sub[p][q] = sub[p-1][q-1] + T[p-1]
		else:
			if dp[p-1][q] > dp[p][q-1]:
				dp[p][q] = dp[p-1][q]
				sub[p][q] = sub[p-1][q]
			else:
				dp[p][q] = dp[p][q-1]
				sub[p][q] = sub[p][q-1]
print(sub[len(T)][len(S)])

### FIXED CODE ###

S = input()
T = input()
dp = [[-1 for i in range(len(S)+1)] for j in range(len(T)+1)]
sub = [["" for i in range(len(S)+1)] for j in range(len(T)+1)]
for a in range(len(S)+1):
	dp[0][a] = 0
for b in range(len(T)+1):
	dp[b][0] = 0
for p in range(1, len(T)+1):
	for q in range(1, len(S)+1):
		if T[p-1] == S[q-1]:
			dp[p][q] = 1 + dp[p-1][q-1]
			sub[p][q] = "c"
		else:
			if dp[p-1][q] > dp[p][q-1]:
				dp[p][q] = dp[p-1][q]
				sub[p][q] = "u"
			else:
				dp[p][q] = dp[p][q-1]
				sub[p][q] = "l"
t = len(T)
s = len(S)
out = ""
while sub[t][s] != "":
	if sub[t][s] == "c":
		out = S[s-1] + out
		t -= 1
		s -= 1
	elif sub[t][s] == "u":
		t -= 1
	else:
		s -= 1
print(out)
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))

MAX = pow(10, 4) * N
costs = [MAX for _ in range(N)]
costs[0] = 0

for h_i in range(N):
    move_max = min(N - h_i - 1, K) 
    for step in range(1, move_max + 1):
        costs[h_i + step] = min(abs(h[h_i + step] - h[h_i]) + costs[h_i], costs[h_i + step])


print(costs[N - 1])


### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))

MAX = pow(10, 4) * N
costs = [MAX for _ in range(N)]
costs[0] = 0

for h_i in range(N - 1):
    next_step = h_i + 1
    back_max = min(next_step, K)
    for back_index in range(back_max):
        costs[next_step] = min(abs(h[next_step] - h[next_step - back_index -1]) + costs[next_step - back_index -1 ], costs[next_step])


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

N = int(input())
S = []
for n in range(N):
  s = [ss for ss in input()]
  s.sort()
  s_join = "".join(s)
  S.append(s_join)

S_set = list(set(S))
ans = 0
for ss in S_set:
  howmany_ss = S.count(ss)
  if howmany_ss == 1:
    continue
  else:
    ans += sum(range(1, howmany_ss))
    
print(ans)

### FIXED CODE ###

N = int(input())
S = {}
for n in range(N):
  s = [ss for ss in input()]
  s.sort()
  s_join = "".join(s)
  if s_join not in S.keys():
    S[s_join] = 1
  else: #s_join in S.keys():
    S[s_join] += 1

ans = 0
for k in S.values():
  if k == 1:
    continue
  else:
    ans += sum(range(1, k))

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

N = int(input())
prices = [int(n) for n in input().split()]
money = 1000
stock = 0
p_today = prices[0]
for n in range(N-1):
    p_tomm = prices[n+1]
    if p_tomm >= p_today:
        while money >= p_today:
            stock += 1
            money -= p_today
    else:
        money += p_today * stock
        stock = 0
    p_today = p_tomm

if stock > 0:
    money += prices[-1] * stock

print(money)

### FIXED CODE ###

N = int(input())
prices = [int(n) for n in input().split()]
money = 1000
stock = 0
p_today = prices[0]
for n in range(N-1):
    p_tomm = prices[n+1]
    if p_tomm >= p_today:
        n_stock = money // p_today
        stock += n_stock
        money = money - p_today * n_stock
        # while money >= p_today:
        #     stock += 1
        #     money -= p_today
    else:
        money += p_today * stock
        stock = 0
    p_today = p_tomm

if stock > 0:
    money += prices[-1] * stock

print(money)