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

#!/usr/bin/env python3
import sys, math, fractions, itertools, collections


def solve(N: int, s: "List[str]"):
    S = []
    for ss in s:
        ss = sorted(ss)
        S.append(''.join(ss))
    c = collections.Counter(S).values()
    s = 0
    for cc in c:
        s += len(list(itertools.combinations(range(cc), 2)))
    print(s)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    s = [ next(tokens) for _ in range(N) ]  # type: "List[str]"
    solve(N, s)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys, math, fractions, itertools, collections


def solve(N: int, s: "List[str]"):
    S = []
    for ss in s:
        ss = sorted(ss)
        S.append(''.join(ss))
    c = list(collections.Counter(S).values())
    s = 0
    for cc in c:
        s += cc*(cc-1)//2
    print(s)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    s = [ next(tokens) for _ in range(N) ]  # type: "List[str]"
    solve(N, s)

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

K = int(input())
if K % 2 == 0:
    print(-1)
    exit()
if K % 5 == 0:
    print(-1)
    exit()

x = 7
counter = 1
while (True):
    if x%K == 0:
        print(counter)
        exit()
    x += 7 * 10 ** counter
    counter += 1


### FIXED CODE ###

K = int(input())
if K%5 == 0 or K%2 == 0:
    print(-1)
    exit()
x = 7
counter = 1
while True:
    if x%K == 0:
        print(counter)
        exit()
    counter += 1
    x = (10 * x + 7) % K
### BUGGY CODE ###

N=int(input())
str_list = input().split(' ')
H = [int(x) for x in str_list]
max_count = 0
for ii in range(len(H)-1):
    count=0
    while H[ii+count]>=H[ii+count+1]:
        count += 1
        if ii+count>=len(H)-1:
            break
    if max_count < count:
        max_count = count
print(max_count)


### FIXED CODE ###

N=int(input())
str_list = input().split(' ')
H = [int(x) for x in str_list]
max_count = 0
count=0
for ii in range(len(H)-1):
    if H[ii] >= H[ii+1]:
        count += 1
    else:
        count = 0
    if max_count < count:
        max_count = count
    #if max_count + ii > len(H):
    #    break
print(max_count)
### BUGGY CODE ###

S=input()
l=len(S)
t=0
p=0
m=[[0] * l for i in range(l)]

for i in range(l):
    for j in range(l-i):
        m[i][j]=int(S[i])*(10**j)%2019

for i in range(l-1,2,-1):

    p=0
    for j in range(i+1):
        p=(p+m[i-j][j])%2019

        if p==0:

            t+=1

print(t)

### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())

grid = []
for i in range(H):
    grid.append(input().rstrip())

d = deque()
d.append((Ch-1, Cw-1, 0))

memo = [[[False] * W for _ in range(H)] for _ in range(1000)]
memo[0][Ch-1][Cw-1] = True

searched = [[False] * W for _ in range(H)]

ans = -1

while d:
    h, w, c = d.popleft()

    if searched[h][w]:
        continue

    searched[h][w] = True

    if h == Dh-1 and w == Dw-1:
        ans = c
        break

    for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        if 0 <= h+i < H and 0 <= w+j < W:
            if grid[h+i][w+j] == '.':
                if not memo[c][h+i][w+j]:
                    memo[c][h+i][w+j] = True
                    d.appendleft((h+i, w+j, c))

    for i in range(-2, 3):
        for j in range(-2, 3):
            if 0 <= h+i < H and 0 <= w+j < W:
                if grid[h+i][w+j] == '.':
                    if not memo[c][h+i][w+j] and not memo[c+1][h+i][w+j]:
                        memo[c+1][h+i][w+j] = True
                        d.append((h+i, w+j, c+1))

print(ans)


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())

grid = []
for i in range(H):
    grid.append(input().rstrip())

d = deque()
d.append((Ch-1, Cw-1, 0))

memo = [[[False] * W for _ in range(H)] for _ in range(2)]
memo[0][Ch-1][Cw-1] = True

