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

from collections import Counter
S = input()
T = input()
q = int(input())
for i in range(q):
  a, b, c, d = map(int, input().split())
  c1 = Counter(list(S[a-1:b]))
  c2 = Counter(list(T[c-1:d]))
  if abs((c1['A'] - c1['B']) - (c2['A'] - c2['B'])) % 3 == 0:
    print('YES')
  else:
    print('NO')

### FIXED CODE ###

ds = [0]
tmp = 0
for c in input():
  tmp += [-1, 1][c == 'A']
  ds.append(tmp)

dt = [0]
tmp = 0
for c in input():
  tmp += [-1, 1][c == 'A']
  dt.append(tmp)

q = int(input())
for i in range(q):
  a, b, c, d = map(int, input().split())
  if abs((ds[b] - ds[a-1]) - (dt[d] - dt[c-1])) % 3 == 0:
    print('YES')
  else:
    print('NO')
### BUGGY CODE ###

import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

h,w = map(int, input().split())
board = [list(input()) for i in range(h)]

road = []

for i in range(h):
    for j in range(w):
        if board[i][j] == ".":
            road.append([i,j])


from heapq import heappop, heappush

def dfs(start, end):
    dxdy = [(0,1),(1,0),(0,-1),(-1,0)]
    dist = [[float("inf")]*w for i in range(h)]
    #heap = [(0, *start)]
    heap = [(0, start[0], start[1])]
    while heap:
        c,x,y = heappop(heap)
        if dist[x][y] <= c:
            continue
        dist[x][y] = c
        for dx, dy in dxdy:
            nx = x + dx
            ny = y + dy
            if 0<=nx<h and 0<=ny<w and board[nx][ny] == ".":
                heappush(heap, (c+1, nx, ny))
    return dist[end[0]][end[1]]


from itertools import combinations

ans = 0
for start, end in combinations(road, 2):
    #print(start, end)
    tmp = dfs(start, end)
    if tmp != float("inf"):
        ans = max(ans, tmp)
print(ans)

### FIXED CODE ###

import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

from heapq import heappop, heappush

dxdy = [(0,1),(1,0),(0,-1),(-1,0)]

h,w = map(int, input().split())
board = [list(input()) for i in range(h)]

def dfs(x, y):
    dist = [[float("inf")]*w for i in range(h)]
    heap = [(0, x, y)]
    while heap:
        c,x,y = heappop(heap)
        if dist[x][y] <= c:
            continue
        dist[x][y] = c
        for dx, dy in dxdy:
            nx = x + dx
            ny = y + dy
            if 0<=nx<h and 0<=ny<w and board[nx][ny] == "." and dist[nx][ny] > c+1:
                heappush(heap, (c+1, nx, ny))
    ret = 0
    for i in range(h):
        for j in range(w):
            if dist[i][j] != float("inf"):
                ret = max(ret, dist[i][j])
    return ret

ans = 0
for i in range(h):
    for j in range(w):
        if board[i][j] == ".":
            ans = max(ans, dfs(i,j))

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

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

L = sorted(L, reverse=True)

# print(L)

ans = 0
for i in range(N):
    a = L[i]
    for j in range(i+1, N):
        b = L[j]
        for k in range(j+1, N):
            c = L[k]
            if not c < a + b:
                break
            if a < b + c and b < c + a:
                # print("a:{}, b:{}, c:{}".format(a, b, c))
                ans += 1

print(ans)


### FIXED CODE ###

import time
N = int(input())
L = list(map(int, input().split()))

L = sorted(L)

# print(L)

# 三角形なのでa>b>cになるように選べば, a+b>cとなる
ans = 0
for i in range(N-2):
    a = L[i]
    for j in range(i+1, N-1):
        # print("i:{}, j:{}".format(i, j))
        b = L[j]
        left = j+1
        right = N-1
        c = L[N-1]
        if a+b>c:
            # print("true - k:{}".format(N-1))
            # print("num_c:{}".format())
            ans += N-j-1
        else:
            mid = right
            while left < right:
                if mid == (left+right)//2:
                    break
                mid = (left+right)//2
                # print("left:{}, mid:{}, right:{}".format(left, mid, right))
                c = L[mid]
                if a+b>c:
                    left = mid
                else:
                    right = mid
                # time.sleep(0.05)
            # print("false - k:{}".format(mid))
            if a+b>c:
                # print("a+b>c:{}".format(True))
                ans += mid - j
            else:
                # print("a+b>c:{}".format(False))
                ans += mid - j - 1
        # print("ans of ({},{}): {}".format(i,j,ans))

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

