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

import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    s = list(input())
    t = list(input())

    sl = len(s)
    tl = len(t)

    dp = [[0 for _ in range(tl + 1)] for __ in range(sl + 1)]
    ans = [["" for _ in range(tl + 1)] for __ in range(sl + 1)]

    for i in range(sl):
        for j in range(tl):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
                ans[i + 1][j + 1] = ans[i][j] + s[i]
            else:
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
                if dp[i + 1][j] > dp[i][j + 1]:
                    ans[i + 1][j + 1] = ans[i + 1][j]
                else:
                    ans[i + 1][j + 1] = ans[i][j + 1]

    print(ans[sl][tl])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    s = list(input())
    t = list(input())

    sl = len(s)
    tl = len(t)

    dp = [[0 for _ in range(tl + 1)] for __ in range(sl + 1)]

    for i in range(sl):
        for j in range(tl):
            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])

    ans = ""
    x = sl
    y = tl
    while x > 0 and y > 0:
        if s[x - 1] == t[y - 1]:
            ans = s[x - 1] + ans
            x -= 1
            y -= 1
        elif dp[x][y] == dp[x - 1][y]:
            x -= 1
        elif dp[x][y] == dp[x][y - 1]:
            y -= 1
    print(ans)


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

n = int(input())

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

import itertools
B = []
for i in range(n+1):
    for j in itertools.permutations(A, i):
        sum_ = sum(j)
        if sum_ % 10 == 0:
            B.append(0)
        else:
            B.append(sum_)
print(max(B))

### FIXED CODE ###

n = int(input())

A = []
for i in range(n):
    A.append(int(input()))
total = sum(A)

if total % 10 != 0:
    print(total)
else:
    A = sorted(A)
    for i in range(n):
        if A[i] % 10 != 0:
            total -=A[i]
            break
    if total % 10 == 0:
        print(0)
    else:
        print(total)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

MOD=10**9+7
n,k=map(int,input().split())