searched = [[False] * W for _ in range(H)]

ans = -1

while d:
    h, w, c = d.popleft()

    if searched[h][w]:
        continue

    searched[h][w] = True

    if h == Dh-1 and w == Dw-1:
        ans = c
        break

    for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        if 0 <= h+i < H and 0 <= w+j < W:
            if grid[h+i][w+j] == '.':
                if not memo[0][h+i][w+j] and not searched[h+i][w+j]:
                    memo[0][h+i][w+j] = True
                    d.appendleft((h+i, w+j, c))

    for i in range(-2, 3):
        for j in range(-2, 3):
            if 0 <= h+i < H and 0 <= w+j < W:
                if grid[h+i][w+j] == '.':
                    if not memo[0][h+i][w+j] and not memo[1][h+i][w+j] and not searched[h+i][w+j]:
                        memo[1][h+i][w+j] = True
                        d.append((h+i, w+j, c+1))

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

N = int(input())
A = [int(input()) for i in range(N)]

ans = 1
X = [-1]
for i in range(N):
    for j in range(ans):
        if X[j] < A[i]:
            X[j] = A[i]
            break
        elif j == ans - 1:
            X.append(X[ans-1])
            for k in range(ans-1,0,-1):
                X[k] = X[k-1]
            ans += 1
            X[0] = A[i]

print(ans)


### FIXED CODE ###

import bisect

N = int(input())
A = [int(input()) for i in range(N)]

ans = 1
X = [-A[0]]
for i in range(1,N):
    if -X[ans-1] >= A[i]:
        X.append(-A[i])
        ans += 1
    else:
        pos = bisect.bisect_right(X,-A[i])
        X[pos] = -A[i]

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

n = int(input())
a,b = 0, n-1
print(0,flush=True)
s = str(input())
if s == 'Vacant':
    exit()
for i in (19):
    check = (a+b) // 2
    print(check,flush=True)
    t = str(input())
    if t == 'Vacant':
        exit()
    if (check-a) % 2 == 0 and s == t:
        a = check
    elif (check-a) % 2 == 0 and s != t:
        b = check
    elif (check-a) % 2 == 1 and s == t:
        b = check
    else:
        a,s = check,t


### FIXED CODE ###

n = int(input())
a,b = 0, n
print(a,flush=True)
s = str(input())
if s == 'Vacant':
        exit()
for i in range(19):
    check = (a+b) // 2
    print(check,flush=True)
    t = str(input())
    if t == 'Vacant':
        exit()
    if (check-a) % 2 == 0 and s == t:
        a = check
    elif (check-a) % 2 == 0 and s != t:
        b = check
    elif s == t:
        b = check
    else:
        a,s = check,t
### BUGGY CODE ###

import sys
from collections import deque
input=sys.stdin.readline


def solve():
    N, M = map(int, input().split())
    d = {i:[] for i in range(1, N+1)}

    used = set()
    for _ in range(N+M-1):
        A, B = map(int, input().split())
        d[A].append(B)
        used.add(B)

    root = (set(range(1, N+1))-used).pop()

    q = deque([(root, 0, 0)])
    parents = [0] * N
    dist = [0] * (N+1)

    while q:
        s, r, x = q.popleft()
        if x>dist[s] or r==0:
            dist[s] = x
            parents[s-1] = r
        else:
            continue
        for t in d[s]:
            q.append((t, s, x+1))

    for i in parents:
        print(i)


if __name__ == "__main__":
    solve()


### FIXED CODE ###

import sys
from collections import deque
input=sys.stdin.readline

N, M = map(int, input().split())
d = {i:[] for i in range(1, N+1)}
e = {i:[] for i in range(1, N+1)}

l = []
h = [0] * (N+1)

for _ in range(N+M-1):
    A, B = map(int, input().split())
    d[A].append(B)
    e[B].append(A)
    h[B] += 1

st = set()
for i in range(1, N+1):
    if h[i]==0:
        st.add(i)

