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

import numpy as np

def widespread_2():
	n, a, b = map(int, raw_input().split(" "))
	monsters = []
	for i in range(n):
		monsters.append(int(raw_input()))
	# as a>b holds
	dif_a_b = a - b
	monsters = np.array(monsters)
	max_ans = int(max(monsters)/b)+1
	min_ans = int(max(monsters)/a)-1
	# using binary search
	while True:
		current_attepmt = int((max_ans+min_ans)/2)
		# print current_attepmt
		re = _inner_widespread_2(monsters, current_attepmt, a, b)
		# print re
		if re>current_attepmt:
			min_ans = current_attepmt
		elif re<current_attepmt:
			max_ans = current_attepmt
		else:
			print current_attepmt
			return

		if current_attepmt==int((max_ans+min_ans)/2):
			print max_ans
			return


def _inner_widespread_2(monsters, attemps, a, b):
	dif = a-b
	re = 0
	for e in monsters:
		update_e = e-b*attemps
		if update_e>0:
			if update_e%dif==0:
				re = re+update_e/dif
			else:
				re = re + int(update_e/dif)+1
	return re


if __name__ == "__main__":
	widespread_2()

### FIXED CODE ###

def widespread_2():
	n, a, b = map(int, raw_input().split(" "))
	monsters = []
	for i in range(n):
		monsters.append(int(raw_input()))
	# as a>b holds
	dif_a_b = a - b
	max_ans = int(max(monsters)/b)+1
	min_ans = int(max(monsters)/a)-1
	# using binary search
	while min_ans+1 < max_ans:
		current_attepmt = (max_ans+min_ans)/2
		# print current_attepmt
		re = _inner_widespread_2(monsters, current_attepmt, a, b)
		# print re
		if re>current_attepmt:
			min_ans = current_attepmt
		else:
			max_ans = current_attepmt
	print max_ans


def _inner_widespread_2(monsters, attemps, a, b):
	dif = a-b
	re = 0
	for e in monsters:
		update_e = e-b*attemps
		if update_e>0:
			if update_e%dif==0:
				re = re+update_e/dif
			else:
				re = re + int(update_e/dif)+1
	return re


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

S = input()

ans = 0
for i in range(len(S)):
    Sum = int(S[i]) % 3
    for j in range(i+1, len(S)):
        Sum = (int(S[j]) + Sum) % 3
        if Sum != 0:
            continue
        if int(S[i:j+1]) % 2019 == 0:
            ans += 1

print(ans)

### FIXED CODE ###

from collections import Counter

S = input()
N = len(S)

dp = [0] * N
dp[N-1] = int(S[N-1])
times = 10
for i in reversed(range(1, N)):
    dp[i-1] = (dp[i] + times * int(S[i-1])) % 2019
    times *= 10
    times %= 2019

T = Counter(dp)
ans = T[0]
for t in T.values():
    ans += t*(t-1)//2

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

N = int(input())
L = []
for i in range(1,N + 1):
  if N % i == 0:
    div = int(N / i)
    distance = (div + i - 2)
    L.append(distance)
    
print(min(L))

### FIXED CODE ###

n = int(input())

distance = 10 ** 12

i = 1

while i * i <= n:
  if n % i == 0:
    m = int(n / i)
    move = (m - 1) + (i - 1)
    if move < distance:
      distance = move
  i += 1

print(distance)
### BUGGY CODE ###

n = int(input())
l = []
for i in range(n):
    i = list(map(int,input().split()))
    l.append(i)
tmp = 0

for j in reversed(range(n)):
    l[j][0] += tmp
    while  l[j][0]%l[j][1] != 0:
        l[j][0] += 1
        tmp += 1

print(tmp)

### FIXED CODE ###

n = int(input())
l = []
for i in range(n):
    i = list(map(int,input().split()))
    l.append(i)
tmp = 0

for j in reversed(range(n)):
    l[j][0] += tmp
    if l[j][0]%l[j][1] != 0:
        tmp += l[j][1] - l[j][0]%l[j][1]

print(tmp)
### BUGGY CODE ###

l=input()
mod=pow(10,9)+7
import sys
sys.setrecursionlimit(10**7)

def func(li):
  if '0' not in li:
    return pow(3,len(li),mod)
  elif len(li)==1:
    if li=='1':
      return 3
    else:
      return 1
  elif li[0]=='0':
    return func(li[1:])%mod
  else:
    ret=(2*func(li[1:]))%mod
    ret+=pow(3,len(li)-1,mod)
    return ret%mod
