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

from collections import deque
import sys
input = sys.stdin.readline
h, w, k = map(int, input().split())
x1, y1, x2, y2 = [int(a) - 1 for a in input().split()]
c = [input() for _ in range(h)]

inf = 10 ** 8
d = [inf for _ in range(h*w)]
move = [(1, 0), (0, 1), (-1, 0), (0, -1)]


que = deque()
for i in range(4):
    d[x1*w+y1] = 0
    que.append((x1, y1))
    
while len(que):
    cur_x, cur_y = que.popleft()
    if cur_x == x2 and cur_y == y2:
        break
    for dx, dy in move:
        to_x, to_y = cur_x, cur_y
        for _ in range(k):
            to_x += dx
            to_y += dy
            if 0 <= to_x < h and 0 <= to_y < w and c[to_x][to_y] == '.' and d[to_x*w+to_y] > d[cur_x*w+cur_y]:
                    d[to_x*w+to_y] = d[cur_x*w+cur_y] + 1
                    que.append((to_x, to_y))
            else:
                break


print(-1 if d[x2*w+y2] == inf else d[x2*w+y2])

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
h, w, k = map(int, input().split())
x1, y1, x2, y2 = [int(a) - 1 for a in input().split()]
c = [input() for _ in range(h)]

inf = 10 ** 8
d = [[inf for _ in range(w)] for _ in range(h)]
move = [(1, 0), (0, 1), (-1, 0), (0, -1)]


que = deque()
for i in range(4):
    d[x1][y1] = 0
    que.append((x1, y1))
    
while len(que):
    cur_x, cur_y = que.popleft()
    if cur_x == x2 and cur_y == y2:
        break
    for dx, dy in move:
        to_x, to_y = cur_x, cur_y
        for _ in range(k):
            to_x += dx
            to_y += dy
            if 0 <= to_x < h and 0 <= to_y < w and c[to_x][to_y] == '.':
                if d[to_x][to_y] > d[cur_x][cur_y] + 1:
                    d[to_x][to_y] = d[cur_x][cur_y] + 1
                    que.append((to_x, to_y))
                elif d[to_x][to_y] == d[cur_x][cur_y] + 1:
                    continue
                else:
                    break
            else:
                break


print(-1 if d[x2][y2] == inf else d[x2][y2])
### BUGGY CODE ###

import itertools
import math
import functools

k = int(input())
li = [i for i in range(1,k+1)]
all_li = list(itertools.product(li, repeat=3))
ans = 0
for a in all_li:
    ans += functools.reduce(math.gcd, a)
print(ans)

### FIXED CODE ###

import math
k = int(input())
count = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for k in range(1,k+1):
            tmp = math.gcd(i,j)
            count += math.gcd(tmp,k)
print(count)
### BUGGY CODE ###

Q=int(input())
A=[list(map(int,input().split())) for i in range(Q)]
B,C=zip(*A)
a=max(max(B),max(C))
def get_primenumber(N):
  prime_list=[2]
  for num in range(3,N+1,2):
    if all(num%prime != 0 for prime in prime_list):
      prime_list.append(num)
  return prime_list

X=get_primenumber(a)
P=[False]*(a+1)
L=[False]*(a+1)
for i in X:
  P[i]=True