l = []
while st:
    i = st.pop()
    l.append(i)
    for j in d[i]:
        h[j] -= 1
        if h[j] == 0:
            st.add(j)

tp = {j:i for i,j in enumerate(l, start=1)}
ans = [0] * (N+1)
for i in range(1, N+1):
    s, t = 0, 0
    for j in e[i]:
        if s < tp[j]:
            s = tp[j]
            t = j
    print(t)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
q=int(input())
b=[0]*q
c=[0]*q
s=[0]*(q+1)
for i in range(q):
	b[i],c[i]=map(int,input().split())
f={}
for i in range(n):
	f.setdefault(a[i],[])
for i in range(n):
	f[a[i]].append(i)
for g,h in f.items():
	#print(len(h)*g)
	s[0]=s[0]+len(h)*g
#print(f)
for i in range(1,q+1):
	if b[i-1] in f:
		if c[i-1] in f:
			f[c[i-1]]=f[c[i-1]]+f[b[i-1]]
			s[i]=s[i-1]-len(f[b[i-1]])*b[i-1]
			#print(s[i])
			
			s[i]=s[i]+len(f[b[i-1]])*c[i-1]
			f.pop(b[i-1])
		else:
			f.setdefault(c[i-1],[])
			f[c[i-1]]=f[c[i-1]]+f[b[i-1]]
			s[i]=s[i-1]-len(f[b[i-1]])*b[i-1]
			#print(s[i])
			
			s[i]+=len(f[b[i-1]])*c[i-1]
			f.pop(b[i-1])
	#print(f)
	#for g,h in f.items():
		#print(len(h)*g)
		#s[i]=s[i]+len(h)*g
	else:
		s[i]=s[i-1]
	print(s[i])


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
q=int(input())
b=[0]*q
c=[0]*q
s=[0]*(q+1)
for i in range(q):
	b[i],c[i]=map(int,input().split())
f={}
for i in range(n):
	f.setdefault(a[i],0)
for i in range(n):
	f[a[i]]+=1
for g,h in f.items():
	#print(len(h)*g)
	s[0]=s[0]+h*g
#print(f)
for i in range(1,q+1):
	if b[i-1] in f:
		if c[i-1] in f:
			f[c[i-1]]=f[c[i-1]]+f[b[i-1]]
			s[i]=s[i-1]-f[b[i-1]]*b[i-1]
			#print(s[i])
			
			s[i]=s[i]+f[b[i-1]]*c[i-1]
			f.pop(b[i-1])
		else:
			f.setdefault(c[i-1],0)
			f[c[i-1]]=f[c[i-1]]+f[b[i-1]]
			s[i]=s[i-1]-f[b[i-1]]*b[i-1]
			#print(s[i])
			
			s[i]+=f[b[i-1]]*c[i-1]
			f.pop(b[i-1])
	#print(f)
	#for g,h in f.items():
		#print(len(h)*g)
		#s[i]=s[i]+len(h)*g
	else:
		s[i]=s[i-1]
	print(s[i])
### BUGGY CODE ###

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

m = [[0]*n for _ in range(n)]
dp = [-1]*n
from collections import deque
for _ in range(M):
  a,b = list(map(int,input().split()))
  a -= 1
  b -= 1
  m[a][b] = 1
  m[b][a] = 1

que = deque([0])
dp[0] = 0

while que:
  c = que.popleft()
  for i in range(n):
    if m[c][i] == 1:
      if dp[i] != -1 :continue
      dp[i] = c+1
      que.append(i)

#[exit(print('No')) for i in range(1,n)  if dp[i] == 0]

print('Yes')
[print(dp[i]) for i in range(1,n)]


### FIXED CODE ###

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

m = [[] for _ in range(n)]
dp = [0]*n
from collections import deque
que = deque()
for _ in range(M):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  m[a].append(b)
  m[b].append(a)
  if a == 0:
    que.append(b)
    dp[b] = 1
  if b == 0:
    que.append(a)
    dp[a] = 1

