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

S=input()
T=input()
s=len(S)
t=len(T)
#dp[i][j] Sのi文字目までとTのj文字目までで最大共通文字数
dp=[[0]*(t+1) for i in range(s+1)]
for i in range(s):
    for j in range(t):
        if S[i]==T[j]:
            dp[i+1][j+1]=max(dp[i][j]+1, dp[i][j])
        else:
            dp[i+1][j+1]=max(dp[i+1][j], dp[i][j+1])
ans=''
while s>0 and t>0:
    if dp[s][t]==dp[s-1][t]:
        s-=1
    elif dp[s][t]==dp[s][t-1]:
        t-=1
    else:
        s-=1
        t-=1
        ans+=T[t]
ans=ans[::-1]
print(ans)

### FIXED CODE ###

S=input()
T=input()
s=len(S)
t=len(T)
#dp[i][j] Sのi文字目までとTのj文字目までで最大共通文字数
dp=[[0]*(t+1) for i in range(s+1)]
for i in range(s):
    for j in range(t):
        if S[i]==T[j]:
            dp[i+1][j+1]=max(dp[i][j]+1, dp[i][j])
        else:
            dp[i+1][j+1]=max(dp[i+1][j], dp[i][j+1])
ans=''
while s>0 and t>0:
    if dp[s][t]==dp[s-1][t]:
        s-=1
    elif dp[s][t]==dp[s][t-1]:
        t-=1
    else:
        s-=1
        t-=1
        ans+=T[t]
ans=ans[::-1]
print(ans)
### BUGGY CODE ###

import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from scipy.sparse.csgraph import floyd_warshall
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations, combinations_with_replacement
from heapq import heappop, heappush, heapify
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def main():
    n = int(input())
    x = list(input())
    for i in range(n):
        x[i] = int(x[i])
    n = 2*10**5
    x = [1 for _ in range(n)]
    A = 0
    B = sum(x)
    for i in range(n):
        A += x[i]*pow(2,n-i-1,B)
        A %= B
    for i in range(n):
        if x[i] == 0:
            AA = A + pow(2,n-i-1)
            BB = B + 1
        else:
            AA = A - pow(2,n-i-1)
            BB = B - 1
        ans = 1
        while AA%BB:
            AA = AA%BB
            AAA = copy.deepcopy(AA)
            BB = 0
            while AAA != 0:
                BB += AAA%2
                AAA //= 2
            ans += 1
        print(ans)
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys, math, copy
sys.setrecursionlimit(10**8)