print(func(l))


### FIXED CODE ###

l=input()
n=len(l)
mod=pow(10,9)+7
import sys
sys.setrecursionlimit(10**7)
#dp1,dp2=[0]*n,[0]*n
dp1,dp2=0,1
for i in range(n):
  if l[i]=='0':
    dp1*=3
  else:
    dp1*=3
    dp1+=dp2
    dp2*=2
  dp1%=mod
  dp2%=mod
print((dp1+dp2)%mod)
### BUGGY CODE ###

# Surrounded Nodes
from collections import deque
import sys
sys.setrecursionlimit(10**8)
mod = 10**9 + 7
N = int(input())
G = [[] for i in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
S = -1
for i in range(1, N+1):
    if len(G[i]) == 1:
        S = i
        break
visited = [False for i in range(N+1)]
parent = [-1 for i in range(N+1)]
count = [1 for i in range(N+1)]

ans = N*pow(2, N-1, mod)
stack = deque()


def dfs(node):
    visited[node] = True
    for child in G[node]:
        if visited[child] == False:
            parent[child] = node
            stack.append((node, child))
            dfs(child)


dfs(S)
while stack:
    mom, child = stack.pop()
    count[mom] += count[child]
ans = 0
for i in range(1, N+1):
    if len(G[i]) > 1:
        ans += pow(2, N-1, mod)
        for x in G[i]:
            if x != parent[i]:
                ans -= pow(2, count[x], mod)
        ans -= pow(2, N-count[i], mod)
        ans += len(G[i]) - 1
D = pow(2, N, mod)
print(ans*pow(D, mod-2, mod) % mod)

### FIXED CODE ###

# Surrounded Nodes
from collections import deque
import sys
sys.setrecursionlimit(10**8)
mod = 10**9 + 7
N = int(input())
G = [[] for i in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
S = -1
for i in range(1, N+1):
    if len(G[i]) == 1:
        S = i
        break
visited = [False for i in range(N+1)]
parent = [-1 for i in range(N+1)]
count = [1 for i in range(N+1)]

ans = N*pow(2, N-1, mod)
stack = deque()


def dfs(node):
    visited[node] = True
    for child in G[node]:
        if visited[child] == False:
            parent[child] = node
            stack.append((node, child))
            dfs(child)


powers = [1 for i in range(2*10**5+1)]
for i in range(1, 2*10**5+1):
    powers[i] = powers[i-1]*2 % mod

dfs(S)
while stack:
    mom, child = stack.pop()
    count[mom] += count[child]
ans = 0
for i in range(1, N+1):
    if len(G[i]) > 1:
        ans += powers[N-1]
        for x in G[i]:
            if x != parent[i]:
                ans -= powers[count[x]]
        ans -= powers[N-count[i]]
        ans += len(G[i]) - 1
        ans %= mod
D = pow(2, N, mod)
print(ans*pow(D, mod-2, mod) % mod)
### BUGGY CODE ###

n, k = map(int, input().split())
a_list = []
for i in range(n):
	a, b = map(int, input().split())
	a_list.extend([a] * b)
	if a_list.count(1) >= k:
		break
a_list.sort()
print(a_list[k-1])

### FIXED CODE ###

n, k = map(int, input().split())
a_list = []
for i in range(n):
	a, b = map(int, input().split())
	a_list.append([a, b])
a_list.sort(key=lambda x: x[0])
for i in range(n):
	k -= a_list[i][1]
	if k <= 0:
		print(a_list[i][0])
		break
### BUGGY CODE ###

import fractions

MOD = 1000000007
inv = [1] * 1001001

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

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

for i in range(2, 1001001):
    inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD

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)
### BUGGY CODE ###

# LCS: Longest common subsequence
# dp[i][j]: Sのi-1番目まで, Tのj-1番目まででの最長共通文字列
# dp[0][0] = 0 長さ0の文字列
# dp[0][1] = 0 長さ1の文字列と長さ0の文字列
# dp[1][0] = 0 長さ0の文字列と長さ1の文字列
# dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (S[i] != T[j])
# dp[i][j] = max(
#                dp[i-1][j-1]+1  (共通文字列を利用する),
#                dp[i-1][j]        (共通文字列を利用しない),
#                dp[i][j-1]        (共通文字列を利用しない),
#            )


dp = [[[0, ''] for _ in range(3001)] for _ in range(3001)]

def main():
    S = input()
    T = input()

    result = solve(S, T)
    print(result[1])



def solve(S, T):
    for i, s in enumerate(S, start=1):
        for j, t in enumerate(T, start=1):
            if s != t:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1], key=lambda x: x[0])
            else:
                a = dp[i-1][j-1][0]
                b = dp[i-1][j][0]
                c = dp[i][j-1][0]
                if a >= b and a >= c:
                    dp[i][j] = [dp[i-1][j-1][0] + 1, dp[i-1][j-1][1] + s]
                elif b>=a and b>= c:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i][j-1]
    return dp[len(S)][len(T)]


