Harryxun/stf_run huggingface dataset:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
from collections import deque
from math import ceil

def dist(h,w,x,y):
    return min(x-1,h-x,y-1,w-y)

h,w,k=map(int,input().split())
delta=[[1,0],[0,1],[-1,0],[0,-1]]
MAP=[]
A=['#']*(w+2)
MAP.append(A)
for i in range(h):
    s=input()
    for j,t in enumerate(s):
        if t=='S':
            sx,sy=i+1,j+1
    MAP.append(list(s))
MAP.append(A)
d=[[-1]*(w+2) for _ in range(h+2)]
d[sy][sx]=0
P=[]
q=deque()
q.append((sx,sy))
while q:
    x,y=q.popleft()
    if d[x][y]>k:
        break
    P.append([x,y])
    for dx,dy in delta:
        if d[y+dy][x+dx]==-1 and MAP[y+dy][x+dx]=='.':
            q.append((y+dy,x+dx))
            d[y+dy][x+dx]=d[y][x]+1
ans=float('inf')
for x,y in P:
    ans=min(ans,1+ceil(dist(h,w,x,y)/k))
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
from collections import deque
from math import ceil

h,w,k=map(int,input().split())
MAP=[]
for i in range(h):
    s=list(input().strip())
    for j,t in enumerate(s):
        if t=='S':
            sx,sy=i,j
    MAP.append(s)
delta=[[1,0],[0,1],[-1,0],[0,-1]]
q=deque()
q.append((sx,sy,k))
dist=float('inf')
Visited=[[False]*w for _ in range(h)]
Visited[sx][sy]=True
while len(q)>0:
    x,y,t=q.popleft()
    dist=min(dist,x,y,h-1-x,w-1-y)
    if dist==0:
        break
    if t>0:
        t-=1
        for dx,dy in delta:
            if MAP[x+dx][y+dy]=='.' and not Visited[x+dx][y+dy]:
                q.append((x+dx,y+dy,t))
                Visited[x+dx][y+dy]=True
print(1+ceil(dist/k))
N = int(input())

S=set()
i=2
while len(S)<=N:
    if i%2==0 or i%3==0:
        S.add(i)
    i+=1

r=sum(S)%6

if r%6==0:
    pass
elif r%2==0:
    S.remove(8)
    while len(S)<=N:
        if i%6==0:
            S.add(i)
            break
        i+=1
elif r%3==0:
    S.remove(9)
    while len(S)<=N:
        if i%6==0:
            S.add(i)
            break
        i+=1
elif r%5==0:
    S.remove(9)
    while len(S)<=N:
        if i%6==4:
            S.add(i)
            break
        i+=1




print(" ".join(map(str,S)))


### FIXED CODE ###

N = int(input())

if N==2:
    print(3,5)
    exit()
if N==3:
    print(2,5,63)
    exit()
if N==4:
    print(2,5,20,63)
    exit()

if N==5:
    print(2,5,20,30,63)
    exit()

S=set()
i=2
while len(S)<N:
    if i%2==0 or i%3==0:
        S.add(i)
    i+=1

i+=1
r=sum(S)

if r%6==0:
    pass
elif r%6==2:
    S.remove(8)
    while len(S)<N:
        if i%6==0:
            S.add(i)
            break
        i+=1
elif r%6==3:
    S.remove(9)
    while len(S)<N:
        if i%6==0:
            S.add(i)
            break
        i+=1
elif r%6==5:
    S.remove(9)
    while len(S)<N:
        if i%6==4:
            S.add(i)
            break
        i+=1

assert len(S)==N,len(S)
print(" ".join(map(str,S)))
S = input()
if(S == "hi"orS == "hihi"orS == "hihihi"orS == "hihihihi"orS == "hihihihihi"):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

S = input()
if(S == "hi"or S == "hihi"or S == "hihihi"or S == "hihihihi"or S == "hihihihihi"):
    print("Yes")
else:
    print("No")
