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

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

# N = 5
# A = [1, 1, 2, 1, 2]

Aset = set(A)
lst = {}
for i in Aset:
    lst[i] = 0

# print(lst)
    
for i in range(N):
    lst[A[i]] += 1

# print(lst)
c = dict(lst) # c = dict(lst)で異なるオブジェクトとして等価なcを定義
              # c = lst だと、同一のオブジェクトとなってしまう？

for i in lst:
#     print('i: {}'.format(i))
    c[i] = 0
    tmp_lst = dict(lst)
#     print('tmp_lst {}'.format(tmp_lst))
#     print('tmp_lst[i]: {}'.format(tmp_lst[i]))
    tmp_lst[i] -= 1
#     print('tmp_lst[i]: {}'.format(tmp_lst[i]))
    for j in tmp_lst:
#         print(tmp_lst[j])
        c[i] += tmp_lst[j]*(tmp_lst[j]-1)//2
#         print('c[i]: {}'.format(c[i]))
        
for i in range(N):
    print(int(c[A[i]]))

### FIXED CODE ###

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

Aset = set(A)
lst = {}
for i in Aset:
    lst[i] = 0
    
for i in range(N):
    lst[A[i]] += 1

llst = dict(lst) # llst は、valueが1のものを消したリスト
for i in lst:
    if lst[i] == 1:
        llst.pop(i)

c = dict(lst) # c は keyの値である場合の組み合わせの数。
              # c = dict(lst)で異なるオブジェクトとして等価なcを定義
              # c = lst だと、同一のオブジェクトとなってしまう？
c_all = 0
for j in llst:
    c_all += llst[j]*(llst[j]-1)//2

# print('c_all:{}'.format(c_all))
for i in lst:
#     print('i:{}'.format(i))
#     print('lst[i]:{}'.format(lst[i]))
    c[i] = c_all
    c[i] = c[i] - lst[i]*(lst[i]-1)//2 + (lst[i]-1)*(lst[i]-2)//2
        
for i in range(N):
    print(c[A[i]])
### BUGGY CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
bc = [list(map(int,input().split())) for _ in range(m)]

bc = sorted(bc,key=lambda x:(x[1]))
count=0
for b,c in bc:
  count += b
  a.extend([c]*b)
  if b > n:
    break
    
print(sum(sorted(a,reverse=True)[:n]))

### FIXED CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
bc = [list(map(int,input().split())) for _ in range(m)]

bc = sorted(bc,key=lambda x:(x[1]),reverse=True)
count=0
for b,c in bc:
  count += b
  a.extend([c]*b)
  if count >= n:
    break
    
print(sum(sorted(a,reverse=True)[:n]))
### BUGGY CODE ###

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

ans = 0
for i in range(n-1):
  for j in range(i+1,n):
    ans += aa[i] ^ aa[j]    

print(ans % (10**9+7)) 

### FIXED CODE ###

## D
MOD = 10**9 + 7
n = int(input())
A = list(map(int,input().split()))

m = 1
ans = 0
for i in range(60):
  s = sum([a&m for a in A])
  s//=m
  ans = (ans + (n-s)*s * m) % MOD
  m <<= 1
  
print(ans)
### BUGGY CODE ###

from scipy.sparse import lil_matrix
from scipy.sparse.csgraph import connected_components

def main():
    n, m = [int(i) for i in input().split()]
    adj = lil_matrix((n, n), dtype=int)
    for _ in range(m):
        x, y, z = [int(i) for i in input().split()]
        adj[x-1, y-1] = 1
    print(connected_components(adj)[0])

if __name__ == '__main__':
    main()



### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.rank = [0] * n

    def root(self, x):
        if x != self.par[x]:
            self.par[x] = self.root(self.par[x])
        return self.par[x]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return

        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
        else:
            self.par[ry] = rx
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    def update_p(self):
        for x in range(self.n):
            self.root(x)

    def get_size(self, x):
        return self.size[self.find_set(x)]




def main():
    n, m = [int(i) for i in input().split()]
    uf = UnionFind(n)
    for _ in range(m):
        x, y, _ = [int(i) for i in input().split()]
        uf.unite(x-1, y-1)
    uf.update_p()
    print(len(set(uf.par)))

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