# coding: utf-8
N, M = map(int, input().split())
a = []
for i in range(M):
    a.append(int(input()))
a.append(N+1)
a.append(N+2)
#print("a", a)

dp = [1, 0]
#s = 0
mod = 1000000007

for s in reversed(range(N)):
    if s in a: # xだったら
        dp.insert(0, 0) # 無を代入
        #continue
    else: # oだったら
        t = (dp[0] + dp[1]) % mod
        dp.insert(0, t)
        
print(dp[0])


### FIXED CODE ###

# coding: utf-8
def main():
    N, M = map(int, input().split())

    a = [True] * (N+1)
    #s = [True for _ in range(N+1)]
    for _ in range(M):
        a[int(input())] = False
    #print(a)
    
    #a = []
    #for i in range(M):
    #    a.append(int(input()))
    
    dp = [0] * (N)
    dp.append(1)
    dp.append(0)
    mod = 10**9 + 7
    
    for s in reversed(range(N)):
        if a[s] == False: # xだったら
            if a[s+1] == False:
                dp[s] = 0 # 2回連続で穴があったら0返して終了
                break
            else:
                dp[s] = 0 # 無を代入
        else: # oだったら
            dp[s] = (dp[s+1] + dp[s+2]) % mod # DP!! DP!!
            
    print(dp[0])

main()
### BUGGY CODE ###

def main():
  N,M = map(int,input().split())
  ships = sorted([list(map(int,input().split())) for i in range(M)])
  
  ans = "IMPOSSIBLE"
  
  con = 0
  
  for i in range(M):
    if ships[i][0] == 1:
      con += 1
  
  for i in range(0,min(M,con + 1)):
    if ships[i][0] == 1:
      ship = ships[i][1]
      for j in range(con,M):
        if ships[j][0] == ship and ships[j][1] == N:
          ans = "POSSIBLE"
          break
      else:
        continue
      break
        
  print(ans)
  
main()

### FIXED CODE ###

def main():
  N,M = map(int,input().split())
  ships = [list(map(int,input().split())) for i in range(M)]
  start, goal = set(), set()
  for i in range(M):
    if ships[i][0] == 1:
      start.add(ships[i][1])
    if ships[i][1] == N:
      goal.add(ships[i][0])
  flg = start & goal
  print("POSSIBLE" if flg else "IMPOSSIBLE")
 
main()
### BUGGY CODE ###

def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()
import copy
n,wmax=IL()
dp=[0 for i in range(wmax+1)]
for i in range(1,n+1):
    w,v=IL()
    predp=copy.deepcopy(dp)
    for j in range(w,wmax+1):
        dp[j]=max(predp[j],predp[j-w]+v)
print(dp[wmax])

### FIXED CODE ###

import numpy as np
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()

n,wmax=IL()
dp=np.zeros(wmax+1,dtype=int)
for i in range(n):
    w,v=IL()
    dp[w:]=np.maximum(dp[w:],dp[:-w]+v)
print(dp[wmax])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import itertools
# 周長は三角形のうちの最大長の2倍よりも大きい

def solve(N: int, L: "List[int]"):
    # N = 5
    # L = [1,2,2,3,4]
    L.sort()
    answer = 0
    for i in range(N):
        for j in range(i+1,N):
            for k in range(j+1,N):
                if L[i]+L[j]>L[k]:
                    answer += 1
    print(answer)
    return


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
    L = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, L)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import bisect

def solve(N: int, L: "List[int]"):
    L.sort()
    answer = 0
    for i in range(N):
        for j in range(i+1,N):
            max_k = bisect.bisect_left(L,L[i]+L[j])
            answer += max_k-(j+1)
    print(answer)
    return


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
    L = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, L)

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