if __name__ == "__main__":
    main()


### FIXED CODE ###

# LCS: Longest common subsequence
# dp[i][j]: Sのi-1番目まで, Tのj-1番目まででの最長共通文字列
# dp[0][0] = 0 長さ0の文字列
# dp[0][1] = 0 長さ1の文字列と長さ0の文字列
# dp[1][0] = 0 長さ0の文字列と長さ1の文字列
# dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (S[i] != T[j])
# dp[i][j] = max(
#                dp[i-1][j-1]+1  (共通文字列を利用する),
#                dp[i-1][j]        (共通文字列を利用しない),
#                dp[i][j-1]        (共通文字列を利用しない),
#            )


dp = [[0 for _ in range(3001)] for _ in range(3001)]


def main():
    S = input()
    T = input()

    result = solve(S, T)
    print(result)


def solve(S, T):
    for i in range(1, len(S) + 1):
        for j in range(1, len(T) + 1):
            if S[i - 1] != T[j - 1]:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i-1][j-1])
            else:
                dp[i][j] = max(dp[i - 1][j - 1] + 1, dp[i - 1][j], dp[i][j - 1])
    result = ""
    i = len(S)
    j = len(T)
    while dp[i][j] != 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            result += S[i-1]
            i -= 1
            j -= 1
    return "".join(reversed(result))


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

N,M = map(int,input().split())
P = []
S = []
for _ in range(M):
  p,s = map(str,input().split())
  P.append(p)
  S.append(s)
ac = 0
wa = 0

for i in range(1,N+1):
  count_wa = 0
  for j in range(M):
    if int(P[j]) == i:
      if S[j] == 'WA':
        count_wa += 1
      else:
        wa += count_wa
        ac += 1
        break
print(ac,wa)

### FIXED CODE ###

N,M = map(int,input().split())
P = []
S = []
for _ in range(M):
  p,s = map(str,input().split())
  P.append(int(p))
  S.append(s)
ac = ['WA']*N
wa = [0]*N

for i in range(M):
  if S[i] == 'WA':
    if ac[P[i]-1] == 'WA':
      wa[P[i]-1] += 1
  else:
    ac[P[i]-1] = 'AC'
for j in range(N):
  if ac[j] == 'WA':
    wa[j] = 0
print(ac.count('AC'),sum(wa))
### BUGGY CODE ###

n = int(input())
arr = list(map(int, input().split()))
q = int(input())
for t in range(q):
	b, c = map(int, input().split())
	for x in range(len(arr)):
		if arr[x] == b:
			arr[x] = c
	sum = 0
	for y in range(len(arr)):
		sum = sum + arr[y]
	print(sum)

### FIXED CODE ###

n = int(input())
arr = list(map(int, input().split()))
sum = 0
for x in arr:
	sum = sum+x
q = int(input())
newarr = [0]*10**6
for x in arr:
	newarr[x]=newarr[x]+1
for t in range(q):
	b, c = map(int, input().split())
	sum = sum - b*newarr[b]
	sum = sum + c*newarr[b]
	newarr[c] = newarr[c] + newarr[b]
	newarr[b] = 0
	print(sum)
### BUGGY CODE ###

dic = []
ind = {"A":0,"C":1,"G":2,"T":3}
dic = [[[],[],[],[]] for i in range(12)]
n = int(input())
for i in range(n):
    a = input()
    t=a.split()
    if t[0] == "insert":
        dic[len(t[1])-1][ind[t[1][0]]].append(t[1])
    else:
        if t[1] in dic[len(t[1])-1][ind[t[1][0]]]:
            print("yes")
        else:
            print("no")

### FIXED CODE ###

dic=dict()
n = int(input())
for i in range(n):
    a = input()
    t=a.split()
    if t[0] == "insert":
        dic[t[1]] = True
    else:
        if t[1] in dic:
            print("yes")
        else:
            print("no")