for i in X:
  if P[(i+1)//2]:
    L[i]=True
C=[]
c=0
for i in range(a+1):
  if L[i]:
    c+=1
  C.append(c)
for s,t in A:
  print(C[t]-C[s-1])

### FIXED CODE ###

Q=int(input())
A=[list(map(int,input().split())) for i in range(Q)]
B,C=zip(*A)
a=max(max(B),max(C))
def get_primenumber(N):
  prime_list=[2]
  for num in range(3,N+1,2):
    if all(num%prime != 0 for prime in prime_list):
      prime_list.append(num)
  return prime_list

X=get_primenumber(a)
P=[False]*(a+1)
L=[False]*(a+1)
for i in X:
  P[i]=True
for i in X:
  if P[(i+1)//2]:
    L[i]=True
C=[]
c=0
for i in range(a+1):
  if L[i]:
    c+=1
  C.append(c)
for s,t in A:
  print(C[t]-C[s-1])
### BUGGY CODE ###

from collections import deque
N, Q = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(N-1)]
operations = [list(map(int, input().split())) for _ in range(Q)]

edge_map = {}
for i in range(N):
    edge_map[i] = deque([])

for edge in edges:
    a = edge[0]
    b = edge[1]
    edge_map[a-1].append(b-1)
    edge_map[b-1].append(a-1)


counters = [0 for i in range(N)]

for operation in operations:
    p = operation[0]
    x = operation[1]
    counters[p-1] += x


res_list = [counters[i] for i in range(N)]
calculated = [False for i in range(N)]

def dfs_res(idx, parent, diff):
    global res_list
    global counters
    if calculated[i]:
        return res_list[idx]
    res = counters[idx] + diff
    res_list[idx] = res
    calculated[idx] = True
    for child in edge_map[idx]:
        if child == parent:
            continue
        dfs_res(child, idx, res)
    return

dfs_res(0, None, 0)

ans = ""
for res in res_list:
    ans += str(res) + " "
print(ans)

### FIXED CODE ###

from collections import deque
N, Q = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(N-1)]
operations = [list(map(int, input().split())) for _ in range(Q)]

edge_map = [[] for i in range(N)]

for edge in edges:
    a = edge[0]
    b = edge[1]
    edge_map[a-1].append(b-1)
    edge_map[b-1].append(a-1)


counters = [0]*N

for operation in operations:
    p = operation[0]
    x = operation[1]
    counters[p-1] += x


res_list = [counters[i] for i in range(N)]
calculated = [False for i in range(N)]

target = [0]
while len(target) > 0:
    t = target.pop()
    calculated[t] = True
    for child in edge_map[t]:
        if calculated[child]:
            continue
        target.append(child)
        res_list[child] += res_list[t]

print(*res_list)
### BUGGY CODE ###

# B Frog 2

n, k = map(int, input().split())
h_list = [int(x) for x in input().split()]

dp = [float('Inf')] * n
dp[0] = 0

for i in range(1,n,1):
    _step = max(0,i-k)
    for j in range(_step,i,1):
        dp[i] = min(dp[i], dp[j] + abs(h_list[i]-h_list[j]))

print(dp[n-1])

### FIXED CODE ###

# B Frog 2

n, k = map(int, input().split())
h_list = [int(x) for x in input().split()]

dp = [float('Inf')] * n
dp[0] = 0

for i in range(n):
    for j in range(1,k+1,1):
        if i - j < 0:
            continue
        dp[i] = min(dp[i], dp[i-j] + abs(h_list[i-j]-h_list[i]))

        
print(dp[n-1])
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import defaultdict
n=int(input())
s=input()
count=0
for le in range(1,n-1):
    mojiretu=defaultdict(int)
    for i in range(n-le+1):
        j=i+le
        if 0<mojiretu[s[i:j]]<=i:
            count=max(count,le)
            break
        else:mojiretu[s[i:j]]=j
print(count)


### FIXED CODE ###

N=int(input())
S=input()

class RollingHash():
    BASE1 = 1007
    BASE2 = 2009
    MOD1 = 1000000007
    MOD2 = 1000000009
 
    def __init__(self, s, opt=2):
        self.n = len(s)
        self.opt = opt
        self.hash1 = [0] * (self.n + 1)
        self.power1 = [1] * (self.n + 1)
        if opt == 2:
            self.hash2 = [0] * (self.n + 1)
            self.power2 = [1] * (self.n + 1)
        for i, e in enumerate(s):
            self.hash1[i + 1] = (self.hash1[i] * self.__class__.BASE1 + ord(e)) % self.__class__.MOD1
            self.power1[i + 1] = (self.power1[i] * self.__class__.BASE1) % self.__class__.MOD1
            if opt == 2:
                self.hash2[i + 1] = (self.hash2[i] * self.__class__.BASE2 + ord(e)) % self.__class__.MOD2
                self.power2[i + 1] = (self.power2[i] * self.__class__.BASE2) % self.__class__.MOD2
 
    def get(self, l: int, r: int):
        res1 = self.hash1[r] - self.hash1[l] * self.power1[r - l] % self.__class__.MOD1
        if(res1 < 0):
            res1 += self.__class__.MOD1
        if self.opt == 2:
            res2 = self.hash2[r] - self.hash2[l] * self.power2[r - l] % self.__class__.MOD2
            if(res2 < 0):
                res2 += self.__class__.MOD2
        return (res1, res2) if self.opt == 2 else res1


    