n = int(input())
s = input()
print(max([len(set(s[:x])&set(s[x:])) for x in range(1,n-1)]))


### FIXED CODE ###

n = int(input())
s = input()
print(max([len(set(s[:x])&set(s[x:])) for x in range(1,n)]))
from math import *

def next_int():
    return int(input())

def next_ints():
    return list(map(int, input().split()))

a, b = next_ints()
n = gcd(a, b)
ans = 1
i = 2
while i*i <= n:
    if n%i == 0:
        ans += 1
        while n%i == 0:
            n //= i
    i += 1
if n != 1:
    ans += 1
print(ans,end="")


### FIXED CODE ###

# from math import *
from fractions import *

def next_int():
    return int(input())

def next_ints():
    return list(map(int, input().split()))

a, b = next_ints()
n = gcd(a, b)
ans = 1
i = 2
while i*i <= n:
    if n%i == 0:
        ans += 1
        while n%i == 0:
            n //= i
    i += 1
if n != 1:
    ans += 1
print(ans)
n = int(input())
m = 0
b = True
lis = map(long,input().split())
while(b):
  for index,l in enumrate(lis):
    if l % 2 == 1:
      b = False
      m -= 1
      break
    else:
      lis[index] = l // 2
  m += 1
 

### FIXED CODE ###

n = int(input())
lis = list(map(int,input().split()))
m = 0
b = True
while(b):
  for index,l in enumerate(lis):
    if l % 2 == 1:
      b = False
      m -= 1
      break
    else:
      lis[index] = l / 2
  m += 1
print(m)
def gmax(a,b):
  if a<b:
  	a,b=b,a
  while a%b!=0:
    tmp=a
    a=b
    b=tmp%b
  return b

n=int(input())
x=[]
for i in range(n):
  x.append(int(input()))
    
g=gmax(x[0],x[1])
l=x[0]*x[1]//g

for i in range(2,len(x)):
  g=gmax(x[i],l)
  l=x[i]*l//g

ans=l
print(ans)

### FIXED CODE ###

def gmax(a,b):
  if a<b:
  	a,b=b,a
  while a%b!=0:
    tmp=a
    a=b
    b=tmp%b
  return b
 
n=int(input())
x=[]
for i in range(n):
  x.append(int(input()))

if len(x)!=1:
  g=gmax(x[0],x[1])
  l=x[0]*x[1]//g

  for i in range(2,len(x)):
    g=gmax(x[i],l)
    l=(x[i]*l)//g
else:
  l=x[0]