def main():
    n = int(input())
    x = list(input())
    for i in range(n):
        x[i] = int(x[i])
    A0 = 0
    A1 = 0
    B = sum(x)
    for i in range(n):
        if B+1 != 0:
            A0 += x[i]*pow(2,n-i-1,B+1)
            A0 %= B+1
        if B-1 != 0:
            A1 += x[i]*pow(2,n-i-1,B-1)
            A1 %= B-1
    for i in range(n):
        if x[i] == 0:
            BB = B + 1
            AA = A0 + pow(2,n-i-1,BB)
        else:
            BB = B - 1
            if BB == 0:
                AA = 0
            else:
                AA = A1 - pow(2,n-i-1,BB)
        ans = 1
        if BB == 0:
            print(0)
            continue
        while AA%BB != 0:
            AA = AA%BB
            AAA = AA
            BB = 0
            while AAA != 0:
                BB += AAA%2
                AAA //= 2
            ans += 1
        print(ans)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**3
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    P = LI()

    seat = [[1] * N for _ in range(N)]
    zero = [[1] * N for _ in range(N)]

    ans = 0

    for i in P:
        x = (i-1) % N
        y = (i-1) // N

        dp = [[INF] * N for _ in range(N)]
        d = 0
        q = collections.deque()
        q.append((x,y,d))
        dp[x][y] = 0
        min_cnt = INF
        while q:
            i,j,d = q.popleft()
            if d >= min_cnt: continue
            for di,dj in ((1,0),(0,1),(-1,0),(0,-1)):
                if not(0 <= i+di < N and 0 <= j+dj < N):
                    break
                if zero[i+di][j+dj] == 0:
                    break
                e = seat[i+di][j+dj]
                if dp[i+di][j+dj] > d+e:
                    dp[i+di][j+dj] = d+e
                    q.append((i+di,j+dj,d+e))
            else:
                continue
            min_cnt = min(min_cnt,d)

        seat[x][y] = 0
        if min_cnt == 0:
            q = collections.deque()
            q.append((x,y))
            zero[x][y] = 0
            while q:
                i,j = q.popleft()
                for di,dj in ((1,0),(0,1),(-1,0),(0,-1)):
                    if not(0 <= i+di < N and 0 <= j+dj < N): continue
                    if seat[i+di][j+dj] == 1 or zero[i+di][j+dj] == 0: continue
                    zero[i+di][j+dj] = 0
                    q.append((i+di,j+dj))
        ans += min_cnt
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    P = LI()

    s = []
    for i in range(N):
        for j in range(N):
            s.append(min(i,N-1-i,j,N-1-j))

    r = [1] * (N*N)

    ans = 0
    q = []
    for p in P:
        p -= 1
        ans += s[p]
        r[p] = 0
        q.append(p)
        while q:
            a = q.pop()
            nc = s[a] + r[a]

            if a >= N:
                if s[a-N] > nc:
                    s[a-N] = nc
                    q.append(a-N)
            if a + N < N*N:
                if s[a+N] > nc:
                    s[a+N] = nc
                    q.append(a+N)
            if a % N:
                if s[a-1] > nc:
                    s[a-1] = nc
                    q.append(a-1)
            if a % N < N -1:
                if s[a+1] > nc:
                    s[a+1] = nc
                    q.append(a+1)

    print(ans)

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

N, Q = map(int, input().split())
S = input()
A = []
B = [0]*Q
for n in range(N-1):
    if S[n:n+2] == "AC":
        A.append(n)
for n in range(Q):
    l, r = map(int, input().split())
    for m in range(len(A)):
        if A[m] >= l-1:
            if A[m] <= r-2:
                B[n] += 1
            else:
                break;
for n in range(Q):
    print(B[n])

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
A = [0]*(N-1)
B = [0]
C = []
for n in range(N-1):
    if S[n:n+2] == "AC":
        A[n] += 1
for n in range(N-1):
    B.append(B[n]+A[n])
for n in range(Q):
    l, r = map(int, input().split())
    C.append(B[r-1]-B[l-1])
for n in range(Q):
    print(C[n])
### BUGGY CODE ###

h, w, m = map(int, input().split())
hp = [0]*h
wp = [0]*w
hw = []
for _ in range(m):
    h1, w1 = map(int, input().split())
    hp[h1-1] += 1
    wp[w1-1] += 1
    hw.append([h1, w1])

h_max = max(hp)
w_max = max(wp)

hh = [i+1 for i, v in enumerate(hp) if v == h_max]
ww = [i+1 for i, v in enumerate(wp) if v == w_max]


ans = h_max + w_max
for hb in hh:
    for wb in ww:
        if [hb, wb] not in hw:
            print(ans)
            exit()
print(ans-1)

### FIXED CODE ###

def main():
    h, w, m = map(int, input().split())
    hp = [0]*h
    wp = [0]*w
    hw = set()
    for _ in range(m):
        h1, w1 = map(int, input().split())
        hp[h1-1] += 1
        wp[w1-1] += 1
        hw.add((h1, w1))

    h_max = max(hp)
    w_max = max(wp)

    hh = [i+1 for i, v in enumerate(hp) if v == h_max]
    ww = [i+1 for i, v in enumerate(wp) if v == w_max]
    ans = h_max + w_max

    for hb in hh:
        for wb in ww:
            if (hb, wb) not in hw:
                print(ans)
                exit()
    print(ans-1)


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

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

movable = [0]*N
i = 0
while i < N-1-max(movable):
    j = i
    while j < N-1 and H[j] >= H[j+1]:
        movable[i] += 1
        j += 1
    i = i + movable[i] + 1