rh = RollingHash(S, opt=1)

def check(n: int):
    d = dict()
    for i in range(N - n + 1):
        p = rh.get(i, i + n)
        if p in d.keys():
            if(i - d[p] >= n):
                return True
        else:
            d[p] = i
    return False
    
ok, ng = 0, N // 2 + 1
while ng - ok > 1:
    mid = (ok + ng) // 2
    if check(mid):
        ok = mid
    else:
        ng = mid
print(ok)
### BUGGY CODE ###

S=input()
T=input()
Skey=sorted(S,key=S.index)
Tkey=sorted(T,key=T.index)

for index,i in enumerate(Skey):
  S=S.replace(i,str(index))
for index,i in enumerate(Tkey):
  T=T.replace(i,str(index))

if S==T:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

S = input()
T = input()

Skey = sorted(set(S),key=S.index)
Tkey = sorted(set(T),key=T.index)

for idx,i in enumerate(Skey):
  S = S.replace(i,str(idx))
for idx,i in enumerate(Tkey):
  T = T.replace(i,str(idx))

if S==T:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

import sys
sys.getrecursionlimit()

n, m = map(int, input().split())

graph1 = [[] for _ in range(n)]
graph2 = [[] for _ in range(n)]

for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph1[u].append((1, v))


def dfs(v0, v, k):
    if k == 0:
        graph2[v0].append((1, v))
        return

    for i in range(len(graph1[v])):
        dfs(v0, graph1[v][i][1], k-1)

for i in range(n):
    dfs(i, i, 3)
    # print(graph1[i])

for i in range(n):
    graph2[i] = list(set(graph2[i]))
# print()
# for i in range(n):
#     print(graph2[i])


s, t = map(int, input().split())
s -= 1
t -= 1


from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    # graph[node] = [(cost, to)]
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist
    # dist = [costs to nodes]

inf = float('inf')
dist = dijkstra(graph2, n, s)
if dist[t] == inf:
    print(-1)
else:
    print(dist[t])


### FIXED CODE ###

n, m = map(int, input().split())

graph1 = [[] for _ in range(n*3)]

for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph1[u*3+0].append(v*3+1)
    graph1[u*3+1].append(v*3+2)
    graph1[u*3+2].append(v*3+0)

s, t = map(int, input().split())
s -= 1
t -= 1
s = s*3
t = t*3

from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    # graph[node] = [(cost, to)]
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    NextCost = 1
    while heap:
        cost,thisNode = heappop(heap)
        for NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist
    # dist = [costs to nodes]

inf = float('inf')
dist = dijkstra(graph1, n*3, s)
if dist[t] == inf:
    print(-1)