print(l)
import math 
a,b=map(int,input().split()) 
print(a*b//math.gcd(a,b))

### FIXED CODE ###

import fractions  
a,b=map(int,input().split())  
print(a*b//fractions.gcd(a,b))
N = int(input())
L = list(map(int,input().strip().split()))
L_sort = L.sort()
count = 0
for i in range(N-2):
	for j in range(i+1 , N):
		for k in range(j+1 , N):
        	if L_sort(i) + L_sort(j) > L_sort(k):
            	count += 1
print(count)

### FIXED CODE ###

input_weather = input()
if input_weather.count('RRR') == 1:
	print(3)
elif input_weather.count('RR') == 1:
    print(2)
elif input_weather.count('R') >= 1:
    print(1)
else :
    print(0)
a = [raw_input().split(" ")]
a.sort()
print "%s %s %s" % (a[0],a[1],a[2])

### FIXED CODE ###

a = raw_input().split(" ")
a.sort()
print "%s %s %s" % (a[0],a[1],a[2])
s = input()
t = input()

ans = len(s)

for s_start in range(len(s)):
  if i + len(t) - 1 >= len(s):break;
    dif=0
    for j in range(len(t)):
      if s[i+j] != t[j]:
        dif += 1
    ans = min(ans, dif)
print(ans)

### FIXED CODE ###

s = input()
t = input()

ans = len(s)

for i in range(len(s)):
  if i + len(t) - 1 >= len(s):break;
  dif=0
  for j in range(len(t)):
    if s[i+j] != t[j]:
      dif += 1
  ans = min(ans, dif)
print(ans)
a = int(input())
b = [int(x) for x in input().split()]
summ = 1
for i in range(a):
    summ*=b[i]
    if(summ>1000000000000000000):
        summ=-1
        break
print(summ)

### FIXED CODE ###

b = [int(x) for x in input().split()]
print(b[0]*b[1])
print(input() ** 3)

### FIXED CODE ###

print(int(input())**3)
import math
n, k = map(int, input().split())
p = 0
for i in range(1,n+1):
  tmp = 1
  while i * temp < k:
    temp *= 2
  p += 1/temp
print(p/n)

### FIXED CODE ###

import math
n, k = map(int, input().split())
p = 0
for i in range(1,n+1):
  temp = 1
  while i * temp < k:
    temp *= 2
  p += 1/temp
print(p/n)
n = int(input())
a = map(int, input().split())

for i in range(1, n):
    print(str(a[-i]) + " ", end="")
print(a[0])

### FIXED CODE ###

n = int(input())
a = input().split()

for i in range(1, n):
    print(str(a[-i]) + " ", end = "")
print(a[0])
x,a,b = map(int,input().split())
s = abs(a - x)
t = abs(b - x)

print(min[s, t])

### FIXED CODE ###

x,a,b = map(int,input().split())
s = abs(a - x)
t = abs(b - x)
ans = "A"
if s > t:
    ans = "B"

print(ans)
a,p = map(int,input().split())
z = a*3+p
if z % 2 = 0:
  print(int(z/2))
else:
  print(int((z-1)/2))


### FIXED CODE ###

a,p = map(int,input().split())
z = a*3+p
if z % 2 == 0:
  print(int(z/2))
else:
  print(int((z-1)/2))
import sys
from collections import Counter

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

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

blue = 'b'*A
red= 'r'*B

ands =red+blue
alls = ands * (N//(A+B) + 1)
alls = alls[:N]
c = Counter(alls)
print(c['b'])


### FIXED CODE ###

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

# import collections

# blues = 'b' * A
# reds = 'r' * B

# set_balls = blues + reds

# all_balls = set_balls * ( N // ( A + B ) + 1 )

# balls_N = all_balls[:N]

# c = collections.Counter(balls_N)
# print(c['b'])

p = N//(A+B)

if N - p*(A+B) < A:
    print(A*p + N - p*(A+B) )
else:
    print(A*p+A)
inputs= list(input().split())
A=int(inputs[0])
B=int(float(inputs[1]+0.5)*100)
Ans=A*B/100//1
print(int(Ans))


### FIXED CODE ###

inputs= list(input().split())
A=int(inputs[0])
B=float(inputs[1])
B=int(B*100+0.5)
Ans=A*B//100
print(Ans)
import math
A, B, H, M = map(int, input().spli3t())
 
H_degree = (30 * H) + (0.5 * M)
M_degree = 6 * M
diff = abs(H_degree - M_degree)
if diff > 180:
  diff = 360 - diff
else:
  diff = diff
 
length = math.sqrt(A**2 + B**2 - 2*A*B*math.cos(math.radians(diff)))
 
print(length)

### FIXED CODE ###

import math
A, B, H, M = map(int, input().split())
 
H_degree = (30 * H) + (0.5 * M)
M_degree = 6 * M
diff = abs(H_degree - M_degree)
if diff > 180:
  diff = 360 - diff
else:
  diff = diff
 
length = math.sqrt(A**2 + B**2 - 2*A*B*math.cos(math.radians(diff)))
 
print(length)
a=int(input())
b=int(input())
c=int(input())
x=int(input())
cnt=0

for i in range(a+1):
  for j in range(b+1):
    for k in range(c+1):
      if 500*i + 100*j + 50*k==x:
        cnt+=1
print(cnt)


### FIXED CODE ###

from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

n,m=LI()
c=[]
x=[inf]*n
ans=True
g=[[] for _ in range(n)]
for i in range(m):
    l,r,d=LI_()
    d+=1
    g[l].append((r,d))
    g[r].append((l,-d))
    c.append((l,r,d))

v=[inf]*n
vs=[-1]*n

def bfs(st):
    if v[st]!=inf:
        return True
    q=[st]
    v[st]=0
    vs[st]=0
    while q:
        
        c=q.pop()
        for nb,d in g[c]:
            if vs[nb]==0:
                continue
            else:
                q.append(nb)
                vs[nb]=0
                if v[nb]==inf:
                    v[nb]=v[c]+d
                elif v[nb]!=v[c]+d:
                    show(c+1,nb+1,v)
                    return False
    return True

for i in range(n):
    if bfs(i):
        continue
    else:
        print('No')
        exit()

for i in range(m):
    l,r,d=c[i]
    if v[l]+d!=v[r]:
        print('No')
        exit()
        
print('Yes')
# coding: utf-8
# Here your code !
n = int(input())
output = []
for i in range(n):
    order,data =input().split() 
    if order == "insert":
        output.append(int(data))
#    elif order == "deleteFirst":
#        output.pop()
#    elif order == "deleteLast":
#        output.popleft()

#   elif order == "delete":
#        try:
#            output.remove(int(data))
#        except:
#            pass
output.reverse()
print(" ".join(output))
#print(" ".join(map(str,output)))

### FIXED CODE ###

import sys
from collections import deque
n = int(sys.stdin.readline())
lines = sys.stdin.readlines()
 
Q = deque()
for i in range(n):
    command = lines[i].split()
    if command[0] == "insert":
        Q.appendleft(command[1])
    elif command[0] == "deleteFirst":
        Q.popleft()
    elif command[0] == "deleteLast":
        Q.pop()
    elif command[0] == "delete":
        try:
            Q.remove(command[1])
        except:
            pass
print(" ".join(Q))
x, y = input().split()
if x = y:
    print('=')
elif x < y:
    print('<')
else:
    print('>')


### FIXED CODE ###

x, y = input().split()
 
if x > y:
    print('>')
elif x < y:
    print('<')
else:
    print('=')
import math
n=int(input())
count=0
for i in range(1, math.ceil(int(n**0.5))+1):
    if  n%i==0:
        if i==n%((n//i)-1):
            count+=(n//i)-1
print(count)

### FIXED CODE ###

n=int(input())
count=0
if n==1:count=0
else:
    for i in range(1, int(n**0.5)+1):
        if  n%i==0:
            if i==n%((n//i)-1):
                count+=(n//i)-1
print(count)
import collections
q = collections.deque(maxlen=1000000)

n = int(input())
for i in range(n):
    com = input().split()
    if com[0]=='insert':
        q.appendleft(int(com[1]))
    elif com[0]=='delete':
        try:
            q.remove(int(com[0]))
        except ValueError:
            pass
    elif com[0]=='deleteFirst':
        q.popleft()
    elif com[0]=='deleteLast':
        q.pop()
print(' '.join(q))

### FIXED CODE ###

import collections
q = collections.deque()
n = int(input())
for i in range(n):
    com = input().split()
    if com[0] == 'insert':
        q.appendleft(int(com[1]))
    elif com[0] == 'delete':
        try:
            q.remove(int(com[1]))
        except:
            pass
    elif com[0] == 'deleteFirst':
        q.popleft()
    elif com[0] == 'deleteLast':
        q.pop()
print(*q)
import math
A,B = map(int, input().split())
print(int(A*B//math.gcd(A,B)))

### FIXED CODE ###

import fractions
A,B = map(int, input().split())
print(int(A*B//fractions.gcd(A,B)))
a, v = map(int,input().split())
b, w = map(int,input().split())
t = int(input())

kyo = abs(b - a)
ti = v - w

if w >= v:
    print("NO")
    exit()


if round(kyo / ti) <= t:
    print("YES")
else:
    print("NO")


### FIXED CODE ###

s = input()

print(s[:3])
a=int(input())
b=int(input())
c=int(input())
if a==1:
  print("Hello World")
elif a==2:
  print(b+c)


### FIXED CODE ###

a=int(input())
if a==1:
  print("Hello World")
else:
  b=int(input())
  c=int(input())
  print(b+c)
5
aaaaa aaaaa

### FIXED CODE ###

n = int(input())
a ,b = input().split(" ")
s = ""
for x in range(n):
  s = s + a[x] + b[x]
print(s)
a, b = int(input().toString().split(" "))

print(abs((a-2)*(b-2)))

### FIXED CODE ###

a, b = [int(x) for x in input().split(" ")]
print(abs((a-2)*(b-2)))
# ABC097B - Exponential
x = int(input())
lst = []

for i in range(1, 32):
    for j in range(1, 10):
        if i ** j == x:
            print(x)
            exit()
        elif i ** j < x and i ** j not in lst:
            lst.append(i ** j)
        elif i ** j > x:
            break
            
lst.append(x)
lst = sorted(lst)

print(lst[lst.index(1000) - 1])

### FIXED CODE ###

# ABC097B - Exponential
x = int(input())
lst = []

for i in range(1, 32):
    for j in range(2, 10):
        if i ** j == x:
            print(x)
            exit()
        elif i ** j < x and i ** j not in lst:
            lst.append(i ** j)
        elif i ** j > x:
            break
            
lst.append(x)
lst = sorted(lst)

print(lst[lst.index(x) - 1])
s = int(input())
if 7 in s:
  print('yes')
else:
  print('no')

### FIXED CODE ###

if "7" in input():
  print("Yes")
else:
  print("No")
from functools import lru_cache

mod = 10**9+7

S = input()
S = S[::-1]
#print(S)

# 0~i桁目までの部分文字列において
# (mod 13)がbとなるパターン数を返す
@lru_cache(maxsize=None)
def search(i,rem):
	if i==len(S):
		return 1 if rem==5 else 0
	
	ch = int(S[i]) if S[i]!='?' else -1

	res = 0
	for d in range(10):
		if ch!=-1 and ch!=d:
			continue
		num = d*(10**i)%13
		res += search(i+1,(rem+num)%13)
	return res%mod

print(search(0,0))


### FIXED CODE ###

S = input()
S = S[::-1]
#print(S)

mod = 10**9+7

tblpow = [1]
for i in range(1,len(S)+1):
	tblpow.append(10*tblpow[i-1]%13)

dp = [0]*13
dp[0] = 1
for i in range(len(S)-1,-1,-1):
	ch = int(S[i]) if S[i]!='?' else -1
	temp = [0]*13
	for d in range(10):
		if ch!=-1 and ch!=d:
			continue
		for m in range(13):
			temp[(d*tblpow[i]+m)%13] += dp[m]
	for m in range(13):
		temp[m] %= mod
	dp = temp
print(dp[5])
x, n = map(int, input().split())
if n == 0:
	print(x)
	exit()
p = list(map(int, input().split()))
mind = abs(x - p[0])
pos = []
s = set(p)
p = []
for x1 in range(-100, 200):
	if x1 in s:
		continue
	else:
		p.append(x1)
for q in p:
	if abs(x - q) < mind:
		mind = abs(x - q)
		pos = [q]
	elif abs(x - q) == mind:
		pos.append(q)
pos.sort()
print(pos[0])

### FIXED CODE ###

x, n = map(int, input().split())
if n == 0:
	print(x)
	exit()
p = list(map(int, input().split()))

s = set(p)
p = []
for x1 in range(-100, 200):
	if x1 in s:
		continue
	else:
		p.append(x1)
mind = abs(x - p[0])
pos = [p[0]]
for q in p:
	if abs(x - q) < mind:
		#print(q)
		mind = abs(x - q)
		pos = [q]
	elif abs(x - q) == mind:
		pos.append(q)
pos.sort()
print(pos[0])
ab=int(input())
ll=s(ab)
def s(l):
    if l<2:
        return 1
    else:
        return s(l-2)
a=0
b=1
while(b):
    if(ll%10!=0):
        b=0
    else:
        a=a+1
print(a)

### FIXED CODE ###

p=int(input())
n=p
if n%2 == 0:
    num=10
    c=0;
    while num <= n:
        c += (n//num)
        num *= 5
    print(c)
else:
    print(0)
N,K,S = map(int, input().split())

if S == 10**9:
  [S]*K +[1]*(N-K)
else:
  ans = [S]*K +[S+1]*(N-K)

ans_txt=''

for s in ans:
  ans_txt += str(s)+' '

print(ans_txt)

### FIXED CODE ###

N,K,S = map(int, input().split())

if S == 10**9:
  ans = [S]*K +[1]*(N-K)
else:
  ans = [S]*K +[S+1]*(N-K)

ans_txt=''

for s in ans:
  ans_txt += str(s)+' '

print(ans_txt)
T=list(map(int,input().split(' '))).sort()
print(sum(T[-1]))


### FIXED CODE ###

T=list(map(int,input().split(' ')))
T.sort()
print(sum(T[:2]))
def main():
    s = input()
    slen = len(s)
    cnt = 0
    last = 0
    if s[0] == "W":
        for i in range(slen-1):
            if s[i] == "W" and s[i+1] =="B":
                cnt += 1
        if s[-1] == "W" and s[-2] == "B":
            last = 1
    if s[0] == "B":
        for i in range(slen-1):
            if s[i] == "B" and s[i+1] =="W":
                cnt += 1
        if s[-1] == "B" and s[-2] == "W":
            last = 1        
    if cnt == 0:
        print(cnt)
    else:
        print(cnt*2 - 1 + last)
    

 
    
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    s = input()
    slen = len(s)
    cnt = 0
    last = 0
    if s[0] == "W":
        for i in range(slen-1):
            if s[i] == "W" and s[i+1] =="B":
                cnt += 1
        if s[-1] == "W":
            last = 1
    if s[0] == "B":
        for i in range(slen-1):
            if s[i] == "B" and s[i+1] =="W":
                cnt += 1
        if s[-1] == "B":
            last = 1        
    if cnt == 0:
        print(cnt)
    else:
        print(cnt*2 - 1 + last)
    

 
    
    
if __name__ == "__main__":
    main()
a, b = map(int, input().split())
if b != 0:
    c = input()
    l = c.split()
    cc = [int(s) for s in l]
    ccc =list(cc)
    z = max(ccc) + 2
    for i in range(a,z):
        if i in ccc:
            continue
        else:
            x = i
            break
    for i in reversed(range(1, a)):
        if i in ccc:
            continue
        else:
            y = i
            break
    if x-a<a-y:
        print(x)
    else:
        print(y)
else:
    d = input()
    print(a)

### FIXED CODE ###

a, b = map(int, input().split())
if b != 0:
    c = input()
    l = c.split()
    cc = [int(s) for s in l]
    ccc =list(cc)
    for i in range(a,102):
        if i in ccc:
            continue
        else:
            x = i
            break
    for i in reversed(range(0, a)):
        if i in ccc:
            continue
        else:
            y = i
            break
    if x-a<a-y:
        print(x)
    else:
        print(y)
else:
    d = input()
    print(a)
import sys

# 最長部分列の長さを求める
# 0行と0列は0
def lcs_count(A,B):
    # initial value setting
    dp = [[0]*(l2+1) for _ in range(l1+1)]
    # create table
    for i in range(1,l1+1):
        for j in range(1,l2+1):
            if A[i-1] == B[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j],dp[i][j-1])
#    for line in dp:
#        print(line)
    return dp

def lcs_string(dp): 
    string = []
    i = l1-1
    j = l2-1
    while i > 0 and j > 0:
        if t[i - 1] == t[j - 1]:
            string.insert(0,chr(s[i-1]+97))
            i, j = i - 1, j - 1
        elif dp[i][j - 1] > dp[i - 1][j]:
            j -= 1
        else:
            i -= 1
    print("".join(string))

s = [ord(a)-97 for a in list(sys.stdin.readline().rstrip())]
t = [ord(b)-97 for b in list(sys.stdin.readline().rstrip())]
l1 = len(s)
l2 = len(t)

DP = lcs_count(s,t)
#print(DP[l1][l2])
lcs_string(DP)




### FIXED CODE ###

import sys

s = [ord(a)-97 for a in list(sys.stdin.readline().rstrip())]
t = [ord(b)-97 for b in list(sys.stdin.readline().rstrip())]
len_s = len(s)
len_t = len(t)

dp = [[0] * (len_t+1) for i in range(len_s+1)]
for i in range(len_s):
    for j in range(len_t):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

strings = []
while len_s > 0 and len_t > 0:
    if s[len_s-1] == t[len_t-1]:
        len_s -= 1
        len_t -= 1
        strings.insert(0,chr(s[len_s]+97))
    elif dp[len_s][len_t-1] > dp[len_s-1][len_t]:
        len_t -= 1
    else:
        len_s -= 1

print("".join(strings))
n,m = (int(x) for x in input().split())
memo = [0]*n
pena = [0]*n
ans2 = 0
for i in range(m):
    p,s = (str(x) for x in input().split())
    p = int(p)
    if s=="AC":
        memo[p-1] = 1
    elif s=="WA":
        if memo[p-1]==0:
            pena[p-1] += 1

for j in range(p):
    if memo[j]==1:
        ans2 += pena[j]

print("{} {}".format(sum(memo),ans2))

### FIXED CODE ###

n,m = (int(x) for x in input().split())
memo = [0]*n
pena = [0]*n
ans2 = 0
for i in range(m):
    p,s = (str(x) for x in input().split())
    p = int(p)
    if s=="AC":
        memo[p-1] = 1
    elif s=="WA":
        if memo[p-1]==0:
            pena[p-1] += 1

for j in range(n):
    if memo[j]==1:
        ans2 += pena[j]

print("{} {}".format(sum(memo),ans2))
n=int(input())
d=list(map(int,input().split())
hp=0
for i in range(n-1):
       for j in range(i+1,n):
            hp=hp+d[i]*d[j]
print(hp)

### FIXED CODE ###

n=int(input())
d=list(map(int,input().split()))
hp=0
for i in range(n-1):
       for j in range(i+1,n):
            hp=hp+d[i]*d[j]
print(hp)
S=input()
print('ABC' if S='ARC' else 'ARC')

### FIXED CODE ###

S=input()
print('ABC' if S=='ARC' else 'ARC')
import sys
n = int(input())
if n == 1:
	print('Hello World)
	sys.exit()
print(sum([int(input()) for _ in range(2)]))

### FIXED CODE ###

import sys
n = int(input())
if n == 1:
	print('Hello World')
	sys.exit()
print(sum([int(input()) for _ in range(2)]))
#abc161b
n,m=map(int,raw_input().split())
a=map(int,raw_input().split())
x=sum(a)/(4*m)
l=[i for i in a if i>=x]
if len(l)>m:
 print 'Yes'
else:
 print 'No'


### FIXED CODE ###

#abc161a
x,y,z=map(int,raw_input().split())
x,y=y,x
x,z=z,x
print x,y,z
import fractions
N = int(input())
A = [int(x) for x in input().split()]
a = A[0]
for i in range(1,N):
  a =fractions.gcd(a,A[i])
print(a)

### FIXED CODE ###

N,M=  map(int,input().split())

A = list(map(int,input().split()))
sorted(A)
B =[0,2,5,5,4,5,6,3,7,6]
C =[]
for i in A:
    C.append(B[i])
dp = [-1]*(N+1)
dp[0] = 0
for i in range(N+1):
    for a in range(len(C)):
        if i+C[a]<=N and 0<=dp[i]:
            dp[i+C[a]] = max(dp[i]*10+A[a],dp[i+C[a]])
print(dp[-1])