while que:
  c = que.popleft()
  for i in m[c]:
    if dp[i] == 0 :
      dp[i] = c+1
      que.append(i)

#[exit(print('No')) for i in range(1,n)  if dp[i] == 0]

print('Yes')
[print(dp[i]) for i in range(1,n)]
### BUGGY CODE ###

from collections import deque
import sys
imput = sys.stdin.readline


diff = ((0, 1), (0, -1), (1, 0), (-1, 0))
n = int(input())
p = list(map(int, input().split()))

cost = [0] * (n * n)
for i in range(n):
    for j in range(n):
        cost[i * n + j] = min(i, j, n - i - 1, n - j - 1) + 1

occ = [True] * (n * n)
ans = 0
for start in p:
    start -= 1
    q = deque([start])
    ans += cost[start] - 1
    occ[start] = False

    while q:
        ij = q.popleft()
        i, j = divmod(ij, n)
        for di, dj in diff:
            nxt_i = i + di
            nxt_j = j + dj
            nxt_ij = nxt_i * n + nxt_j
            if not(0 <= nxt_i < n and 0 <= nxt_j < n):
                continue
            elif not occ[ij] and cost[nxt_ij] > cost[ij]:
                cost[nxt_ij] = cost[ij]
                q.append(nxt_ij)
            elif cost[nxt_ij] > cost[ij] + 1:
                cost[nxt_ij] = cost[ij] + 1
                q.append(nxt_ij)
print(ans)

### FIXED CODE ###

from collections import deque
import sys
imput = sys.stdin.readline


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

cost = [0] * (n * n)
for i in range(n):
    for j in range(n):
        cost[i * n + j] = min(i, j, n - i - 1, n - j - 1)

occ = [True] * (n * n)
ans = 0
for start in p:
    start -= 1
    q = deque([start])
    ans += cost[start]
    occ[start] = False
    while q:
        ij = q.popleft()
        i, j = divmod(ij, n)

        nxt_ij = (i + 1) * n + j
        if not(0 <= i + 1 < n and 0 <= j < n):
             pass
        elif not occ[ij] and cost[nxt_ij] > cost[ij]:
            cost[nxt_ij] = cost[ij]
            q.append(nxt_ij)
        elif cost[nxt_ij] > cost[ij] + 1:
            cost[nxt_ij] = cost[ij] + 1
            q.append(nxt_ij)
              
        nxt_ij = (i - 1) * n + j
        if not(0 <= i - 1 < n and 0 <= j < n):
            pass
        elif not occ[ij] and cost[nxt_ij] > cost[ij]:
            cost[nxt_ij] = cost[ij]
            q.append(nxt_ij)
        elif cost[nxt_ij] > cost[ij] + 1:
            cost[nxt_ij] = cost[ij] + 1
            q.append(nxt_ij)

        nxt_ij = i * n + (j + 1)
        if not(0 <= i + 0 < n and 0 <= j + 1 < n):
            pass
        elif not occ[ij] and cost[nxt_ij] > cost[ij]:
            cost[nxt_ij] = cost[ij]
            q.append(nxt_ij)
        elif cost[nxt_ij] > cost[ij] + 1:
            cost[nxt_ij] = cost[ij] + 1
            q.append(nxt_ij)

        nxt_ij = i * n + (j - 1)
        if not(0 <= i < n and 0 <= j - 1 < n):
            pass
        elif not occ[ij] and cost[nxt_ij] > cost[ij]:
            cost[nxt_ij] = cost[ij]
            q.append(nxt_ij)
        elif cost[nxt_ij] > cost[ij] + 1:
            cost[nxt_ij] = cost[ij] + 1
            q.append(nxt_ij)
print(ans)
### BUGGY CODE ###

def can_make_one(n, k):
    while True:
        if n % k == 0:
            n = n // k
        else:
            n = n - k
        if n == 1:
            return True
        elif n < 1:
            return False