import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

def main():
    s = ns()
    k = ni()

    check = set()

    for left in range(0, len(s)):
        for right in range(left+1, len(s)+1):
            check.add(s[left:right])
    
    print(sorted(list(check))[k-1])

if __name__ == '__main__':
    main()

### FIXED CODE ###

import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

def main():
    s = ns()
    k = ni()

    check = set()

    for left in range(0, len(s)):
        for right in range(left+1, left+k+1):
            check.add(s[left:right])
    
    print(sorted(list(check))[k-1])

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

n, q = map(int, input().split())
s = str(input())
a = []
for i in range(q):
    a.append([int(i) for i in input().split()])
diff = [1 if s[i:i+2] == "AC" else 0 for i in range(len(s)-1)]
for i in a:
    ans = sum(diff[i[0]-1:i[1]-1])
    print(ans)

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
t = [0] * (n+1)
for i in range(n):
    t[i + 1] = t[i] + (1 if s[i:i+2] == "AC" else 0)
for j in range(q):
    l, r = map(int, input().split())
    ans = t[r-1] - t[l-1]
    print(ans)
### BUGGY CODE ###

S=input()
M=13
MOD=10**9+7
dp=[[0]*M for i in range(2)]
dp[1][0]=1
for i in range(len(S)):
  dp[0]=[0]*13
  s=S[i]
  if s=='?':
    for s in range(10):
      for j,d in enumerate(dp[1]):
        dp[0][(j+s)%M]+=d
        #dp[0][(j+s)%M]%=MOD
  else:
    s=int(s)
    for j,d in enumerate(dp[1]):
      dp[0][(j+s)%M]=d
  for j,d in enumerate(dp[0]):
    dp[1][(10*j)%M]=d%MOD
print(dp[0][5]%MOD)



### FIXED CODE ###

S=input()
import numpy as np
M=13
MOD=10**9+7
dp=np.zeros(M, dtype=np.int64)
dp[0]=1
idx = np.zeros(M, dtype=np.int8)
window = np.ones(10, dtype=np.int8)
for i in range(M):
  idx[i * 10 % M] = i
for s in S:
  if s=='?':
    tdp=dp[idx]
    ndp = np.concatenate([tdp[4:], tdp])
    dp = np.convolve(ndp, window, mode='valid') % MOD
  else:
    dp=np.roll(dp[idx],int(s))
print(dp[5]%MOD)
### BUGGY CODE ###

from operator import itemgetter
import numpy as np

N, T = [int(i) for i in input().split()]

data = []
for i in range(N):
    data.append([int(i) for i in input().split()])

data.sort(key=itemgetter(0))

#dp = [[0] * (T+1) for i in range(N)]
dp = np.zeros((N, T+1), int)

dp[0][T] = data[0][1]
for i in range(1, N):
    time = data[i-1][0]
    value = data[i-1][1]
    add_value = data[i][1]
    for j in range(T):
        if j >= time:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-time] + value)
        else:
            dp[i][j] = dp[i-1][j]
    dp[i][T] = dp[i][T-1] + add_value

ans = np.max([row[-1] for row in dp[:]])
print(ans)


### FIXED CODE ###

from operator import itemgetter
N, T = [int(i) for i in input().split()]

data = []
for i in range(N):
    data.append([int(i) for i in input().split()])

data.sort(key=itemgetter(0))

dp = [[0]*(T) for i in range(N)]
ans = data[0][1]
for i in range(1, N):
    for j in range(T):
        if j >= data[i-1][0]:
            value1 = dp[i-1][j]
            value2 = dp[i-1][j-data[i-1][0]] + data[i-1][1]
            dp[i][j] = max(value1, value2)
        else:
            dp[i][j] = dp[i-1][j]
    value3 = dp[i][T-1] + data[i][1]
    ans = max(value3, ans)
print(ans)
### BUGGY CODE ###

from collections import Counter as ct
n = int(input())
ans = 0
words = [input() for _ in range(n)]
while words:
  mas = words.pop()
  count = 0
  for word in words:
    if ct(mas) == ct(word):
      count += 1
      words.remove(word)
  if count == 1:
    ans += count
  else:
    ans += count * (count + 1) // 2