print(max(movable))

### FIXED CODE ###

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

movable = [0]*N
i = 0
while i < N-1:
    j = i
    while j < N-1 and H[j] >= H[j+1]:
        movable[i] += 1
        j += 1
    i = i + movable[i] + 1

print(max(movable))
### BUGGY CODE ###

A, B, C, X, Y = map(int, input().split())

price = 5000 * 100000 * 2

for a in range(X+1):
    for b in range(Y+1):
        for c in range(min([2*(X-a), 2*(Y-b)]), X + Y + 1):
            if X <= a + c // 2 and Y <= b + c // 2:
                if price > A*a+B*b+C*c:
                    price = A*a+B*b+C*c

print(price)


### FIXED CODE ###

A, B, C, X, Y = map(int, input().split())

price = min(A*X+B*Y, C*2 * (max(X, Y)))

is_break = 0

for i in range(100000):
    if price >= A*max(0, X - i) + B*max(0, Y - i)+2*C*i:
        price = A*max(0, X - i) + B*max(0, Y - i)+2*C*i
print(price)
### BUGGY CODE ###

def maina(n):
    return n-1

N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]
score = [int(K) for __ in range(N)]

for i in range(Q):
    score = list(map(maina, score))
    score[A[i]-1] = score[A[i]-1]+1
for k in range(N):
    if score[k] <= 0:
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

n, k, q = map(int, input().split())
p = k-q
l = [p]*n
for i in range(q):
    a = int(input())
    l[a-1] += 1
for k in range(n):
    print("Yes" if l[k]>0 else "No")
### BUGGY CODE ###

from collections import Counter
s = input()
# 累積和の準備
sum_list = [0]*(len(s)+1)  # s[0]は０であってほしいから配列数ひとつおおい
for i in range(1, len(s) + 1):
    sum_list[i] += sum_list[i-1] + int(s[len(s)-i])*10**(i-1)
"""
(s[j]-s[i]/10**i)が区間の整数
区間の整数が2019で割り切れればよい
つまり、(s[j]-s[i]/10**i)≡0 (mod=2019)
ここで10**iと2019(素数)は互いに素なので、
10**iをかけて上の式はs[j]-s[i]≡0 (mod=2019)と同値
s[j]≡s[i] (mod=2019)となる。
"""
# s[i]のmod=2019を記憶しておくリスト用意
mod_s = [[] for _ in range(len(sum_list))]
mod_s[0] = 0
for i in range(1, len(sum_list)):
    mod_s[i] = sum_list[i] % 2019

#print(mod_s)
c = Counter(mod_s)
ans = 0
#print(c)
for value in c.values():
    ans += value*(value-1)//2
print(ans)






### FIXED CODE ###

from collections import Counter
s = input()
n = len(s)
# 累積和の準備
sum_list = [0]*(n+1)  # s[0]は０であってほしいから配列数ひとつおおい
_10 = 1
for i in range(1, n + 1):
    sum_list[i] += (sum_list[i-1] + int(s[n-i])*_10 % 2019) % 2019  # ここでmodしておく
    _10 = _10*10 %2019
"""
(s[j]-s[i]/10**i)が区間の整数
区間の整数が2019で割り切れればよい
つまり、(s[j]-s[i]/10**i)≡0 (mod=2019)
ここで10**iと2019(素数)は互いに素なので、
10**iをかけて上の式はs[j]-s[i]≡0 (mod=2019)と同値
s[j]≡s[i] (mod=2019)となる。
"""
c = Counter(sum_list)
ans = 0

for key in c.keys():
    ans += c[key]*(c[key]-1)//2
print(ans)
### BUGGY CODE ###

n = int(input())
h = list(map(int, input().split()))
h.sort()

def triangle(n,h):
    x = 0
    for i in range(0,n-2):
        for j in range(i+1,n-1):
            for k in range(j+1, n):
                if h[k] < h[j] + h[i] :
                    x = x + 1
    return x
print(triangle(n,h))