### BUGGY CODE ###

from itertools import combinations

N, K = map(int,input().split())
lists = combinations(range(N),K)
s = list(map(int,input().split()))
min_result = 10 ** 9
for li in lists:
    total = 0
    for l in li:
        total += s[l]
    min_result = min(min_result,total)

print(min_result)

### FIXED CODE ###

N, K = map(int,input().split())
s = list(map(int,input().split()))
s.sort()
print(sum(s[:K]))
### BUGGY CODE ###

from collections import deque
H,W=map(int,input().split())
A=[input() for _ in range(H)]
visited_area=[[-1]*W for _ in range(H)]
stack=deque([])
for h,c_h in enumerate(A):
    for w,c_w in enumerate(c_h):
        if c_w=='#':
            stack.append([h,w])
def bfs(A,visited_area,stack):
    kotae = 0
    for a in range(H):
        kotae += A[a].count('#')
    while kotae<H*W:
        h, w = stack.pop()
        for x, y in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h = h + x
            new_w = w + y
            if new_h < 0 or new_h >= H or new_w < 0 or new_w >= W:
                continue
            if A[new_h][new_w] == '.' and visited_area[new_h][new_w] == - 1:
                visited_area[new_h][new_w] = visited_area[h][w]+1
                stack.appendleft([new_h, new_w])
                kotae+=1
bfs(A,visited_area,stack)
answers=[]
for a in visited_area:
    answers.append(max(a))
print(max(answers)+1)


### FIXED CODE ###

from collections import deque
H,W=map(int,input().split())
A=[input() for _ in range(H)]
visited_area=[[-1]*W for _ in range(H)]
stack=deque([])
for h,c_h in enumerate(A):
    for w,c_w in enumerate(c_h):
        if c_w=='#':
            stack.append([h,w])
def bfs(A,visited_area,stack):
    kotae = 0
    for a in range(H):
        kotae += A[a].count('#')
    while kotae<H*W:
        h, w = stack.pop()
        for x, y in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h = h + x
            new_w = w + y
            if new_h < 0 or new_h >= H or new_w < 0 or new_w >= W:
                continue
            if A[new_h][new_w] == '.' and visited_area[new_h][new_w] == - 1:
                visited_area[new_h][new_w] = visited_area[h][w]+1
                stack.appendleft([new_h, new_w])
                kotae+=1
bfs(A,visited_area,stack)
answers=[]
for a in visited_area:
    answers.append(max(a))
print(max(answers)+1)
### BUGGY CODE ###

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

ans = 1
for i in range(n):
    ans *= a[i]
if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

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

ans = 1
if 0 in a:
    print(0)
    exit()
for i in range(n):
    ans *= a[i]
    if ans > 10**18:
        print(-1)
        exit()
else:
    print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
MOD = 10 ** 9 + 7
digit = 60
o=[0]*digit
z=[0]*digit

for i in a:
  for j in range(digit):
    if (i >> j) & 1:
      o[j] += 1
    else:
      z[j] += 1
ans = 0
for j in range(digit):
  ans += (o[j]*z[j]*2**j)
  ans %= MOD
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
MOD = 10 ** 9 + 7
digit = 60
o=[0]*digit
z=[0]*digit

for i in a:
  for j in range(digit):
    if (i >> j) & 1:
      o[j] += 1
    else:
      z[j] += 1
ans = 0    
for j in range(digit):
  ans += (o[j]*z[j]*pow(2,j,MOD))
print(ans % MOD)
### BUGGY CODE ###

n=int(input())
lst=[]
for i in range(n):
 lst.extend(input().split())
 new_list=set(lst)
print(len(new_list))

### FIXED CODE ###

n=int(input())
lst={}
for i in range(n):
  lst[input()]=1
print(len(lst))
### BUGGY CODE ###

N=int(input())
*X,=map(int,input().split())


import statistics

for i in range(len(X)):
    t=X[:i]+X[i+1:]
    print(statistics.median(t))

### FIXED CODE ###

N=int(input())
*X,=map(int,input().split())
s=sorted(X)