rn,gn,bn,n=map(int,input().split())
print(sum(n-rn*r-gn*g >=0 and (n-rn*r-gn*g)%bn==0 for r in range(1+n//rn) for g in range(1+n//gn))) 

### FIXED CODE ###

rn,gn,bn,n=map(int,input().split())
nn=sorted([rn,gn,bn]) 
c=0
for r in range(1+n//nn[0]):
    rt=n-nn[0]*r
    for g in range(1+rt//nn[1]):
        gt=rt-nn[1]*g
        if gt%nn[2]==0:
            c+=1
print(c)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
BC = [[int(x) for x in input().split()] for _ in range(M)]
for i in BC:
    B, C = i
    A += [C] * B
    A.sort()
    A = A[len(A) - N:]
print(sum(A[len(A) - N:]))

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
BC = [[int(x) for x in input().split()] for _ in range(M)]
BC = sorted(BC, reverse = True, key = lambda x:x[1])
N2 = N
D = []
for i in BC:
    temp = min(N2,i[0])
    D += [i[1]] * temp
    N2 -= temp
    if not N2:
        break
A += D
A.sort()
print(sum(A[len(A) - N:]))
### BUGGY CODE ###

N = int(input())
S = input().strip()
qn = int(input())
qs = list(map(int, input().split()))
dp = [[0,0,0]]
As = [0]*qn
d=m=dm=0
for i, w in enumerate(S):
    i += 1
    if w=="D":
        d+=1
    elif w == "M":
        m+=1
        dm+=d
    elif w == "C":
        for j, q in enumerate(qs):
            ll = max(i-q, 0)
            As[j] += dm - dp[ll][2] - dp[ll][0]*(m-dp[ll][1])
    dp.append([d,m,dm])
for a in As:
    print(a)


### FIXED CODE ###

N = int(input())
S = input().strip()
qn = int(input())
qs = list(map(int, input().split()))
dd,mm,cc = [0],[0],[0]
As = [0]*qn
d=m=dm=0
for i, w in enumerate(S):
    i += 1
    if w=="D":
        d+=1
    elif w == "M":
        m+=1
        dm+=d
    elif w == "C":
        for j, q in enumerate(qs):
            ll = max(i-q, 0)
            As[j] += dm - cc[ll] - dd[ll]*(m-mm[ll])
    dd.append(d)
    mm.append(m)
    cc.append(dm)
for a in As:
    print(a)
### BUGGY CODE ###

N=int(input())
S=str(input())
list_R=[]
list_G=[]
list_B=[]
count=0
for i in range(N):
    if S[i]=="R":
        list_R.append(i)
    if S[i]=="G":
        list_G.append(i)
    if S[i]=="B":
        list_B.append(i)
for i in range(N):
    for j in range(N):
        k=2*j-i
        if i<j and j<k and k<N:
            if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
                count=count+1

print(len(list_B)*len(list_G)*len(list_R)-count)
        


### FIXED CODE ###

N=int(input())
S=str(input())
list_R=[]
list_G=[]
list_B=[]
count=0
for i in range(N):
    if S[i]=="R":
        list_R.append(i)
    if S[i]=="G":
        list_G.append(i)
    if S[i]=="B":
        list_B.append(i)
for i in range(N):
    for j in range(N):
        if i+2*j>N-1:
            break
        if S[i]!=S[i+j] and S[i+j]!=S[i+j*2] and S[i+2*j]!=S[i]:
            count=count+1

print(len(list_B)*len(list_G)*len(list_R)-count)
### BUGGY CODE ###

# 入力
N, K = map(int, input().split())
A = list(map(int, input().split()))


# MSBから順に0or1を決めていく
# 0にする場合、下位ビットの最適値は貪欲に求まる
def s(i):
    return sum((a >> (i - 1)) & 1 for a in A)


def g(L, b):
    return (
        0 if b == 0 else
        g(L, b - 1) + 2**(b - 1) * s(b) if L < 2**(b - 1) else
        g(L >> 1, b - 1) + 2**(b - 1) * max(
            s(b),
            N - s(b)
        ) if L == (2**b - 1) else
        max(
            g(2**(b - 1) - 1, b - 1) + 2**(b - 1) * s(b),
            g(L - 2**(b - 1), b - 1) + 2**(b - 1) * (N - s(b))
        )
    )


ans = g(K, max(K, *A).bit_length())

# 出力
print(ans)


### FIXED CODE ###

from itertools import accumulate
N, K = map(int, input().split())
A = list(map(int, input().split()))
m = K.bit_length()
b = [sum((a >> k) & 1 for a in A) for k in range(m)]
opt = [0] + list(accumulate(1 << k if 2 * b[k] < N else 0 for k in range(m)))


def f(x):
    return sum(x ^ a for a in A)


def g(k, s):
    if k == 0:
        return f(s)
    r = k.bit_length()
    return max(
      f(s + opt[r - 1]),
      g(k - (1 << (r - 1)), s + (1 << (r - 1)))
    )


ans = g(K, 0)
print(ans)
### BUGGY CODE ###

h,w=map(int,input().split())
grid=[None]*h
seen=[[-1 for i in range(w)] for j in range(h)]
from collections import deque
que=deque()
for i in range(h):
  grid[i]=list(input())
  for j in range(len(grid[i])):
    if grid[i][j]=="#":
      grid[i][j]="."
      que.append([i,j,0])
      
ans=0
while que:
  node=que.popleft()
  y=node[0]
  x=node[1]
  p=node[2]
  if grid[y][x]=="#":
    continue
  if grid[y][x]==".":
    grid[y][x]="#"
  ans=max(ans,p)
  if y-1>=0:
    que.append([y-1,x,p+1])
  if y+1<h:
    que.append([y+1,x,p+1])
  if x-1>=0:
    que.append([y,x-1,p+1])
  if x+1<w:
    que.append([y,x+1,p+1])
print(ans)

### FIXED CODE ###

H,W=map(int,input().split())
INF=10**4
import numpy as np
a=np.full((H,W),INF,dtype=int)
for i in range(H):
  s=input()
  for j in range(len(s)):
    if s[j]=="#":
      a[i,j]=0

for i in range(0,W-1):
  np.minimum(a[:,i]+1,a[:,i+1],out=a[:,i+1])
for i in range(W-1,0,-1):
  np.minimum(a[:,i]+1,a[:,i-1],out=a[:,i-1])
for j in range(0,H-1):
  np.minimum(a[j,]+1,a[j+1,],out=a[j+1,])
for j in range(H-1,0,-1):
  np.minimum(a[j,]+1,a[j-1,],out=a[j-1,])

print(a.max())
### BUGGY CODE ###

import pprint as p
def main():
    n = int(input())
    result = []
    for i in range(n):
        a = input()
        b = input()
        array = [[0 for i in range(len(b))] for j in range(len(a))]
        for i in range(len(a)):
            if a[i]==b[0]:
                array[i][0]=1
        for j in range(len(b)):
            if b[j]==a[0]:
                array[0][j]=1 

        for i in range(1, len(a)):
            for j in range(1, len(b)):
                c = 0
                if a[i] == b[j]:
                    c = 1
                array[i][j] = max(
                                    array[i-1][j],
                                    array[i][j-1],
                                    array[i-1][j-1]+c)
        result.append(array[len(a)-1][len(b)-1])
        #p.pprint(array)
    for i in result:
        print(i)
if __name__ == "__main__":
    main()



### FIXED CODE ###

#dj 16D8101012J ito jun
import sys
def search(a,b):
    na=len(a)
    nb=len(b)
    array = [[0]*(nb+1) for _ in range(na+1)]
    for i,x in enumerate(a,1):
        prerow=array[i-1]
        row=array[i]
        for j,y in enumerate(b,1):
            if x == y:
                row[j]=prerow[j-1]+1
            elif prerow[j] < row[j-1]:
                row[j] = row[j-1]
            else:
                row[j] = prerow[j]
    return array[-1][-1]

n = int(input())
strs = [list(i) for i in sys.stdin.read().splitlines()]
result = [search(strs[i*2], strs[i*2+1]) for i in range(n)]
print(*result, sep="\n")
### BUGGY CODE ###

N, W = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(N)]

INF = 10 ** 12
V = 10 ** 3 * 100 + 10

dp = [0] + [INF] * V
for w, v in WV:
	for i in range(V, v - 1, -1):
		dp[i] = min(dp[i], dp[i - v] + w)

r = 0
for i in range(V):
	if dp[i] <= W:
		r = i
print(r)

"""
for cell in dp:
	if cell == INF:
		print("  INF", end="")
	else:
		print("{:5d}".format(cell), end="")
print()
"""


### FIXED CODE ###

N, W = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(N)]

#import math
INF = 10 ** 12 # math.inf
V = 10 ** 5 + 10

dp = [[INF] * V for _ in range(N + 1)]
dp[0][0] = 0

for i, (w, v) in enumerate(WV):
	for n in range(V):
		if v <= n:
			dp[i + 1][n] = min(dp[i + 1][n], dp[i][n - v] + w)
		dp[i + 1][n] = min(dp[i + 1][n], dp[i][n])
"""
for line in dp:
	for cell in line:
		if cell == INF:
			print("  INF", end="")
		else:
			print("{:5d}".format(cell), end="")
	print()
"""
r = 0
for i in range(V):
	if dp[-1][i] <= W:
		r = i
print(r)
### BUGGY CODE ###

import sys
from heapq import heappop as hpp, heappush as hp

readline = sys.stdin.readline
N = int(readline())
A = list(map(int, readline().split()))
B = list(map(int, readline().split()))

Q = [(-B[i], i) for i in range(N)]
Q.sort()

ans = 0
cnt = 0
inf = 10**9+7
while cnt < N:
    b, idx = hpp(Q)
    b = -b
    bsec, _ = Q[0]
    bsec = -bsec
    a = A[idx]
    if b < a:
        ans = -1
        break
    bside = B[(idx+1)%N] + B[(idx-1)%N]
    kb = (1+(b-bsec)//bside)
    ka = (b-a)//bside
    k = min(ka, kb)
    B[idx] -= k*bside
    ans += k
    if B[idx] == a:
        cnt += 1
        hp(Q, (inf, idx))
    elif k == 0:
        ans = -1
        break
    else:
        hp(Q, (-B[idx], idx))
print(ans)

### FIXED CODE ###

import sys
from heapq import heappop as hpp, heappush as hp

readline = sys.stdin.readline
N = int(readline())
A = list(map(int, readline().split()))
B = list(map(int, readline().split()))

geta = 10**6        
Q = [-(B[i]*geta+i) for i in range(N)] + [0]
Q.sort()

ans = 0
cnt = 0
inf = 10**9+7
while cnt < N:
    b, idx = divmod(-hpp(Q), geta)
    a = A[idx]
    if b < a:
        ans = -1
        break
    bside = B[(idx+1)%N] + B[(idx-1)%N]
    kb = 1+(b-bside)//bside
    ka = (b-a)//bside
    k = min(ka, kb)
    B[idx] -= k*bside
    ans += k
    if B[idx] == a:
        cnt += 1
    elif k == 0:
        ans = -1
        break
    else:
        hp(Q, -(B[idx]*geta+idx))
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0

for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            if j - i != k - j and s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
                ans += 1
print(ans)

### FIXED CODE ###

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

ans = s.count('R') *  s.count('G') *  s.count('B')

for i in range(n):
    for j in range(i+1, n):
        k = 2 * j - i

        if k >= n:
            break
        elif s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
            ans -= 1
         
print(ans)
### BUGGY CODE ###

n = list(map(int, input().split()))
a = list(map(int, input().split()))
for i in range(n[1]):
    ma=max(a)
    a.remove(ma)
    a.append(int(ma/2))
print(sum(a))

### FIXED CODE ###

import heapq

N, M= map(int, input().split())
A = list(map(int, input().split()))
a=[-1*i for i in A]
heapq.heapify(a)
for i in range(M):
    m=int(heapq.heappop(a)/2)
    heapq.heappush(a, m)

print(-1*sum(a))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    S = [int(s) for s in input().split()]
    S.sort(reverse = True)

    result = []
    result.append(S[0])
    que = [True]*len(S)
    que[0] = False

    for i in range(N):
        for j in range(2**i):
            for k in range(len(S)):
                if que[k] and result[j]>S[k]:
                    result.append(S[k])
                    que[k] = False
                    break
            else:
                print("No")
                break
        else:
            continue
        break
    else:
        print("Yes")

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])


def main():
    N = I()
    S = sorted(LI(),reverse=True)

    flag = [True]*len(S)

    cur = []
    cur.append(S[0])
    flag[0] = False

    for i in range(N):
        nxt = [x for x in cur]
        j = 0

        for k in range(len(S)):
            if j >= len(cur):
                break
            elif flag[k] and S[k]<cur[j]:
                nxt.append(S[k])
                j+=1
                flag[k] = False
        if len(cur) != j:
            return("No")
        cur = sorted(nxt,reverse=True)
    return("Yes")

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

from bisect import bisect_left as bl


def f(v):
    v = str(v)
    return '0' * (6 - len(v)) + v


N, M = map(int, input().split())
dic = dict()
PY = []
for i in range(M):
    p, y = map(int, input().split())
    if dic.get(p, False):
        dic[p].append(y)
    else:
        dic[p] = [y]
    PY.append((p, y))

for i in range(1, N + 1):
    if dic.get(i, False):
        dic[i] = sorted(dic[i])

# print('dic', dic, PY)
for i in range(M):
    p, y = PY[i]
    # print('p y', p, y)
    l = dic[p]
    ans = f(p) + f(l.index(y) + 1)
    print(ans)


### FIXED CODE ###

from bisect import bisect_left as bl


def f(v):
    v = str(v)
    return '0' * (6 - len(v)) + v


N, M = map(int, input().split())
dic = dict()
PY = []
for i in range(M):
    p, y = map(int, input().split())
    if dic.get(p, False):
        dic[p].append(y)
    else:
        dic[p] = [y]
    PY.append((p, y))

for i in range(1, N + 1):
    if dic.get(i, False):
        dic[i] = sorted(dic[i])

# print('dic', dic, PY)
for i in range(M):
    p, y = PY[i]
    # print('p y', p, y)
    l = dic[p]
    ans = f(p) + f(bl(l, y) + 1)
    print(ans)
### BUGGY CODE ###

n, k = map(int,input().split())
p = list(map(int,input().split()))

ans = 0
for i in range(n-k+1):
    e = 0
    for j in range(0,k):
        e += (0.5*(p[i+j]+1))
    ans = max(ans,e)
print(ans)

### FIXED CODE ###

import numpy as np
n, k = map(int,input().split())
p = list(map(int,input().split()))

e = [(i+1)/2 for i in p]
e = np.cumsum(e)
e = np.append(0,e)
ans = 0
for i in range(n-k+1):
    ans = max(e[i+k]-e[i],ans)
print(ans)
### BUGGY CODE ###

nk = list(map(int, input().split()))
p = list(map(int, input().split()))
n = nk[0]
k = nk[1]
e = [(1+p[i])/2 for i in range(n)]
s = [sum(e[:i]) for i in range(n+1)]
ans = 0
for i in range(n-k+1):
    if (s[i+k]-s[i]) > ans:
        ans = s[i+k]-s[i]
print(ans)

### FIXED CODE ###

def main():    
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    s = sum(p[:k])
    maxs = s
    for i in range(n-k):
        s = s - p[i] + p[i+k]
        if s > maxs:
            maxs = s
    ans = (maxs+k)/2
    print(ans)
main()
### BUGGY CODE ###

N = int(input())
ans_list = []

for i in range(N):
    A = int(input())
    if A in ans_list:
        ans_list.remove(A)
    else:
        ans_list.append(A)

print(len(ans_list))

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())

# 集合　listよりも 検索などが高速
# 重複なしの順序も無し
ans_set = set()

for i in range(N):
    A = int(input())
    if A in ans_set:
        ans_set.remove(A)
    else:
        ans_set.add(A)

print(len(ans_set))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, M = list(map(int, input().split()))
D = list(map(int, input().split()))
UB = [list(map(int, input().split())) for _ in range(M)]

LL = [[-1] * 2 for _ in range(N)]
R = {}
for i in range(M):
  a, b = UB[i]
  a -= 1
  b -= 1
  if a not in R: R[a] = [[b, i]]
  else: R[a].append([b, i])
  if b not in R: R[b] = [[a, i]]
  else: R[b].append([a, i])
  if D[a] < D[b]:
    LL[b] = [a, i]
  else:
    LL[a] = [b, i]

DD = [[0] * 2 for _ in range(N)]
for i in range(N):
  DD[i][0] = D[i]
  DD[i][1] = i
DD.sort()
L = [0] * N
H = [0] * M

for i in range(N):
  h, x = DD[i]
  if L[x] == 0:
    if LL[x][0] == -1:
      for n, m in R[x]:
        LL[n] = [x, m]
        if D[n] == D[x] or L[n] != 0:
          H[m] = h
          if L[n] == 1:
            L[n] = 1
            L[x] = 2
          else:
            L[n] = 2
            L[x] = 1
          break
      else:
        print(-1)
        exit()
    else:
      n, m = LL[x]
      H[m] = h
      if L[n] == 1:
        L[n] = 1
        L[x] = 2
      else:
        L[n] = 2
        L[x] = 1

t = ""
for i in range(N):
  if L[i] == 1:
    t += "B"
  else:
    t += "W"
print(t)
for i in range(M):
  if H[i] == 0:
    print(10 ** 9)
  else:
    print(H[i])


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, M = list(map(int, input().split()))
D = list(map(int, input().split()))
UB = [list(map(int, input().split())) for _ in range(M)]

LL = [[-1] * 2 for _ in range(N)]
for i in range(M):
  a, b = UB[i]
  a -= 1
  b -= 1
  if D[a] < D[b]:
    LL[b] = [a, i]
  elif D[a] > D[b]:
    LL[a] = [b, i]
  else:
    LL[a] = [b, i]
    LL[b] = [a, i]

DD = [[0] * 2 for _ in range(N)]
for i in range(N):
  DD[i][0] = D[i]
  DD[i][1] = i
DD.sort()
L = [0] * N
H = [0] * M

for i in range(N):
  h, x = DD[i]
  if L[x] == 0:
    if LL[x][0] == -1:
      print(-1)
      exit()
    else:
      n, m = LL[x]
      H[m] = h
      if L[n] == 1:
        L[n] = 1
        L[x] = 2
      else:
        L[n] = 2
        L[x] = 1

for i in range(N):
  if L[i] == 1:
    L[i] = "B"
  else:
    L[i] = "W"
print("".join(list(map(str, L))))
for i in range(M):
  if H[i] == 0:
    print(10 ** 9)
  else:
    print(H[i])
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
box = [0]*(N+1)
for i in range(N) :
    box[A[i]] += 1

ans = list(map(lambda x: x*(x-1)//2 , box))
for j in range(N) :
    ans[A[j]] -= (box[A[j]] - 1)
    print(sum(ans))
    ans[A[j]] += (box[A[j]] - 1)
    


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
box = [0]*(N+1)
for i in range(N) :
    box[A[i]] += 1

x = list(map(lambda x: x*(x-1)//2 , box))
ans = sum(x)
for j in range(N) :
    print(ans-(box[A[j]] - 1))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
x = list(sorted(set(a)))
Li = -1
Ri = len(x) - 1
while Li + 1 < Ri:
    i = (Li + Ri) // 2
    xi = x[i]
    lr = []
    s = 0
    M = 0
    for ak in a:
        s += (ak > xi) * 2 - 1
        lr += [s]
        M += (s >= 0) * 2 - 1
    for l in range(1, n):
        for r in range(l, n):
            lr[r] -= lr[l - 1]
            M += (lr[r] >= 0) * 2 - 1
    if M >= 0:
        Li = i
    else:
        Ri = i
print(x[Ri])


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
x = list(sorted(set(a)))
n_sub = n * (n + 1) // 2
Li = 0
Ri = len(x)
while Ri > Li + 1:
    i = (Li + Ri) // 2
    xi = x[i]
    UorD = [1 if ak >= xi else -1 for ak in a]
    cnt_sum = [0] * (2 * n + 1)
    cumsum = 0
    cnt_sum[cumsum + n] = 1
    judge = 0
    s = 0
    for uk in UorD:
        cumsum += uk
        if uk == 1:
            s += cnt_sum[cumsum + n] + 1
        else:
            s -= cnt_sum[cumsum + n + 1] - 1
        cnt_sum[cumsum + n] += 1
        judge += s
        if judge >= n_sub // 2:
            Li = i
            break
    else:
        Ri = i
print(x[Li])
### BUGGY CODE ###

def f():
    # 入力から文字列を生成していく？
    s = input()
    t = input()
    ls, lt = len(s), len(t)
    dp = [[0] * (ls + 1) for _ in range(lt + 1)]
    for i in range(lt):
        for j in range(ls):
            if s[j] == t[i]:
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j])
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1])
    r = ''
    i += 1
    j += 1
    while (i > 0 and j > 0):
        if dp[i][j] == dp[i][j - 1]:
            j -= 1
        elif dp[i][j] == dp[i - 1][j]:
            i -= 1
        else:
            r = s[j - 1] + r
            j -= 1
            i -= 1
    return r


if __name__ == '__main__':
    ans = f()
    print(ans)

### FIXED CODE ###

def f():
    s = input()
    t = input()
    ls, lt = len(s), len(t)
    dp = [[0] * (ls + 1) for _ in range(lt + 1)]
    for i in range(lt):
        for j in range(ls):
            if s[j] == t[i]:
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j])
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1])
    r = ''
    i += 1
    j += 1
    while (i > 0 and j > 0):
        if dp[i][j] == dp[i][j - 1]:
            j -= 1
        elif dp[i][j] == dp[i - 1][j]:
            i -= 1
        else:
            r = s[j - 1] + r
            j -= 1
            i -= 1
    return r
 
 
if __name__ == '__main__':
    ans = f()
    print(ans)