def pow_mod(x,n):
  if n==0:
    return 1
  elif n==1:
    return x
  else:
    xn2=pow_mod(x,n//2)
    if n%2==0:
      return (xn2*xn2)%MOD
    else:
      return (xn2*xn2*x)%MOD

def fact_mod(a):
  if a<=1:
    return 1
  else:
    return a*fact_mod(a-1)%MOD
  
def perm_mod(n,a):
  if a==1:
    return n
  else:
    return (n*perm_mod(n-1,a-1))%MOD

def inv_mod(a):
  return pow_mod(a,MOD-2)%MOD
  
def comb_mod(na,fa):
  ainv=inv_mod(fa)
  return (na*ainv)%MOD
  
if k>=n-1:  
  #nHn=(2n-1)Cn
  perm=perm_mod(2*n-1,n)
  fact=fact_mod(n)
  comb=comb_mod(perm,fact)
  #print(perm,fact,comb)
  print(comb)
else:
  comb_sum=1
  for i in range(1,k+1):
    perm1=perm_mod(n,i)
    fact=fact_mod(i)
    comb1=comb_mod(perm1,fact)
    perm2=perm_mod(n-1,i)
    comb2=comb_mod(perm2,fact)
    comb=(comb1*comb2)%MOD
    comb_sum+=comb
  
  print(comb_sum%MOD)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

MOD=10**9+7
n,k=map(int,input().split())

def pow_mod(x,n):
  if n==0:
    return 1
  elif n==1:
    return x
  else:
    xn2=pow_mod(x,n//2)
    if n%2==0:
      return (xn2*xn2)%MOD
    else:
      return (xn2*xn2*x)%MOD

def fact_mod(a):
  if a<=1:
    return 1
  else:
    return a*fact_mod(a-1)%MOD
  
def perm_mod(n,a):
  if a==1:
    return n
  else:
    return (n*perm_mod(n-1,a-1))%MOD

def inv_mod(a):
  return pow_mod(a,MOD-2)%MOD
  
def comb_mod(na,fa):
  ainv=inv_mod(fa)
  return (na*ainv)%MOD
  
if k>=n-1:  
  #nHn=(2n-1)Cn
  perm=perm_mod(2*n-1,n)
  fact=fact_mod(n)
  comb=comb_mod(perm,fact)
  #print(perm,fact,comb)
  print(comb)
else:
  inv_table = [0]+[1]
  for i in range(2,k+1):
    inv_table+=[inv_table[MOD%i]*(MOD-int(MOD/i))%MOD]
  
  comb_sum=1
  fact=1
  comb1=1
  comb2=1
  for i in range(1,k+1):
    #comb1=comb1*(n-i+1)//i
    comb1=(comb1*(n-i+1)*inv_table[i])%MOD
    #comb2=comb2*(n-i)//i
    comb2=(comb2*(n-i)*inv_table[i])%MOD
    comb=(comb1*comb2)%MOD
    comb_sum+=comb
  
  print(comb_sum%MOD)
### BUGGY CODE ###

from collections import deque

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

black_idx = []
white_idx = []
for h in range(H):
    for w in range(W):
        if A[h][w] == ".":
            white_idx.append([h,w])
        else:
            black_idx.append([h,w])

distance = [[float("inf")]*W for _ in range(H)]
for b in black_idx:
    distance[b[0]][b[1]] = 0

for b in black_idx:
    d = deque([[b[0], b[1]]])
    while d:
        y, x = d.popleft()
        for new_y, new_x in ([int(y)+1, int(x)], [int(y), int(x)+1], [int(y)-1, int(x)], [int(y), int(x)-1]):
            if 0 <= new_y <= H-1 and 0 <= new_x <= W-1:
                new_cost = distance[y][x] + 1
                if new_cost < distance[new_y][new_x]: # 距離更新が発生した点だけdequeにappend
                    distance[new_y][new_x] = new_cost
                    d.append([new_y, new_x])

ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, distance[h][w])

print(ans)

### FIXED CODE ###

from collections import deque

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

black_idx = []
for h in range(H):
    for w in range(W):
        if A[h][w] == "#":
            black_idx.append([h,w])

distance = [[float("inf")]*W for _ in range(H)]
for b in black_idx:
    distance[b[0]][b[1]] = 0

d = deque(black_idx)
ans = 0

while d:
    y, x = d.popleft()
    for new_y, new_x in ([int(y)+1, int(x)], [int(y), int(x)+1], [int(y)-1, int(x)], [int(y), int(x)-1]):
        if 0 <= new_y <= H-1 and 0 <= new_x <= W-1 and distance[y][x] + 1 < distance[new_y][new_x]:
            distance[new_y][new_x] = distance[y][x] + 1
            ans = max(ans, distance[y][x] + 1)
            d.append([new_y, new_x])

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

n,m=map(int,input().split())
mList=[int(input()) for i in range(m)]

dp=[0]*(n+1)
#dp=[-1]*(n+1)
dp[0]=1
if 1 not in mList:
  dp[1]=1

for i in range(2,n+1):
  if i in mList: continue
  dp[i]+=dp[i-1]
  dp[i]+=dp[i-2]
  dp[i]%=1000000007

#def calc(i):
#  if dp[i]!=-1: return dp[i]
#  if i in mList:
#    dp[i]=0
#    return dp[i]
#  dp[i]=calc(i-1)+calc(i-2)
#  dp[i]%=1000000007
#  return dp[i]

#print(calc(n))
print(dp[n])


### FIXED CODE ###

n,m=map(int,input().split())
mList=set([int(input()) for _ in range(m)])

dp=[0]*(n+1)
dp[0]=1
if 1 not in mList:
  dp[1]=1

for i in range(2,n+1):
  if i in mList: continue
  dp[i]+=dp[i-1]
  dp[i]+=dp[i-2]
  dp[i]%=1000000007

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

n, x, y = map(int, input().split())
distance = [0] * int(n*(n+1)/2)
cnt = 0
for i in range(1, n):
    for j in range(i+1, n+1):
        distance[cnt] = (min([abs(j-i), abs(x-i)+abs(y-j)+1]))
        cnt += 1

for k in range(1, n):
    print(distance.count(k))

### FIXED CODE ###

n, x, y = map(int, input().split())
distance = [0] * n
for i in range(1, n):
    for j in range(i+1, n+1):
        distance[min([abs(j-i), abs(x-i)+abs(y-j)+1])] += 1

print('\n'.join(map(str, distance[1:])))
### BUGGY CODE ###

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

n = int(input())
s = [str(input()) for _ in range(n)]
s_set = set(["".join(sorted(_)) for _ in [i for i in s]])
s = ["".join(sorted(_)) for _ in [i for i in s]]
ans = 0
for word in s_set:
  cnt = 0
  for _ in s:
    if _ == word:
      cnt += 1
  if cnt >= 2:
  	ans += cmb(cnt, 2)
print(ans)

### FIXED CODE ###

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

n = int(input())
s = [str(input()) for _ in range(n)]
s = sorted(["".join(sorted(_)) for _ in [i for i in s]])
ans = 0
preb = str()
cnt = 1
for line in s:
  if preb == line:
    cnt += 1
  elif cnt >= 2:
    ans += cmb(cnt, 2)
    cnt = 1
  else:
    cnt = 1
  preb = line
if cnt >= 2:
    ans += cmb(cnt, 2)
print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n,k=map(int,input().split())
a=list(map(int,input().split()))

for i in range(k):
    ans=[0]*(n)
    for j in range(n):
        l=max(0,j-a[j])
        r=j+1+a[j]
        ans[l]+=1
        if r<n:
            ans[r]-=1
    for z in range(n-1):
        ans[z+1]+=ans[z]
    a=ans
print(" ".join(list(map(str,ans))))

### FIXED CODE ###

import sys
input=sys.stdin.readline
n,k=map(int,input().split())
a=list(map(int,input().split()))

for i in range(min(k,500)):
    ans=[0]*(n)
    for j in range(n):
        l=max(0,j-a[j])
        r=j+1+a[j]
        ans[l]+=1
        if r<n:
            ans[r]-=1
    for z in range(n-1):
        ans[z+1]+=ans[z]
    a=ans
print(" ".join(list(map(str,ans))))
### BUGGY CODE ###

n,k,q=map(int,input().split())
a=[int(input())-1 for i in range(q)]
point=[k-q for i in range(n)]

for i in range(n):
    print("Yes" if point[i]+a.count(i)>0 else "No")

### FIXED CODE ###

n,k,q=map(int,input().split())
a=[int(input())-1 for i in range(q)]
point=[k-q for i in range(n)]
for i in a:
    point[i]+=1

for i in point:
    print("Yes" if i>0 else "No")
### BUGGY CODE ###

N = int(input())
ans = []
for i in range(N):
    s = input()
    if (s in ans) == False:
        ans.append(s)
print(len(ans))


### FIXED CODE ###

N = int(input())
ans = []
for i in range(N):
    s = input()
    ans.append(s)
answer = set(ans)
print(len(answer))
### BUGGY CODE ###

import numpy as np
k = int(input().split(" ")[-1])

a_ = np.array([int(i) for i in input().split(" ")])
b_ = np.array([int(i) for i in input().split(" ")])
c_ = np.array([int(i) for i in input().split(" ")])

res = []
for a in a_:
    for b in b_:
        for c in c_:
            if len(res) == k:
                i = res.index(min(res))
                res[i] = max(res[i], a+b+c)
            else:
                res.append(a+b+c)

res = sorted(res)[::-1]

for i in range(k):
    print(res[i])


### FIXED CODE ###

x,y,z,K = (int(i) for i in input().split(" "))

a_ = sorted([int(i) for i in input().split(" ")])[::-1]
b_ = sorted([int(i) for i in input().split(" ")])[::-1]
c_ = sorted([int(i) for i in input().split(" ")])[::-1]

res = []
for i in range(x):
    for j in range(y):
        for k in range(z):
            if (i+1)*(j+1)*(k+1) <= K:
                res.append(a_[i]+b_[j]+c_[k])
            else:
                break

res = sorted(res)[::-1]

for i in range(K):
    print(res[i])
### BUGGY CODE ###

import math

N, P = map(int, input().split())
max_value = math.floor(pow(P, 1/N)+1)
ans = 1

if N == 1:
    ans = P
else:
    for i in range(1, max_value+1):
        mod = i ** N
        if P % mod == 0:
            ans = i

print(ans)


### FIXED CODE ###

import math

N, P = map(int, input().split())
max_value = round(pow(P, 1/N)) + 1 
ans = 1

if N == 1:
    ans = P
else:
    for i in range(1, max_value):
        mod = i ** N
        if P % mod == 0:
            ans = i

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

import itertools
n = int(input())
li = []
lic = []
count = 0
for i in range(n):
    lic.append(i+1)
    lia = list(input())
    lia.sort()
    li.append(lia)
lib = list(itertools.combinations(lic,2))
for i in range(len(lib)):
    if li[lib[i][0]-1] == li[lib[i][1]-1]:
        count += 1
print(count)

### FIXED CODE ###

n = int(input())
li = []
count = 0
f = 1
for i in range(n):
    a = input()
    li.append("".join(sorted(a)))
li.sort()
for i in range(n-1):
    if li[i] == li[i+1]:
        f += 1
    else:
        count += (f*(f-1))//2
        f = 1
count += (f*(f-1))//2
print(count)
### BUGGY CODE ###

K=input()
D=int(input())
mod=10**9+7

L=len(K)

DP=[[0]*D for i in range(2)]#DP[num][limit]で,一つ前の桁について,「桁和,そこまでKと一致していれば1」の場合の数


for j in range(10):
    if j>int(K[0]):
        continue
    if j==int(K[0]):
        DP[1][j%D]+=1
    else:
        DP[0][j%D]+=1
        


for keta in range(1,L):
    NDP=[[0]*D for i in range(2)]

    for i in range(D):
        for j in range(10):
            NDP[0][(i+j)%D]+=DP[0][i]

    for i in range(D):
        for j in range(10):
            if j>int(K[keta]):
                continue
            if j==int(K[keta]):
                NDP[1][(i+j)%D]+=DP[1][i]
            else:
                NDP[0][(i+j)%D]+=DP[1][i]

    DP=NDP

print((DP[0][0]+DP[1][0]-1)%mod)

### FIXED CODE ###

K=input()
D=int(input())
mod=10**9+7

L=len(K)

DP=[0]*D#DP[num][limit]で,一つ前の桁について,「桁和,そこまでKと一致していれば1」の場合の数
LIMIT=[]

for j in range(10):
    if j>int(K[0]):
        continue
    if j==int(K[0]):
        LIMIT=j%D
    else:
        DP[j%D]+=1

for ketanum in K[1:]:
    NDP=[0]*D

    for i in range(D):
        for j in range(10):
            NDP[(i+j)%D]=(NDP[(i+j)%D]+DP[i])%mod

    for j in range(int(ketanum)):
        NDP[(LIMIT+j)%D]+=1

    LIMIT=(LIMIT+int(ketanum))%D

    DP=NDP

print((DP[0]-1+ (LIMIT==0) )%mod)
### BUGGY CODE ###

def dfs(v, dist, d = 0, p = -1):
#     print(v, d)
    dist[v] = d
    for u in to[v]:
        if u == p:
            continue
        dfs(u, dist, d + 1, v)
def calcDist(s, dist):
    dfs(s, dist)        
n, u, v = map(int, input().split())
u -= 1
v -= 1
to = [[] for _ in range(10000005)]
for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
distS = [0] * n
distT = [0] * n
calcDist(u, distS)
calcDist(v, distT)
mx = 0
for i in range(n):
    if distS[i] < distT[i]:
        mx = max(mx, distT[i])
ans = mx - 1
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)