### FIXED CODE ###

import bisect
N = int(input())
#ソートしておく
L = sorted(list(map(int, input().split())))
ans = 0
 
#短い2辺を総当たりで選択
for i in range(N - 2):
  for j in range(i + 1, N - 1):
    #小さい順に並べた時の成立条件
    # l1 + l2 > l3
    l12 = L[i] + L[j]
    #l2の隣から　l12以下のところまで全部が対象、成立しない場合
    #ans += max(bisect.bisect_left(L, l12) - j - 1, 0)
    ans += bisect.bisect_left(L, l12) - j - 1
print(ans)
### BUGGY CODE ###

n = int(input())
if n == 1:
    print(1)
    exit()
a = 1
b = n
for i in range(1, 10**10):
    if n % i == 0:
        if i > n // i:
            print(min(len(str(i)), len(str(b))))
            exit()
        a = i
        b = n // i

### FIXED CODE ###

n = int(input())
if n == 1:
    print(1)
    exit()
a = 1
b = n
for i in range(1, 10**5):
    if n % i == 0:
        if i > n // i:
            print(min(len(str(i)), len(str(b))))
            exit()
        a = i
        b = n // i
print(len(str(b)))
### BUGGY CODE ###

import numpy as np
n,m,q = map(int,input().split())
lr = []
for i in range(m):
    l = list(map(int,input().split()))	
    lr.append(l)
 
ass = np.zeros((n,n))
ans = np.zeros((n,n))   
        
for i in range(m):
    ass[lr[i][0]-1][lr[i][1]-1] += 1
        
#print(ass)

for i in range(n):
    for j in range(n):
        if i == 0:
            ans[n-1][j] = sum(ass[n-1][:j+1:])
        else:
            ans[n-1-i][j] = sum(ass[n-1-i][:j+1:]) + ans[n-i][j]
#print(ass)
#print(ans)

for i in range(q):
    p,qa = map(int,input().split())
   
    print(int(ans[p-1][qa-1]))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m,q = map(int,input().split())

res = [[0]*n for i in range(n)]
for i in range(m):
    L,r = map(int,input().split())
    L -= 1
    r -= 1
    res[r][0] += 1
    if L != n-1:
        res[r][L+1] -= 1

for i in range(n):
    for j in range(1,n):
        res[i][j] += res[i][j-1]
for i in range(n):
    for j in range(1,n):
        res[j][i] += res[j-1][i]