t1=s[N//2-1]
t2=s[N//2]

for x in X:
    if x<=t1:
        print(t2)
    else:
        print(t1)
### BUGGY CODE ###

N,K=map(int,input().split())
a=list(map(int,input().split()))
queue=[]
pre=1
for i in range(K):
    aa=a.pop(0)
    pre*=aa
    queue.append(aa)
for i in range(K,N,1):
    aq=queue.pop(0)
    aa=a.pop(0)
    queue.append(aa)
    now=pre*aa//aq
    if now>pre:
        print("Yes")
    else:
        print("No")
    pre=now


### FIXED CODE ###

N,K=map(int,input().split())
a=list(map(int,input().split()))
for i in range(K,N,1):
    if a[i]>a[i-K]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

#D
n = int(input())
#約数の数を求める＞＞倍数であり、n以下であるものの総和を求める
# >>
#等差数列の和(初項a:公差d:n番目の項まで)
def Sun_of_Arithmetic_sequence(a, d, n):
    return (2 * a + (n - 1) * d) * n // 2
    
ans = 0
for i in range(1, n + 1):
    #iの倍数の数を求める
    m = n // i
    #初項i:公差i:m項までの等比数列の和
    ans += Sun_of_Arithmetic_sequence(i, i, m)
print(ans)

### FIXED CODE ###

#D
n = int(input())
#約数の数を求める＞＞倍数であり、n以下であるものの総和を求める

ans = 0
for i in range(1, n + 1):
    #iの倍数の数を求める
    m = n // i
    #初項i:公差i:m項までの等比数列の和
    ans += m * (2 * i + i * (m - 1)) *0.5
print(int(ans))
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int,input().split()))
    Q = int(input())
    B = [list(map(int,input().split())) for _ in range(Q)]
    dict = {}

    for i in range(1,10**5+1):
    #for i in range(1,6):
        dict[i] = 0

    for i in range(N):
        dict[A[i]] += 1

    for i in range(Q):
        dict[B[i][1]] += dict[B[i][0]]
        dict[B[i][0]] = 0
        #print(dict)
        sum = 0
        for i in range(1,10**5+1):
        #for i in range(1,6):
            sum += dict[i]*i
        print(sum)

main()


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int,input().split()))
    Q = int(input())
    B = [list(map(int,input().split())) for _ in range(Q)]
    dict = {}

    for i in range(1,10**5+1):
    #for i in range(1,6):
        dict[i] = 0

    for i in range(N):
        dict[A[i]] += 1

    sum = 0
    for i in range(1,10**5+1):
        #for i in range(1,6):
        if dict[i] != 0:
            sum += dict[i]*i

    for i in range(Q):
        sum = sum +(dict[B[i][0]]*B[i][1] - dict[B[i][0]]*B[i][0])

        dict[B[i][1]] += dict[B[i][0]]
        dict[B[i][0]] = 0
        #print(dict)
        print(sum)

main()
### BUGGY CODE ###

N, u, v = map(int, input().split())
points = [list(map(int, input().split())) for i in range(N - 1)]
tree = [[] for i in range(N + 1)]
for a, b in points:
	tree[a].append(b)
	tree[b].append(a)

def bfs(node):
	sta = [node]
	dis = [-1] * (N + 1)
	dis[node] = 0
	while sta:
		no = sta.pop(0)
		tempD = dis[no] + 1
		for tempN in tree[no]:
			if dis[tempN] < 0:
				dis[tempN] = tempD
				sta.append(tempN)
	else:
		return dis

disU = bfs(u)
disV = bfs(v)
ans = 0

for u_, v_ in zip(disU[1:], disV[1:]):
	if u_ < v_:
			ans = max(ans, v_)
else:
	print(ans - 1)

### FIXED CODE ###

N, u, v = map(int, input().split())
tree = [[] for i in range(N + 1)]
for _ in range(N - 1):
	a, b = map(int, input().split())
	tree[a].append(b)
	tree[b].append(a)

def dfs(node):
	sta = [node]
	dis = [-1] * (N + 1)
	dis[node] = 0
	while sta:
		no = sta.pop()
		tempD = dis[no] + 1
		for tempN in tree[no]:
			if dis[tempN] < 0:
				dis[tempN] = tempD
				sta.append(tempN)
	else:
		return dis

disU = dfs(u)
disV = dfs(v)
ans = 0

for u_, v_ in zip(disU[1:], disV[1:]):
	if u_ < v_:
			ans = max(ans, v_)
else:
	print(ans - 1)
### 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 ###

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

while y != 0:
	x,y =y,x%y
x = (c*d)//x