else:
    print(dist[t]//3)
### BUGGY CODE ###

N = int(input())
students = [int(x) for x in input().split()]
turns = [str(students.index(x) + 1) for x in range(1, N + 1) ]
print(' '.join(turns))

### FIXED CODE ###

# coding: utf-8
N = int(input())
student_list = [0] * (N + 1)
turn_list = [int(x) for x in input().split()]

for i, s in enumerate(turn_list):
    student_list[s] = i + 1
student_list.pop(0)
for s in student_list:
    print(str(s), end=' ')
print()
### BUGGY CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N = int(readline())
    A = [[int(i) for i in readline().split()] for _ in range(N)]

    via_min = [[10**15] * N for _ in range(N)]

    ans = 0
    for i in range(N-1):
        for j in range(i+1,N):
            d = A[i][j]
            flag = True
            for k in range(N):
                if k == i or k == j:
                    continue
                
                tmp = A[i][k] + A[k][j]
                if tmp < d:
                    print(-1)
                    exit()
                
                elif tmp == d:
                    flag = False
                    break
            if flag:
                ans += d
    
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N = int(readline())
    A = [[int(i) for i in readline().split()] for _ in range(N)]

    via_min = [[10**15] * N for _ in range(N)]

    for i in range(N):
        for j in range(N):
            for k in range(N):
                if k == i or k == j:
                    continue
                via_min[i][j] = min(via_min[i][j], A[i][k] + A[k][j]) 

    ans = 0
    for i in range(N):
        for j in range(i+1,N):
            if via_min[i][j] < A[i][j]:
                print(-1)
                exit()
            elif via_min[i][j] == A[i][j]:
                continue
            else:
                ans += A[i][j]
    
    print(ans)


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

N, M = map(int, input().split())
As = list(map(int, input().split()))
As.sort()
for m in range(M):
  B, C = map(int, input().split())
  count = 0
  for i in range(B):
    if As[i] < C:
      count += 1
    else:
      break
  As[0:count] = []
  #print(As)
  index = N-count
  for i in range(N-count):
    if As[i] > C:
      index = i
      break
  As[index:index] = [C]*count
  #print(As)
print(sum(As))


### FIXED CODE ###

N, M = map(int, input().split())
As = list(map(int, input().split()))
As.sort()
BCs = []
for m in range(M):
  B, C = map(int, input().split())
  BCs.append((B, C))
BCs.sort(key=lambda BC: -BC[1])
#print(BCs)

index = 0
for m in range(M):
  B, C = BCs[m]
  for i in range(B):
    if index >= N:
      break
    if As[index] < C:
      As[index] = C
      index += 1
    else:
      break
print(sum(As))
### BUGGY CODE ###

class Node:
    def __init__(self, x, y):
        self.id = x
        self.k = y
        self.children = []
        self.type = ''
        self.depth = 20
        self.parent = '-1'

def findRoot(tree):
    for x in tree:
        for y in x.children:
            for a in tree:
                if y == a.id:
                    if a.k == 0:
                        a.type = 'leaf'
                    else:
                        a.type = 'internal node'
                    a.parent = x.id
    for i,x in enumerate( tree):
        if x.type == 'root':
            return i


def setd(tree,node,d):
    node.depth = d
    if node.k == 0:
        return
    else:
        for tmp in node.children:
            setd(tree,tree[int(tmp)],d+1)
            '''for x in tree:
                if x.id == tmp:
                    setd(tree,x,d+1)
            '''


if __name__ == '__main__':
    n = (int)(input())
    tree = [None]*n
    for i in range(0,n):
        tmp = input().split()
        a = Node(tmp[0],(int)(tmp[1]))
        a.children=tmp[2:]
        a.type = 'root'
        tree[int(a.id)] = a
    ri = findRoot(tree)
    setd(tree,tree[ri],0)
    
    for tmp in tree:
        print("node {}: parent = {}, depth = {}, {}, {}".format(tmp.id, tmp.parent,tmp.depth,tmp.type,list(map(int,tmp.children))))

    

### FIXED CODE ###

class Node:
    def __init__(self, x, y):
        self.id = x
        self.k = y
        self.children = []
        self.type = ''
        self.depth = 20
        self.parent = '-1'

def findRoot(tree):
    for x in tree:
        for y in x.children:
            tree[int(y)].parent = x.id
            if tree[int(y)].k == 0:
                tree[int(y)].type = 'leaf'
            else:
                tree[int(y)].type = 'internal node'
            '''for a in tree:
                if y == a.id:
                    if a.k == 0:
                        a.type = 'leaf'
                    else:
                        a.type = 'internal node'
                    a.parent = x.id
            '''
    for i,x in enumerate( tree):
        if x.type == 'root':
            return i


def setd(tree,node,d):
    node.depth = d
    if node.k == 0:
        return
    else:
        for tmp in node.children:
            setd(tree,tree[int(tmp)],d+1)
            '''for x in tree:
                if x.id == tmp:
                    setd(tree,x,d+1)
            '''


if __name__ == '__main__':
    n = (int)(input())
    tree = [None]*n
    for i in range(0,n):
        tmp = input().split()
        a = Node(tmp[0],(int)(tmp[1]))
        a.children=tmp[2:]
        a.type = 'root'
        tree[int(a.id)] = a
    ri = findRoot(tree)
    setd(tree,tree[ri],0)
    
    for tmp in tree:
        print("node {}: parent = {}, depth = {}, {}, {}".format(tmp.id, tmp.parent,tmp.depth,tmp.type,list(map(int,tmp.children))))
### BUGGY CODE ###

#E
from collections import Counter
n,p=map(int,input().split())
s=input()
cnt=0

if p==2 or p==5:
    for i in range(n):
        if int(s[i])%p==0:
            cnt+=i+1
else:
    U=[0]*(n+1)
    for i in range(n,0,-1):
        U[i-1]=(int(s[i-1])*10**(n-i)+U[i])%p
    #print(U)
    C=Counter(U)
    for c in C.values():
        cnt+=c*(c-1)//2

print(cnt)

### FIXED CODE ###

#E
from collections import Counter
n,p=map(int,input().split())
s=input()
cnt=0

if p==2 or p==5:
    for i in range(n):
        if int(s[i])%p==0:
            cnt+=i+1
else:
    U=[0]*(n+1)
    for i in range(n,0,-1):
        U[i-1]=(int(s[i-1])*pow(10,n-i,p)+U[i])%p
    #print(U)
    C=Counter(U)
    for c in C.values():
        cnt+=c*(c-1)//2

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

import collections

H, W, M = map(int, input().split())

h, w = [0]*M, [0]*M
for i in range(M):
    h[i], w[i] = map(int, input().split())

counter = collections.Counter(h)
h_max = max(counter.values())
mode_h = [key for key , value in counter.items() if value == h_max]
counter = collections.Counter(w)
w_max = max(counter.values())
mode_w = [key for key , value in counter.items() if value == w_max]

ans = 0
for i in mode_h:
    for j in mode_w:
        if ans == H + W - 1:
            print(ans)
            exit()
        if ans < h.count(i) + w.count(j):
            ans = h.count(i) + w.count(j)
            for k in range(M):
                if h[k] == i and w[k] == j:
                    ans -= 1

print(ans)

### FIXED CODE ###

import collections
H, W, M = map(int, input().split())

h, w = [0]*M, [0]*M
dic = set()
for i in range(M):
    h[i], w[i] = map(int, input().split())
    dic.add((h[i],w[i]))

counter = collections.Counter(h)
h_max = max(counter.values())
mode_h = [key for key , value in counter.items() if value == h_max]
counter = collections.Counter(w)
w_max = max(counter.values())
mode_w = [key for key , value in counter.items() if value == w_max]

for i in mode_h:
    for j in mode_w:
        if (i,j) not in dic:
            print(h_max+w_max)
            exit()

print(h_max+w_max-1)
### BUGGY CODE ###

import heapq
N, M = map(int, input().split())
h = []
for i in input().split():
    heapq.heappush(h, int(i))

for i in range(M):
    b, c = map(int, input().split())
    for j in range(b):
        heapq.heappushpop(h, c)

print(sum(h))



### FIXED CODE ###

import heapq
N, M = map(int, input().split())
h = []
for i in input().split():
    heapq.heappush(h, int(i))
data = [list(map(int, input().split())) for _ in range(M)]
data = sorted(data, reverse=1, key=lambda x: x[1])
for b, c in data:
    for j in range(b):
        a = heapq.heappushpop(h, c)
        if a == c:
            print(sum(h))
            exit()
print(sum(h))
### BUGGY CODE ###

n,a=map(int,input().split())
arr=list(map(int,input().split()))
x=max(arr)
x=max(x,a)
dp=[[[0 for i in range(n*x+1)] for j in range(n+1)] for k in range(n+1)]
dp[0][0][0]=1
for i in range(1,n+1):
  xi=arr[i-1]
  for j in range(n+1):
    for k in range(n*x+1):
      if k<xi:
        dp[i][j][k]=dp[i-1][j][k]
      else:
        if j>=1:
          dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-xi]