print(ans)


### FIXED CODE ###

from collections import Counter as ct
n = int(input())
ans = 0
words = [ct(input()) for _ in range(n)]
words = ct([tuple(sorted([(x, y) for x, y in z.items()])) for z in words])

for i in words.values():
  ans += i * (i-1) // 2
print(ans)
### BUGGY CODE ###

n = int(input())
factor = []

for i in range(1,n+1):
    if n%i == 0:
        factor.append(i + n//i -2)
    else:
        continue

print(min(factor))

### FIXED CODE ###

n = int(input())
factor = []

for i in range(1,int(n**0.5)+1):
    if n%i == 0:
        factor.append(i + n//i)

factor.sort()
print(factor[0]-2)
### BUGGY CODE ###

def dfs(v, c):
    color[v] = c
    for i in range(n):
        if g[v][i] == 1:
            if color[i] == c:
                return False
            if color[i] == 0 and not dfs(i, -c):
                return False
    return True


n = int(input())
g = []
for i in range(n):
    s = list(map(int, list(input())))
    for j in range(n):
        if s[j] == 0:
            s[j] = 1000000
        if i == j:
            s[j] = 0
    g.append(s)

# 二部グラフ判定
color = [0] * n
nibu = True
for i in range(n):
    if color[i] == 0:
        if not dfs(i, 1):
            nibu = False

if nibu:
    for k in range(n):
        for i in range(n):
            for j in range(n):
                g[i][j] = min(g[i][j], g[i][k] + g[k][j])
    ans = 0
    for i in range(n):
        ans = max(ans, max(g[i]))
    print(ans + 1)
else:
    print(-1)

### FIXED CODE ###

def dfs(v, c):
    color[v] = c
    for i in range(n):
        if g[v][i] == 1:
            if color[i] == c:
                return False
            if color[i] == 0 and not dfs(i, -c):
                return False
    return True


n = int(input())
g = []
for i in range(n):
    s = list(map(int, list(input())))
    for j in range(n):
        if s[j] == 0:
            s[j] = 1000000
        if i == j:
            s[j] = 0
    g.append(s)

# 二部グラフ判定
color = [0] * n
nibu = True
for i in range(n):
    if color[i] == 0:
        if not dfs(i, 1):
            nibu = False

if nibu:
    for k in range(n):
        for i in range(n):
            for j in range(n):
                g[i][j] = min(g[i][j], g[i][k] + g[k][j])
    ans = 0
    for i in range(n):
        ans = max(ans, max(g[i]))
    print(ans + 1)
else:
    print(-1)
### BUGGY CODE ###

N=int(input())
S=input()
b=0
for i in range(1000):
 i1=int(i/100)
 i2=int((i-i1*100)/10)
 i3=i%10
 a=0
 for j in range(N):
  if a==0:
   if int(S[j])==i1:
    a+=1
  elif a==1:
   if int(S[j])==i2:
    a+=1
  elif a==2:
   if int(S[j])==i3:
    a+=1
  else:
   continue
 if a==3:
  b+=1
print(b)

### FIXED CODE ###

N=int(input())
S=input()
A=[0]*N
for i in range(N):
 A[i]=int(S[i])
b=0
for i in range(1000):
 i1=int(i/100)
 i2=int((i-i1*100)/10)
 i3=i%10
 a=0
 for j in range(N):
  if a==0:
   if A[j]==i1:
    a+=1
  elif a==1:
   if A[j]==i2:
    a+=1
  else:
   if A[j]==i3:
    b+=1
    break
print(b)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10**6 + 1000)

par = [0]
words = lambda t : list(map(t, input().split()))
n,q = words(int)
edges = [[] for _ in range(n)]
for i in range(n-1):
    a,b = words(int)
    edges[a-1].append(b-1)

points = [0] * n
for i in range(q):
    p,x = words(int)
    points[p-1] += x

ans = [0] * n
def digTree(cur, sum_p):
    #print("debug: ", cur, sum_p)
    sum_pp = sum_p +  points[cur]
    ans[cur] = sum_pp
    for child in edges[cur]:
        digTree(child, sum_pp)

digTree(0, 0)
print(" ".join(map(str,ans)))


### FIXED CODE ###

import sys

sys.setrecursionlimit(10**6 + 1000)


words = lambda t : list(map(t, input().split()))
n,q = words(int)
par = [0] * n
for i in range(n-1):
    a,b = words(int)
    par[b-1] = a-1

points = [0] * n
for i in range(q):
    p,x = words(int)
    points[p-1] += x

ans = [0] * n
ans[0] = points[0]
for i in range(1,n):
    ans[i] = ans[par[i]] + points[i]


print(" ".join(map(str,ans)))
### BUGGY CODE ###

n, k = map(int, input().split())
h = [int(i) for i in input().split()]

dp = [0] * n
dp[1] = abs(h[1] - h[0])

for i in range(2,n):
    min_cost = 999999999
    for j in range(1,min(i,k)+1):
        tmp = dp[i-j] + abs(h[i] - h[i-j])
        min_cost = min(min_cost, tmp)
    dp[i] = min_cost

print(dp[n-1])

### FIXED CODE ###

n, k = map(int, input().split())
h = [int(i) for i in input().split()]

dp = [0] * n
dp[1] = abs(h[1] - h[0])

for i in range(2,n):
    min_cost = 999999999
    for j in range(1,min(i,k)+1):
        tmp = dp[i-j] + abs(h[i] - h[i-j])
        min_cost = min(min_cost, tmp)
    dp[i] = min_cost

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

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

a, b = 0, 0

for i in range(n):
    if i + 1 in hole:
        a, b = 0, a
    else:
        if i == 0:
            a = 1
        elif i == 1:
            a, b = a + 1, a
        else:
            a, b = a + b, a
    

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

### FIXED CODE ###

n, m = map(int,input().split())
hole = [int(input()) for _ in range(m)]
k = 0
a, b = 0, 0
x = (10 ** 9 + 7)
for i in range(n):
    if m >= 1:
        if i + 1 == hole[k]:
            a, b = 0, a
        else:
            if i == 0:
                a = 1
            elif i == 1:
                a, b = (a + 1) % x, a % x
            else:
                a, b = (a + b) % x, a % x
        if i + 1 >= hole[k] and k < m - 1:
            k += 1
    else:
        if i == 0:
                a = 1
        elif i == 1:
            a, b = (a + 1) % x, a % x
        else:
            a, b = (a + b) % x, a % x
    
print(a)
### BUGGY CODE ###

#import random

def putmx(lis):
  ret=[]
  mx=max(lis)
  for i in range(len(lis)):
    if mx==lis[i]:
      ret.append(i)
  return ret
  

h,w,m=map(int,input().split())
#inp=[(random.randrange(1,h+1),random.randrange(1,w+1)) for i in range(m)]
hb=[0]*h
wb=[0]*w
bmb=[]
for i in range(h):
  bmb.append([])
for i in range(m):
  hh,ww=map(int,input().split())
  hh-=1
  ww-=1
  bmb[hh].append(ww)
  hb[hh]+=1
  wb[ww]+=1

hmx=[i for i, x in enumerate(hb) if x == max(hb)]
wmx=[i for i, x in enumerate(wb) if x == max(wb)]
mhb=max(hb)
mwb=max(wb)
#print(hb,wb,hmx,wmx)
fl=False
for i in hmx:
  for j in wmx:
    if not j in bmb[i]:
      print(mhb+mwb)
      fl=True
      break
  if fl:
    break
else:
  print(mhb+mwb-1)


### FIXED CODE ###

#import random

def putmx(lis,mx):
  ret=[]
  for (i,j) in zip(range(len(lis)),lis):
    if j==mx:
      ret.append(i)
  return ret
  

h,w,m=map(int,input().split())
hb=[0]*h
wb=[0]*w
bmb=[]
for i in range(h):
  bmb.append({-1})
for i in range(m):
  hh,ww=map(int,input().split())
  hh-=1
  ww-=1
  bmb[hh].add(ww)
  hb[hh]+=1
  wb[ww]+=1
mhb=max(hb)
mwb=max(wb)
hmx=putmx(hb,mhb)
wmx=set(putmx(wb,mwb))

#print(hb,wb,hmx,wmx)
fl=False
for i in hmx:
  if wmx|bmb[i]!=bmb[i]:
    print(mhb+mwb)
    break
else:
  print(mhb+mwb-1)

#print(hmx,wmx,bmb)
### BUGGY CODE ###

#!/usr/bin/python3
K = int(input())
sum_gcd = 0
gcd = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            i = 1
            while i <= min(a,b,c):
                if a % i == 0 and b % i == 0 and c % i == 0:
                   gcd = i  
                i += 1
            sum_gcd += gcd
print(sum_gcd)       

### FIXED CODE ###

#!/usr/bin/python3
import math
K = int(input())
sum_gcd = 0
for a in range(1,K+1):
    for b in range(1,a+1):
        for c in range(1,b+1):
            if a == b and b == c :
                sum_gcd += math.gcd(math.gcd(a,b),c)
            elif a == b or b == c or c == a:
                sum_gcd += 3 * math.gcd(math.gcd(a,b),c)
            else:
                sum_gcd += 6 * math.gcd(math.gcd(a,b),c)
print(sum_gcd)
### BUGGY CODE ###

if __name__ == '__main__':
    h,w = list(map(int, input().split()))
    s = []
    for i in range(h):
        s.append(input())
    
    l = [[0 for i in range(w)] for j in range(h)]
    r = [[0 for i in range(w)] for j in range(h)]
    u = [[0 for i in range(w)] for j in range(h)]
    d = [[0 for i in range(w)] for j in range(h)]

    for i in range(h):
        for j in range(0, 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
            
            tw = w-j-1
            if(s[i][tw] == "#"):
                r[i][tw] = 0
            elif(j == 0):
                r[i][tw] = 1
            else:
                r[i][tw] = r[i][tw+1] + 1
            
            if(s[i][j] == "#"):
                u[i][j] = 0
            elif(i == 0):
                u[i][j] = 1
            else:
                u[i][j] = u[i-1][j] + 1
                
            th = h-i-1
            if(s[th][j] == "#"):
                d[th][j] = 0
            elif(i == 0):
                d[th][j] = 1
            else:
                d[th][j] = d[th+1][j] + 1
            
    result = 0

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


    print(result)


### FIXED CODE ###

if __name__ == '__main__':
    h,w = list(map(int, input().split()))
    s = []
    for i in range(h):
        s.append(input())
    
    l = [[0 for i in range(w)] for j in range(h)]
    r = [[0 for i in range(w)] for j in range(h)]
    u = [[0 for i in range(w)] for j in range(h)]
    d = [[0 for i in range(w)] for j in range(h)]

    for i in range(h):
        for j in range(0, 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
            
            tw = w-j-1
            if(s[i][tw] == "#"):
                r[i][tw] = 0
            elif(j == 0):
                r[i][tw] = 1
            else:
                r[i][tw] = r[i][tw+1] + 1
            
            if(s[i][j] == "#"):
                u[i][j] = 0
            elif(i == 0):
                u[i][j] = 1
            else:
                u[i][j] = u[i-1][j] + 1
                
            th = h-i-1
            if(s[th][j] == "#"):
                d[th][j] = 0
            elif(i == 0):
                d[th][j] = 1
            else:
                d[th][j] = d[th+1][j] + 1
            
    result = 0

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


    print(result)
### BUGGY CODE ###

from fractions import gcd

MOD = 1000000007

def LCM(a, b):
    return a * b // gcd(a, b)

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

lcm = 1
for i in A: lcm = LCM(lcm, i)

ans = 0
for i in A:
    ans += lcm // i
    ans %= MOD

print(ans)

### FIXED CODE ###

from fractions import gcd

MOD = 1000000007

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

lcm = 1
for i in A: lcm = lcm * i // gcd(lcm, i)

ans = 0
for i in A: ans += lcm // i

print(ans % MOD)