for i in range(q):
    p,q = map(int,input().split())
    print(res[q-1][p-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

def main():
    s = input()
    q = int(input())

    r_flg = True

    for i in range(q):
        query = input().split()

        # query 1
        if query[0] == '1':
            r_flg = not r_flg
        
        # query 2
        else:
            # Fi = 1
            if query[1] == '1':
                if r_flg:
                    s = query[2] + s
                else:
                    s = s + query[2]
            # Fi = 2
            else:
                if r_flg:
                    s = s + query[2]
                else:
                    s = query[2] + s

        # print('cont:{}, s:{}, r_flg:{}'.format(i, s, r_flg))

    if not r_flg:
        s = s[::-1]

    print(s)

if __name__ == "__main__":
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-

def main():
    s = input()
    q = int(input())
    q_list = list()

    for i in range(q):
        q_list.append(input())

    r_flg = True
    s_str = ''
    e_str = ''

    for query in q_list:
        # query 1
        if query[0] == '1':
            r_flg = not r_flg
        
        # query 2
        else:
            # Fi = 1
            if query[2] == '1':
                if r_flg:
                    s_str = query[4] + s_str
                else:
                    e_str = e_str + query[4]
            # Fi = 2
            else:
                if r_flg:
                    e_str = e_str + query[4]
                else:
                    s_str = query[4] + s_str

        # print('cont:{}, s:{}, r_flg:{}'.format(i, s, r_flg))

    s = s_str + s + e_str

    if not r_flg:
        s = ''.join(reversed(s))

    print(s)

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

def ints():
  return [int(x) for x in input().split()]
def ii():
  return int(input())

import math

N, K = ints()
A = list(sorted(ints()))
F = list(reversed(sorted(ints())))

afmax = max([a*f for a in A for f in F])

def binsearch(cant_lower, can_upper):
  if cant_lower+1==can_upper:
    return can_upper

  m = (cant_lower + can_upper)//2

  if can(m):
    return binsearch(cant_lower, m)
  else:
    return binsearch(m, can_upper)

def can(seiseki):
  k = K
  for i in range(N):
    if A[i]*F[i]>seiseki:
      k -= math.ceil((A[i]*F[i]-seiseki)/F[i])
  return k>=0

w = binsearch(-1, afmax)
print(w)



### FIXED CODE ###

def ints():
  return [int(x) for x in input().split()]
def ii():
  return int(input())

import math

N, K = ints()
A = list(sorted(ints()))
F = list(reversed(sorted(ints())))
AF = [A[i]*F[i] for i in range(N)]

afmax = max(AF)

def can(max_af):
  k = K
  for i in range(N):
    af = AF[i]
    if af>max_af:
      max_ai = max_af // F[i]
      k -= A[i]-max_ai
      if k<0:
        return False
  return k>=0

l = -1
r = afmax
while r-l>1:
  m = (l+r)//2
  if can(m):
    r = m
  else:
    l = m
print(r)
### BUGGY CODE ###

from collections import deque
INF = 10 ** 5
n, x, y = (int(_) for _ in input().split())
dict = {}
table = [[INF] * (n+1) for i in range(n+1)]
res = [0] * n

def bfs(i): #頂点iから行ける場所を探す
  deq = deque()
  node_lst = [-1] * (n+1) #訪れた頂点を管理
  node_lst[i] = 0
  deq.extend(dict[i])
  for j in dict[i]:
    node_lst[j] = node_lst[i] + 1
  while deq:
    p = deq.popleft()
    for j in dict[p]:
      if node_lst[j] == -1:
        deq.append(j)
        node_lst[j] = node_lst[p] + 1
  for j in range(1, n+1):
    if node_lst[j] < 1:
      continue
    a, b = i, j
    if x > y:
      a, b = b, a
    table[a][b] = min(table[a][b], node_lst[j])
  
#入力
for i in range(1, n+1):
  if i == 1:
    dict[i] = [2]
  elif i == n:
    dict[i] = [n - 1]
  else:
    dict[i] = [i-1, i+1]
dict[x] += [y]
dict[y] += [x]

#bfs
for i in range(1, n+1):
  bfs(i)
for i in range(1, n+1):
  for j in range(i, n+1):
    if table[i][j] == INF:
      continue
    res[table[i][j]] += 1
    
#出力
for i in range(1, n):
  print(res[i])


### FIXED CODE ###

from collections import deque
INF = 10 ** 5
n, x, y = (int(_) for _ in input().split())
dict = {}
table = [[INF] * (n+1) for i in range(n+1)]
res = [0] * n

def bfs(i): #頂点iから行ける場所を探す
  deq = deque()
  node_lst = [-1] * (n+1) #訪れた頂点を管理
  node_lst[i] = 0
  deq.extend(dict[i])
  for j in dict[i]:
    node_lst[j] = node_lst[i] + 1
  while deq:
    p = deq.popleft()
    for j in dict[p]:
      if node_lst[j] == -1:
        deq.append(j)
        node_lst[j] = node_lst[p] + 1
  for j in range(1, n+1):
    if node_lst[j] < 1:
      continue
    a, b = i, j
    if x > y:
      a, b = b, a
    table[a][b] = min(table[a][b], node_lst[j])
  
#入力
for i in range(1, n+1):
  if i == 1:
    dict[i] = [2]
  elif i == n:
    dict[i] = [n - 1]
  else:
    dict[i] = [i-1, i+1]
dict[x] += [y]
dict[y] += [x]

#bfs
for i in range(1, n+1):
  bfs(i)
  
#出力
for i in range(1, n+1):
  for j in range(i, n+1):
    if table[i][j] == INF:
      continue
    res[table[i][j]] += 1
for i in range(1, n):
  print(res[i])
### BUGGY CODE ###

import copy
n=int(input())
x=list(input())
b=[]
for i in range(2**18):
  b.append(format(i,'0'+str(18)+'b'))
  if i>n+1:
    break
ct=[0]*(n+1)
for i in range(1,n):
  ct1=0
  for j in range(len(b[i])):
    if b[i][j]=='1':
      ct1+=1
  ct[i]=i%ct1

CT=0
for i in range(n):
  if x[i]=='1':
    CT+=1

moda=[1]
modb=[1]
modc=[1]
for i in range(n-1):
  if CT>=2:
    moda.append(moda[-1]*2%(CT-1))
  if CT>=1:
    modb.append(modb[-1]*2%CT)
  modc.append(modc[-1]*2%(CT+1))


x.reverse()
za=0
zb=0
zc=0
for i in range(n):
  if x[i]=='1':
    if CT>=2:
      za+=moda[i]
      za%=(CT-1)
    if CT>=1:
      zb+=modb[i]
      zb%=CT
    zc+=modc[i]
    zc%=(CT+1)
x.reverse()
moda.reverse()
modc.reverse()

for i in range(n):
  y=copy.copy(x)
  y2=y[i]
  y[i]=str(1-int(y[i]))
  ct1=0
  if y2=='1':
    ct1=CT-1
  else:
    ct1=CT+1
  if ct1==0:
    print(0)
  else:
    if y2=='1':
      z=za
      z-=moda[i]
      z%=ct1
    else:
      z=zc
      z+=modc[i]
      z%=ct1
    
    ans=1
    while z!=0:
      z=ct[z]
      ans+=1
    print(ans)

### FIXED CODE ###

import copy
n=int(input())
x=list(input())
b=[]
for i in range(2**18):
  b.append(format(i,'0'+str(18)+'b'))
  if i>n+1:
    break
ct=[0]*(n+1)
for i in range(1,n):
  ct1=0
  for j in range(len(b[i])):
    if b[i][j]=='1':
      ct1+=1
  ct[i]=i%ct1

CT=0
for i in range(n):
  if x[i]=='1':
    CT+=1

moda=[1]
modb=[1]
modc=[1]
for i in range(n-1):
  if CT>=2:
    moda.append(moda[-1]*2%(CT-1))
  if CT>=1:
    modb.append(modb[-1]*2%CT)
  modc.append(modc[-1]*2%(CT+1))


x.reverse()
za=0
zb=0
zc=0
for i in range(n):
  if x[i]=='1':
    if CT>=2:
      za+=moda[i]
      za%=(CT-1)
    if CT>=1:
      zb+=modb[i]
      zb%=CT
    zc+=modc[i]
    zc%=(CT+1)
x.reverse()
moda.reverse()
modc.reverse()

for i in range(n):
  y2=x[i]
  if y2=='1':
    ct1=CT-1
  else:
    ct1=CT+1
  if ct1==0:
    print(0)
  else:
    if y2=='1':
      z=za
      z-=moda[i]
      z%=ct1
    else:
      z=zc
      z+=modc[i]
      z%=ct1
    
    ans=1
    while z!=0:
      z=ct[z]
      ans+=1
    print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(5000)

H, W = map(int, input().split())
F = [input() for _ in range(H)]
FH = [[0]*W for _ in range(H)]
FV = [[0]*W for _ in range(H)]


def search(x, y, c, d):
    if not (0 <= x < H and 0 <= y < W):
        return c
    if F[x][y] == "#":
        return c
    else:
        if d == "h":
            return search(x, y+1, c+1, "h")
        else:
            return search(x+1, y, c+1, "v")

ans = 0
for i in range(H):
    for j in range(W):
        if F[i][j] == "#":
            FH[i][j] = 0
        elif F[i][j] == ".":
            if FH[i][j-1] > 0:
                FH[i][j] = FH[i][j-1]
            else:
                FH[i][j] = search(i, j+1, 1, "h")

ans = 0
for i in range(H):
    for j in range(W):
        if F[i][j] == "#":
            FV[i][j] = 0
        elif F[i][j] == ".":
            if FV[i-1][j] > 0:
                FV[i][j] = FV[i-1][j]
            else:
                FV[i][j] = search(i+1, j, 1, "v")

        if FH[i][j] + FV[i][j] > ans:
            ans = FH[i][j] + FV[i][j]

if ans >= 2:
    print(ans-1)
else:
    print(ans)


### FIXED CODE ###

import numpy as np

H, W = map(int, input().split())
F = np.array([[1 if i == "." else 0 for i in input()] for _ in range(H)])
FU = np.zeros((H, W), dtype=int)
FD = np.zeros((H+1, W), dtype=int)
FL = np.zeros((H, W), dtype=int)
FR = np.zeros((H, W+1), dtype=int)

for i in range(H):
    FU[i] += (FU[i-1]+1)*F[i]

for i in range(H-1, -1, -1):
    FD[i] += (FD[i+1]+1)*F[i]

for i in range(W):
    FL[:, i] += (FL[:, i-1]+1)*F[:, i]

for i in range(W-1, -1, -1):
    FR[:, i] += (FR[:, i+1]+1)*F[:, i]

FV = FU + FD[:-1] - 1
FH = FL + FR[:, :-1] - 1
ans = np.max(FV+FH)
if ans >= 2:
    print(ans-1)
else:
    print(ans)
### BUGGY CODE ###

a,b,c,d = map(int, input().split())

count = 0
for i in range(a,b+1):
  if i%c != 0 and i%d != 0:
    count += 1
print(count)

### FIXED CODE ###

import fractions

a,b,c,d = map(int, input().split())

a -= 1

# a~bの数でcで割り切れる数の個数は
divC = b//c - a//c
# a~bの数でdで割り切れる数の個数は
divD = b//d - a//d
# a~bの数でc,dの最小公倍数で割り切れる数の個数は
l = (c*d) // fractions.gcd(c,d)
divU= b//l - a//l
divSum = divC+divD-divU


print(b-a - divSum)
### BUGGY CODE ###

N = int(input())
slist = list(map(int, input().split()))
ans = 0
for C in range(1,N-1,1):
    flg = [False for i in range(N)]
    score = 0
    for k in range((N-1)//C):
        if (k-1)*C == N-1-k*C: #一つ前に選んだところ
            break
        if 2*k*C == N-1: #今から選ぶ二つが同じところ
            break
        score += slist[k*C]+slist[N-1-k*C]
        ans = max(ans, score)
print(ans)

### FIXED CODE ###

N = int(input())
slist = list(map(int, input().split()))
ans = 0
for C in range(1,N-1,1):
    score = 0
    for k in range((N-1)//C):
        if (k-1)*C == N-1-k*C: #一つ前に選んだところ
            break
        if 2*k*C == N-1: #今から選ぶ二つが同じところ
            break
        score += slist[k*C]+slist[N-1-k*C]
        ans = max(ans, score)
print(ans)
### BUGGY CODE ###

mod = 10**9+7
s=[x for x in input()]
n=len(s)
dp=[[0 for i in range(13)] for j in range(n+1)]
dp[0][0]=1
for i in range(n):
  for j in range(10):
    if s[i]!='?' and s[i]!=str(j):
      continue
    for k in range(13):
      dp[i+1][(k*10+j)%13] += dp[i][k]
  for j in range(13):
    dp[i+1][j]=dp[i+1][j]%mod
print(dp[n][5])

### FIXED CODE ###

mod = 10**9+7
s=[x for x in input()]
n=len(s)
dp=[[0 for i in range(13)] for j in range(n+1)]
dp[0][0]=1
for i in range(n):
  for j in range(10):
    if s[i]!='?' and s[i]!=str(j):
      continue
    for k in range(13):
      dp[i+1][(k*10+j)%13] += dp[i][k]
  for j in range(13):
    dp[i+1][j]=dp[i+1][j]%mod
print(dp[n][5])