count1 = b - (b//c + b//d -b//x)
count2 = (a - 1) - ((a-1)//c + (a-1)//d -(a-1)//x) 
print(count1 - count2)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc129/tasks/abc129_d
from copy import deepcopy
def main():
    h, w = map(int, input().split())

    matrix = []
    matrix.append([0] * (w + 1))
    for _ in range(h):
        row = [1 if x == '.' else 0 for x in input()]
        row = [0] + row
        matrix.append(row)
    matrix.append([0] * (w + 1))

    left = deepcopy(matrix) # 左から右
    right = deepcopy(matrix) # 右から左
    up = deepcopy(matrix) # 上から下
    down = deepcopy(matrix) # 下から上

    for i in range(1, h + 1):
        for j in range(1, w + 1):
            if left[i][j]:
                left[i][j] += left[i][j - 1]
    for i in range(1, h + 1):
        for j in range(1, w + 1)[::-1]:
            if right[i][j - 1]:
                right[i][j - 1] += right[i][j]
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            if up[i][j]:
                up[i][j] += up[i - 1][j]
    for i in range(1, h + 1)[::-1]:
        for j in range(1, w + 1):
            if down[i - 1][j]:
                down[i - 1][j] += down[i][j]

    ans = 1
    for i in range(h + 1):
        for j in range(w + 1):
            t = left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3
            ans = max(ans, t)
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

# https://atcoder.jp/contests/abc129/tasks/abc129_d
from copy import deepcopy
def main():
    h, w = map(int, input().split())
    matrix = []
    for _ in range(h):
        row = list(input())
        matrix.append(row)

    left = [[0] * w for _ in range(h)] # 左から右
    right = [[0] * w for _ in range(h)] # 右から左
    up = [[0] * w for _ in range(h)] # 上から下
    down = [[0] * w for _ in range(h)] # 下から上

    for i in range(h):
        c = 0
        for j in range(w):
            if matrix[i][j] == '.':
                c += 1
            else:
                c = 0
            left[i][j] = c
    for i in range(h):
        c = 0
        for j in range(w)[::-1]:
            if matrix[i][j] == '.':
                c += 1
            else:
                c = 0
            right[i][j] = c
    for j in range(w):
        c = 0
        for i in range(h):
            if matrix[i][j] == '.':
                c += 1
            else:
                c = 0
            up[i][j] = c
    for j in range(w):
        c = 0
        for i in range(h)[::-1]:
            if matrix[i][j] == '.':
                c += 1
            else:
                c = 0
            down[i][j] = c
    ans = 1
    for i in range(h):
        for j in range(w):
            t = left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3
            ans = max(ans, t)
    print(ans)

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

S = str(input())
N = len(S)


ans = 0
amari = [0] * 2019
follow = 0

for i in range(N):
  Amari_ = (int(S[N-i-1]) * pow(10, i) + follow) % 2019
  amari[Amari_] += 1
  follow = Amari_
  
ans = sum(list( i * (i-1)//2 for i in amari ))
ans += amari[0]

print(ans)

### FIXED CODE ###

S = str(input())
N = len(S)

ans = 0
amari = [0] * 2019
amari[0] = 1
follow = 0
POW = 1

for i in reversed(S):
  follow += int(i) * POW
  follow %= 2019
  amari[follow] += 1
  POW *= 10
  POW %= 2019
  
print(sum( i * (i-1) // 2 for i in amari ))
### BUGGY CODE ###

import sys
n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
dp = [1]*2 + [0 for _ in range(n-1)]
mod = 1000000007
  
for i in range(n-1):
  if i+1 in a:
    dp[i+1] = 0
  dp[i+2] = dp[i]+dp[i+1]
  
  if dp[i+2] >= mod:
    dp[i+2] -= mod

print(dp[-1]%mod)  


### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
hole = [0]*(n+1)
for i in range(m):
  hole[int(input())] = 1

dp = [0]*(n+1)
dp[0] = 1
MOD = 10**9+7
   
for i in range(1,n+1):
  if hole[i]==1:
    dp[i] = 0
  else:
    dp[i] = dp[i-1]+dp[i-2]
    dp[i] %= MOD

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

import itertools

n = int(input())

s = input()

numlist = []

for v in itertools.combinations(range(n), 3):
    numlist.append(s[v[0]] + s[v[1]] + s[v[2]])

numlist = set(numlist)
ans = len(numlist)

print(ans)

### FIXED CODE ###

 
n = int(input())
s = input()
ans = 0
 
pin = [str(i).zfill(3) for i in range(1000)]
 
for i in pin:
    idx = -1
    for j in i:
        idx = s.find(j,idx+1)
        if idx < 0:
            break
    else:
        ans += 1
 
print(ans)