n = int(input())
#o: 2, n-1, n
#x: n//2+1 ~ n-2
cnt = 3
if n == 2:
    print(1)
elif n == 3:
    print(2)
elif n == 4 or n == 5:
    print(3)
else:
    for i in range(3, n//2+1):
        if can_make_one(n, i):
            cnt += 1
    print(cnt)

### FIXED CODE ###

import math

def get_divisor(n):
    sn = math.sqrt(n)
    i = 1
    divisor = []
    while i <= sn:
        if n % i == 0:
            divisor.append(i)
            if i != n // i:
                divisor.append(n // i)
        i += 1
    return divisor

n = int(input())
if n == 2:
    print(1)
    exit()
d1 = get_divisor(n)
d2 = get_divisor(n - 1)
ans = -1
for i in d1:
    tmp = int(n)
    if i == 1:
        continue
    while tmp % i == 0:
        tmp //= i
    if tmp % i == 1:
        ans += 1
ans += len(d2)
print(ans)
### BUGGY CODE ###

C=10**100
S=input()
SL=list(S[i] for i in range(len(S)))#床の情報
BL=list(1 for i in range(len(S)))
CL=list(i for i in range(len(S))) #子供の座標
for i in range(C):
  
  for child in range(len(S)):
    houkou=SL[CL[child]]
    if houkou=="L":
      CL[child]=CL[child]-1
    else:
      CL[child]=CL[child]+1
for i in range(len(S)):
  BL[i]=CL.count(i)
print(BL)

### FIXED CODE ###

S=input()
TL=len(S)
SL=list(S[i] for i in range(TL))#床の情報
BL=[0]*TL
ans=[0]*TL #子供の座標
cnt=0
for j in range(2):
  for i in range(TL):
    
    if SL[i]=="R":
      cnt=cnt+1
    else:
      ans[i]=ans[i]+cnt//2
      ans[i-1]=ans[i-1]+(cnt+1)//2
      cnt=0
    
  SL.reverse()
  ans.reverse()
  for i in range(TL):
    if SL[i]=="R":
      SL[i]="L"
    else:
      SL[i]="R" 
for i in range(TL):
  print(ans[i])
### BUGGY CODE ###

N = int(input())

A = []
for i in range(N):
    a = int(input())
    A.append(a)

ma = 0
for i in range(N-1):
    print(max(ma, max(A[i+1:])))
    ma = max(ma, A[i])

print(ma)


### FIXED CODE ###

N = int(input())

A = []
for i in range(N):
    a = int(input())
    A.append([a, i])
    
A_ = sorted(A, reverse=True)

#print(A_)

for i in range(N):
    if A_[0][1] == i:
        print(A_[1][0])
    else:
        print(A_[0][0])
### BUGGY CODE ###

import numpy as np


n = int(input())
arr = np.array(list(map(int, input().split())))


n = 10**3 + 1
primes = set(range(3, n+1, 2))

for i in range(3, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes.add(2)

used = [False] * 1002
ans1 = True
flg = False
for x in arr:
    for p in primes:
        while x > 1 and x % p == 0:
            if used[p]:
                ans1 = False
                flg = True
                break
            while x % p == 0:
                x //= p
            used[p] = True
        if flg:
            break
    if flg:
        break


ans2 = np.gcd.reduce(arr) == 1

if ans1 and ans2:
    print("pairwise coprime")
elif ans2:
    print("setwise coprime")
else:
    print("not coprime")

### FIXED CODE ###

import numpy as np
from numba import njit


n = int(input())
arr = np.array(list(map(int, input().split())))


n = 10**6 + 1
primes = set(range(3, n+1, 2))

for i in range(3, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes.add(2)


@njit
def solve(arr, primes):
    cnt = np.bincount(arr)
    for p in primes:
        if (cnt[p::p]).sum() > 1:
            return False
    else:
        return True


if np.gcd.reduce(arr) != 1:
    print("not coprime")
elif solve(arr, primes):
    print("pairwise coprime")
else:
    print("setwise coprime")
### BUGGY CODE ###

n=int(input())
a=[0]*n;b=a[:]
for i in range(n):
  c,d=map(int,input().split())
  a[i]=c;b[i]=d
ans=0
for i in range(n)[::-1]:
  a[i]+=ans
  while a[i]%b[i]!=0:
    a[i]+=1
    ans+=1
print(ans)


### FIXED CODE ###

n=int(input())
a=[0]*n;b=a[:]
for i in range(n):
  c,d=map(int,input().split())
  a[i]=c;b[i]=d
ans=0
for i in range(n)[::-1]:
  a[i]+=ans
  if a[i]%b[i]==0:continue
  ans+=b[i]-(a[i]%b[i])
print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
 
for i in range(1,n+1):
    print(a.index(i)+1)
 

### FIXED CODE ###

from operator import itemgetter
n=int(input())
a=list(map(int,input().split()))

print(*[t[0] +1 for t in sorted(enumerate(a),key=itemgetter(1))])
### BUGGY CODE ###

n=int(input())
d=[]
ans=0
for i in range(n):
    tmp=[int(j) for j in input().split()]
    d.append(tmp)
for i in range(n):
    for j in range(i+1,n):
        ans+=d[i][j]

for i in range(n):
    for j in range(i+1,n):
        for k in range(n):
            if i==k or j==k:
                continue
            if d[i][j]>d[i][k]+d[k][j]:
                print(-1)
                exit()
            elif d[i][j]==d[i][k]+d[k][j]:
                ans-=d[i][j]
                break
print(ans)


### FIXED CODE ###

n=int(input())
d=[]
ans=0
for i in range(n):
    tmp=[int(j) for j in input().split()]
    d.append(tmp)
for i in range(n):
    for j in range(i+1,n):
        ans+=d[i][j]

for i in range(n):
    for j in range(i+1,n):
        for k in range(n):
            if i==k or j==k:
                continue
            if d[i][j]>d[i][k]+d[k][j]:
                print(-1)
                exit()
            elif d[i][j]==d[i][k]+d[k][j]:
                ans-=d[i][j]
                break
print(ans)
### BUGGY CODE ###

import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
# import numpy as np
starttime = time.time()
# import numpy as np
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

try:
    sys.setrecursionlimit(int(pow(10,6)))
    sys.stdin = open("input.txt", "r")
    # sys.stdout = open("../output.txt", "w")
except:
    pass


s=input()
t=input()
global x,ans
x=[]
ans=[]
def rec(i,j):
    global x,ans
    if len(x)>len(ans):
        ans=x[::]
    if len(x)+min(abs(i-len(s)),abs(j-len(t)))<len(ans):
        return
    if i>=len(s) or j>=len(t):
        return
    if s[i]==t[j]:
        x.append(s[i])
        rec(i+1,j+1)
        x.pop()
        return
    rec(i+1,j)
    rec(i,j+1)
rec(0,0)
print("".join(ans))


endtime = time.time()
# print(f"Runtime of the program is {endtime - starttime}")



### FIXED CODE ###

from subprocess import*
call(('pypy3','-c',"""
s=input()
t=input()
a=len(s)
b=len(t)
dp=[[0]*(b+1) for i in range(a+1)]
for i in range(a):
  for j in range(b):
    if s[i]==t[j]:
      dp[i+1][j+1]=dp[i][j]+1
    else:
      dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
res=''
while a!=0 and b!=0:
  if dp[a][b]==dp[a-1][b]:
    a-=1
  elif dp[a][b]==dp[a][b-1]:
    b-=1
  else:
    a-=1
    b-=1
    res=s[a]+res
print(res)
"""))
"""
from subprocess import*
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
# import numpy as np
starttime = time.time()
# import numpy as np
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

try:
    # sys.setrecursionlimit(int(pow(10,6)))
    # sys.stdin = open("input.txt", "r")
    # sys.stdout = open("../output.txt", "w")
except:
    pass

"""