ans=0
for i in range(1,n+1):
  ans+=dp[n][i][i*a]
print(ans)

### FIXED CODE ###

n,a=map(int,input().split())
arr=list(map(int,input().split()))
l=n*max(a,max(arr))
dp=[[[0]*(l+1) for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0]=1
for i in range(1,n+1):
  xi=arr[i-1]
  for j in range(0,i+1):
    for k in range(0,l+1):
      if k<xi:
        dp[i][j][k]=dp[i-1][j][k]
      elif j>=1:
        dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-xi]
ans=0
for i in range(1,n+1):
  ans+=dp[n][i][i*a]
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

H, W = map(int, input().split())
G = [[i for i in input()] for j in range(H)]

ls = []
dp = [[-1 for i in range(W)] for j in range(H)]
for h in range(H):
    for w in range(W):
        if G[h][w] == "#":
            ls.append([h,w])
            dp[h][w] = 0

ans = -1
while len(ls) > 0:
    ans += 1
    temp = []
    for h, w in ls:
        if 0 <= h+1 <= H-1 and dp[h+1][w] == -1:
            dp[h+1][w] = dp[h][w] + 1
            temp.append([h+1,w])
        if 0 <= h-1 <= H-1 and dp[h-1][w] == -1:
            dp[h-1][w] = dp[h][w] + 1
            temp.append([h-1,w])
        if 0 <= w+1 <= W-1 and dp[h][w+1] == -1:
            dp[h][w+1] = dp[h][w] + 1
            temp.append([h,w+1])
        if 0 <= w-1 <= W-1 and dp[h][w-1] == -1:
            dp[h][w-1] = dp[h][w] + 1
            temp.append([h,w-1])
    ls = temp

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