def dfs(v, dist, d = 0, p = -1):
#     print(v, d)
    dist[v] = d
    for u in to[v]:
        if u == p:
            continue
        dfs(u, dist, d + 1, v)
def calcDist(s, dist):
    dfs(s, dist)        
n, u, v = map(int, input().split())
u -= 1
v -= 1
to = [[] for _ in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
distS = [0] * n
distT = [0] * n
calcDist(u, distS)
calcDist(v, distT)
mx = 0
for i in range(n):
    if distS[i] < distT[i]:
        mx = max(mx, distT[i])
ans = mx - 1
print(ans)
### BUGGY CODE ###

import itertools


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

MOD = 1000000007

l = []
for i in range(N):
    l.append(i)

C = itertools.combinations(l, 2)

a = 0
for c in C:
    a += A[c[0]] * A[c[1]] % MOD
    a %= MOD
print(a)

### FIXED CODE ###

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

MOD = 1000000007

a = 0
b = 0
for i in range(N):
    a += A[i] % MOD
    b += (A[i] ** 2) % MOD
a = a ** 2
ans = (a - b) * pow(2, MOD - 2, MOD) % MOD
print(ans)
### BUGGY CODE ###

def main():

    S = input()

    rem = [0 for _ in range(2019)]
    ans = 0
    for i in range(len(S)):

        temp = [0 for _ in range(2019)]
        temp[int(S[i])] += 1

        for j in range(2019):
            temp[(j*10 + int(S[i])) % 2019] += rem[j]

        rem = temp
        ans += temp[0]

    return ans


if __name__ == '__main__':
    print(main())


### FIXED CODE ###

def main():

    S = input()
    d = dict()
    d[0] = 1
    v = 0
    p = 1
    for i in range(len(S)):
        v = v + int(S[len(S)-i-1]) * p
        v %= 2019
        d[v] = d.get(v, 0) + 1
        p *= 10
        p %= 2019

    ans = 0
    for v in d:
        ans += d[v] * (d[v] - 1) // 2
    return ans


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

n,W = (int(i) for i in input().split())
weights = []
values = []
for j in range(n):
    wt, val = [int(i) for i in input().split()]
    weights.append(wt)
    values.append(val)

prevdp = [0]*(W+1)
tempdp = [0]*(W+1)

for i in range(1,n+1):
    wI = weights[i-1]
    vI = values[i-1]
    
    for j in range(1,W+1):
        if wI>j:
            tempdp[j] = prevdp[j]
        else:
            tempdp[j] = max(prevdp[j],vI+prevdp[j-wI])
    prevdp = tempdp[:]

print(prevdp[-1])


### FIXED CODE ###

import numpy as np

n,W = (int(i) for i in input().split())
weights = []
values = []
for j in range(n):
    wt, val = [int(i) for i in input().split()]
    weights.append(wt)
    values.append(val)

dp  = np.zeros(W+1)

for i in range(1,n+1):
    w = weights[i-1]
    v = values[i-1]
    dp[w:] = np.maximum(dp[w:],v+dp[:-w])

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

def partsum(n,k):
  ret = sum(list(range(n-k+1,n+1)))
  return ret

N, K = map(int,input().split())
ret  = 0
for k in range(K, N+2):
  ret += partsum(N,k) - partsum(k-1,k) + 1
print(ret)


### FIXED CODE ###

def partsum(n,k):
  ret1 = n*(n+1)/2
  ret2 = (n-k+1)*(n-k)/2
  return ret1 - ret2

N, K = map(int,input().split())
ret  = 0
for k in range(K, N+2):
  ret += partsum(N,k) - partsum(k-1,k) + 1
print(int(ret)%(10**9+7))
### BUGGY CODE ###

import copy
def main():
  H,W=map(int, input().split())
  A=[]
  d=[]
  for h in range(H):
    a=[]
    s=input()
    for w in range(W):
      if s[w]=='.':
        a.append(-1)
      else:
        a.append(0)
        d.append((h,w))
    A.append(a)
  cnt=1
  DIF=[(1,0),(0,1),(-1,0),(0,-1)]
  tmp=[]
  while d:
    point=d.pop()
    for dif in DIF:
      x=point[0]+dif[0]
      y=point[1]+dif[1]
      if 0<=x<H and 0<=y<W and A[x][y]==-1:
        tmp.append((x,y))
        A[x][y]=cnt
    if not d:
      #print(tmp)
      d=copy.deepcopy(tmp)
      tmp=[]
      #print(d)
      cnt+=1
  ans=0    
  for h in range(H):
    Amax=max(A[h])
    ans=max(ans,Amax)
  #print(A)
  print(ans)
if __name__=='__main__':
  main()

### FIXED CODE ###

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

from collections import deque

q=deque([])
B=[[None]*W for _ in range (H)]
for i in range(H):
    for j in range(W):
        if A[i][j]=="#":
            q.append((i,j))
            B[i][j]=0
dx=[-1,1,0,0]
dy=[0,0,-1,1]
while len(q)>0:
  XY=[]
  while len(q)>0:
     XY.append(q.popleft())
  for xy in XY:
    for i in range(4):
      if 0<=(xy[0]+dx[i])<=H-1 and 0<=(xy[1]+dy[i])<=W-1:
        if B[xy[0]+dx[i]][xy[1]+dy[i]]==None:
          B[xy[0]+dx[i]][xy[1]+dy[i]]=B[xy[0]][xy[1]]+1
          q.append((xy[0]+dx[i],xy[1]+dy[i]))
        else: pass
      else: pass
print(max([max(B[i]) for i in range(H)]))
### BUGGY CODE ###

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

ans = 1
for e in a:
  ans *= e
if ans > 10 ** 18:
  print('-1')
  exit()

print(ans)


### FIXED CODE ###

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

a.sort()

ans = 1
for e in a:
  ans *= e
  if ans > 10 ** 18:
    print('-1')
    exit()


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

h,w = map(int,input().split())
s = [ input() for _ in range(h) ]

l = [ [0]*w for _ in range(h) ] 
r = [ [0]*w for _ in range(h) ] 
u = [ [0]*w for _ in range(h) ] 
d = [ [0]*w for _ in range(h) ] 

for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            l[i][j] = 0
        elif j==0:
            l[i][j] = 1
        else:
            l[i][j] = l[i][j-1] + 1

for i in range(h):
    for j in reversed(range(w)):
        if s[i][j]=="#":
            r[i][j] = 0
        elif j==(w-1):
            r[i][j] = 1
        else:
            r[i][j] = r[i][j+1] + 1
    
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            u[i][j] = 0
        elif i==0:
            u[i][j] = 1
        else:
            u[i][j] = u[i-1][j] + 1

for i in reversed(range(h)):
    for j in range(w):
        if s[i][j]=="#":
            d[i][j] = 0
        elif i==(h-1):
            d[i][j] = 1
        else:
            d[i][j] = d[i+1][j] + 1

# print(l)
# print(r)
# print(u)
# print(d)

M = 0
for i in range(h):
    for j in range(w):
        lamp = l[i][j] + r[i][j] + u[i][j] + d[i][j] - 3
        M = max(M,lamp)

print(M)

### FIXED CODE ###

h,w = map(int,input().split())
s = [ input() for _ in range(h) ]

l = [ [0]*w for _ in range(h) ] 
r = [ [0]*w for _ in range(h) ] 
u = [ [0]*w for _ in range(h) ] 
d = [ [0]*w for _ in range(h) ] 

for i in range(h):
    for j in range(w):
        # l
        if s[i][j]=="#":
            l[i][j] = 0
        elif j==0:
            l[i][j] = 1
        else:
            l[i][j] = l[i][j-1] + 1
        # u
        if s[i][j]=="#":
            u[i][j] = 0
        elif i==0:
            u[i][j] = 1
        else:
            u[i][j] = u[i-1][j] + 1

for i in reversed(range(h)):
    for j in reversed(range(w)):
        # r
        if s[i][j]=="#":
            r[i][j] = 0
        elif j==(w-1):
            r[i][j] = 1
        else:
            r[i][j] = r[i][j+1] + 1
        # d
        if s[i][j]=="#":
            d[i][j] = 0
        elif i==(h-1):
            d[i][j] = 1
        else:
            d[i][j] = d[i+1][j] + 1

# print(l)
# print(r)
# print(u)
# print(d)

M = 0
for i in range(h):
    for j in range(w):
        lamp = l[i][j] + r[i][j] + u[i][j] + d[i][j] - 3
        M = max(M,lamp)

print(M)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
sum = 0
for i in range(0,n-1):
    for j in range(i+1,n):
        b = a[i]*a[j]%(10**9+7)
        sum = sum + b
print(sum%(10**9+7))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
A = sum(a)
s = 0
for i in range(n-1):
    A = A - a[i]
    b = (a[i]*A)%(10**9+7)
    s = s + b
print(s%(10**9+7))
### BUGGY CODE ###

import sys

input = sys.stdin.readline


def dot(a, b):
    an = len(a)
    bn = len(b[0])
    c = [[0] * bn for _ in range(an)]
    for i in range(an):
        ai = a[i]
        for j in range(bn):
            ck = 0
            for ak, bk in zip(ai, [bi[j] for bi in b]):
                ck += (ak * bk) % md
                c[i][j] = ck % md
    return c


def pwr(a, k):
    c = None
    while k > 0:
        if k & 1:
            if c:
                c = dot(a, c)
            else:
                c = a
        a = dot(a, a)
        k >>= 1
    return c


md = 10 ** 9 + 7
n, k = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
print(sum([sum(pk) % md for pk in pwr(a, k)]) % md)


### FIXED CODE ###

import sys

input = sys.stdin.readline


def dot(a, b):
    c = [[0] * n for _ in range(n)]
    for i, ai in enumerate(a):
        for j, bj in enumerate(zip(*b)):
            c[i][j] = sum(ak * bk for ak, bk in zip(ai, bj)) % md
    return c


def pwr(a, k):
    c = None
    while c == None:
        if k & 1:
            c = a
        a = dot(a, a)
        k >>= 1

    while k > 0:
        if k & 1:
            c = dot(a, c)
        a = dot(a, a)
        k >>= 1
    return c


md = 10 ** 9 + 7
n, k = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
print(sum([sum(pk) % md for pk in pwr(a, k)]) % md)
### BUGGY CODE ###

A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
z = [list(map(int, input().split())) for _ in range(M)]
mem = []

for i in range(len(a)):
    for j in range(len(b)):
        mem.append(a[i] + b[j])

for x, y, c in z:
    mem.append(a[x - 1] + b[y - 1] - c)

print(min(mem))


### FIXED CODE ###

A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
L = [[int(x) for x in input().split()] for _ in range(M)]

reg = min(a) + min(b)
for x, y, c in L:
    tmp = a[x-1] + b[y-1] - c
    reg = min(reg, tmp)
print(reg)