H, W = map(int, input().split())
G = [[i for i in input()] for j in range(H)]

ls = []
dp = [[-1 for i in range(W)] for j in range(H)]
for h in range(H):
    for w in range(W):
        if G[h][w] == "#":
            ls.append([h,w])
            dp[h][w] = 1

ans = -1
while len(ls) > 0:
    ans += 1
    temp = []
    for h, w in ls:
        if 0 <= h+1 <= H-1 and dp[h+1][w] == -1:
            dp[h+1][w] = 1
            temp.append([h+1,w])
        if 0 <= h-1 <= H-1 and dp[h-1][w] == -1:
            dp[h-1][w] = 1
            temp.append([h-1,w])
        if 0 <= w+1 <= W-1 and dp[h][w+1] == -1:
            dp[h][w+1] = 1
            temp.append([h,w+1])
        if 0 <= w-1 <= W-1 and dp[h][w-1] == -1:
            dp[h][w-1] = 1
            temp.append([h,w-1])
    ls = temp

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

import numpy as np

s = input()
t = input()

dp = np.full(len(t) , '', dtype=object)
# dp_len = [0]* len(t)

for i in range(len(s)):
    s_temp = s[i]
    temp_max = ''
    max_len = 0
    for j in range(len(t)):
        before = dp[j]
        if(s_temp == t[j]):
            dp[j] = temp_max + s_temp
        if(max_len < len(before)):
            temp_max = before
            max_len = len(temp_max)

ans = ''
for j in range(len(t)):
    if(len(dp[j]) > len(ans)):
        ans = dp[j]

print(ans)

### FIXED CODE ###

s = input()
t = input()

s_len = len(s)
t_len = len(t)

dp = [[0] * (t_len+1) for _ in range(s_len+1)]

for i in range(1,s_len+1):
    s_temp = s[i-1]
    for j in range(1, t_len+1):
        if(s_temp == t[j-1]):
            dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + 1)
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

ans = ''
while(s_len > 0 and t_len > 0):
    if(dp[s_len][t_len] == dp[s_len-1][t_len]):
        s_len -= 1
    elif(dp[s_len][t_len] == dp[s_len][t_len-1]):
        t_len -= 1
    else:
        ans = s[s_len-1]  + ans
        s_len -= 1
        t_len -= 1

print(ans)