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

import heapq
import math


def main():
    h, w = map(int, raw_input().split())
    aa = []
    for _ in xrange(h):
        aa.append(raw_input())
    q = []
    dist = [[float('inf')] * w for _ in xrange(h)]
    for y in xrange(h):
        row = aa[y]
        for x in xrange(w):
            if row[x] == '#':
                dist[y][x] = 0
                q.append([0, x, y])
    heapq.heapify(q)
    while q:
        d, x, y = heapq.heappop(q)
        dd = d + 1
        for dx, dy in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            xx = x + dx
            yy = y + dy
            if 0 <= xx < w and 0 <= yy < h:
                if aa[yy][xx] == '.' and dist[yy][xx] > dd:
                    dist[yy][xx] = dd
                    heapq.heappush(q, [dd, xx, yy])
    m = 0
    for row in dist:
        for v in row:
            if not math.isinf(v) and v > m:
                m = v
    print m


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    h, w = map(int, raw_input().split())
    aa = []
    for _ in xrange(h):
        aa.append(raw_input())
    q = []
    dist = [[False] * w for _ in xrange(h)]
    for y in xrange(h):
        row = aa[y]
        for x in xrange(w):
            if row[x] == '#':
                dist[y][x] = True
                q.append([x, y])
    m = 0
    nexts = []
    while True:
        for x, y in q:
            for dx, dy in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                xx = x + dx
                yy = y + dy
                if 0 <= xx < w and 0 <= yy < h:
                    if aa[yy][xx] == '.' and not dist[yy][xx]:
                        dist[yy][xx] = True
                        nexts.append([xx, yy])
        if nexts:
            m += 1
            q = nexts
            nexts = []
        else:
            break
    print m


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

N, M = map(int, input().split())
ken = [[] for _ in range(N)]
shi = [tuple(map(int, input().split())) for _ in range(M)]
for s1, s2 in shi:
    ken[s1-1].append(s2)
for k in ken:
    k.sort()
for s1, s2 in shi:
    print("{:06}{:06}".format(s1, ken[s1-1].index(s2)+1))

### FIXED CODE ###

from operator import itemgetter
N, M = map(int, input().split())
iPY = [0]*M
res = [0]*M
for i in range(M):
    P, Y = map(int, input().split())
    iPY[i] = (i, P, Y)
iPY.sort(key=itemgetter(2))
iPY.sort(key=itemgetter(1))
j = 1
p = iPY[0][1]
for i, P, Y in iPY:
    if P != p:
        j = 1
        p = P
    res[i] = "{:06}{:06}".format(P, j)
    j += 1
for s in res:
    print(s)
### BUGGY CODE ###

import copy
import numpy as np

N,M = [int(i) for i in input().split(" ")]
ans = np.array([True for _ in range(N)])
ans_ng = ans[::] & False
ans_num = 0

for _ in range(M):
    ans_cp = copy.deepcopy(ans_ng)
    L,R = [int(i) for i in input().split(" ")]
    ans_cp[L-1:R] = True
    ans = ans & ans_cp

for i in ans:
    if i:
        ans_num += 1

print(ans_num)

### FIXED CODE ###

N,M = [int(i) for i in input().split(" ")]
ans_L = 0
ans_R = 1e5+1

for _ in range(M):
    L,R = [int(i) for i in input().split(" ")]
    if ans_L < L:
        ans_L = L
    if ans_R > R:
        ans_R = R

if (ans_R - ans_L) >= 0:
    print(ans_R - ans_L + 1)
else:
    print(0)
### BUGGY CODE ###

mod =1000000007
n = int(input())
a = list(map(int, input().split()))
sumpro = 0

for i in range(n-1):
    for j in range(i+1, n):
            sumpro += a[i]*a[j]
            
print(sumpro%mod)

### FIXED CODE ###

MOD = 10 ** 9 + 7  # MODは変数に入れてしまったほうが打ち間違えなくていいです

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

S = sum(A) % MOD
ans = 0

# A_Nも含まれてしまいますが、そのときはs=0なので問題ありません
for x in A:
    S -= x  # 自分と自分自身を掛けないように、先に引く必要があります
    S %= MOD  # MODはいちいち取っておくといいです
    ans += S * x
    ans %= MOD

ans %= MOD  # この行は完全に不要ですが、最後だけMODを取り忘れてWAになるミスは非常によくあるので、必要以上に取っておくと安心できます
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
l=list(map(int,input().split()))
m=[]
 
for i in range(k,n+1):
  p = l[i-k:i]
  if sum(m) < sum(p):
    m = p
  
print(sum([m[j]*(m[j]+1)/2/m[j] for j in range(k)]))

### FIXED CODE ###

n, k = list(map(int, input().split()))
p = list(map(int, input().split()))
s = sum(p[:k])
m = s

for i in range(n-k):
  s = s-p[i]+p[i+k]
  if m < s:
    m = s
print((m+k)/2)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
opes = [tuple(map(int, input().split())) for _ in range(M)]

D = [C for B, C in opes for _ in range(B)]
D = sorted(D, reverse=True)[:N]

A.sort()
for i, d in enumerate(D):
    if A[i] >= d:
        break
    A[i] = d

print(sum(A))


### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
opes = [tuple(map(int, input().split())) for _ in range(M)]
opes.sort(key=lambda x:-x[1])

D = []
lenD = 0
for B, C in opes:
    D += [C]*B
    lenD += B
    if lenD >= N:
        break

A.sort()
for i, d in enumerate(D[:N]):
    if A[i] >= d:
        break
    A[i] = d

print(sum(A))
### BUGGY CODE ###

n=int(input())
p=list(map(int,input().split()))
c=0
for m in range(n):
  d=0
  for i in range(m):
    if p[m]>p[i]:
      d+=1
  if d==0:
    c+=1
print(c)
  

### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
c=0
d=p[0]
for i in range(n):
  if p[i]<= d:
    d=p[i]
    c+=1
print(c)
### BUGGY CODE ###

n,m=map(int,input().split())
lst=list(list(map(int,input().split())) for i in range(m))
l=sorted(lst,key =lambda x:x[1])
l=sorted(l,key =lambda x:x[0])
i=0
b=lst[0][0]
for e in l:
    if b==e[0]:
        i+=1
    else:
        i=1
    e.append("%06d"%e[0]+"%06d"%i)
    b=e[0]
for a in lst:
    for b in l:
        if a[1]==b[1]:
            print(b[2])
            continue
            continue

### FIXED CODE ###

n,m=map(int,input().split())
l=list(list(map(int,input().split())) for i in range(m))
for i in range(m):
    l[i].append(i)
l.sort(key =lambda x:x[1])
l.sort(key =lambda x:x[0])
i=0
b=l[0][0]
for e in l:
    if b==e[0]:
        i+=1
    else:
        i=1
    e.append("%06d"%e[0]+"%06d"%i)
    b=e[0]
l.sort(key=lambda x:x[2])
for e in l:
    print(e[3])
### BUGGY CODE ###

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

hBom = [0]*H
wBom = [0]*W

# 各行、各列の爆破対象をカウント
for h, w in bom:
    hBom[h-1] += 1
    wBom[w-1] += 1

# 爆破対象の最大数と最大になる行と列の番号を調べる
maxHBom = max(hBom)
maxWBom = max(wBom)
maxHBomIndex = [index for index, h in enumerate(hBom) if h == maxHBom]
maxWBomIndex = [index for index, w in enumerate(wBom) if w == maxWBom]

# 爆破対象が最大になる行と列の組み合わせについて、
# 爆弾を配置する場所が爆破対象であるかないかで場合分け
for h in maxHBomIndex:
    for w in maxWBomIndex:
        if [h+1, w+1] not in bom:
            print(maxHBom + maxWBom)
            exit()
else:
    print(maxHBom + maxWBom - 1)

### FIXED CODE ###

H, W, M = map(int, input().split())
boms = [tuple(map(int, input().split())) for _ in range(M)]
# boms = [list(map(int, input().split())) for _ in range(M)]

hBom = [0]*H
wBom = [0]*W

# 各行、各列の爆破対象をカウント
for h, w in boms:
    hBom[h-1] += 1
    wBom[w-1] += 1

# 爆破対象の最大数と最大になる行と列の番号を調べる
maxHBom = max(hBom)
maxWBom = max(wBom)
maxHBomIndex = [index for index, h in enumerate(hBom) if h == maxHBom]
maxWBomIndex = [index for index, w in enumerate(wBom) if w == maxWBom]

# 爆破対象が最大になる行と列の組み合わせについて、
# 爆弾を配置する場所が爆破対象であるかないかで場合分け
boms = set(boms)
for h in maxHBomIndex:
    for w in maxWBomIndex:
        if (h+1, w+1) not in boms:
            print(maxHBom + maxWBom)
            exit()
else:
    print(maxHBom + maxWBom - 1)
### BUGGY CODE ###

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

# 2文字の連続部分列はN-1個なので、N-1個のBooleanの配列を生成
b = [S[i:i+2]=="AC" for i in range(N-1)]

for _ in range(Q):
    l,r = map(int,input().split())
    # bのl番目からr-1番目までの和を出力
    print(sum(b[l-1:r-1]))

### FIXED CODE ###

import itertools

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

b = [S[i]=='A' and S[i+1]=='C' for i in range(N-1)]
b.insert(0,0)
b = list(itertools.accumulate(b))

for _ in range(Q):
    l,r = map(int,input().split())
    print(b[r-1]-b[l-1])
### BUGGY CODE ###

import random


A, B = [int(str) for str in input().split()]

def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a

def is_prime(q,k=4):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし(但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


if A < B:
    A, B = B, A

div_list = [i for i in make_divisors(B) if A % i == 0]
prime_list = [1] + [i for i in range(1, gcd(A, B) + 1) if is_prime(i)]
print(len([i for i in prime_list if i in div_list]))

### FIXED CODE ###

A, B = [int(str) for str in input().split()]

def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


print(len(set(prime_factorize(gcd(A, B)))) + 1)
### BUGGY CODE ###

N, M=map(int, input().split())
A=list(map(int, input().split()))
s=[0 for _ in range(N+1)]
counts=[0 for _ in range(M)]
for i in range(N):
    s[i+1]=(s[i]+A[i])%M
ans=0
for i in range(N+1):
    ans+=counts[s[i]]
    counts[s[i]]+=1
print(ans)

### FIXED CODE ###

from collections import defaultdict
#from collections import deque

N, K=map(int, input().split())
A=list(map(int, input().split()))
#for i in range(N):
    #A[i]-=1
s=[0 for _ in range(N+1)]
for i in range(N):
    s[i+1]=(s[i]+A[i])%K
d=defaultdict(int)
ans=0
#q=deque()
for j in range(N+1):
    ans+=d[s[j]]
    d[s[j]]+=1
    #q.append(s[j])
    #if len(q)==K:
        #d[q[0]]-=1
        #q.popleft()
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []
    for _ in range(n):
        v, w = LI()
        V.append(v)
        W.append(w)
    
    q = I()
    vl = []
    maxL = 0
    for i in range(q):
        v, l = LI()
        maxL = max(maxL, l)
        vl.append([v,l])
    
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1) for _ in range(m + 1)]
    
    for i in range(1, m+1):
        v, w = V[i-1], W[i-1]
        for j in range(maxL+1):
            if j < w:
                dp[i][j] = dp[i>>1][j]
            else:
                dp[i][j] = max(dp[i>>1][j], dp[i>>1][j - w] + v)
    
    ans = [None]*q
    for i in range(q):
        v, L = vl[i]
        if v <= m:
            ans[i] = dp[v][L]
            continue
        cnt = 0
        tmp = v
        v_ = []
        w_ = []
        while tmp > m:
            v_.append(V[tmp-1])
            w_.append(W[tmp-1])
            tmp >>= 1
            cnt += 1
        ret = dp[tmp][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_tmp[b] = w_tmp[b - lsb] + w_[l-1]
            if w_tmp[b] <= L:
                v_tmp[b] = v_tmp[b - lsb] + v_[l-1]
                ret = max(ret, v_tmp[b] + dp[tmp][L - w_tmp[b]])
        ans[i] = ret
    print('\n'.join(map(str,ans)))
    return

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []

    maxL = 10**5
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1)]
    
    for i in range(n):
        v, w = LI()
        if i <= m:
            d_ = dp[(i+1)>>1][:]
            for j in range(w, maxL+1)[::-1]:
                d_[j] = max(d_[j], d_[j - w] + v)
            dp.append(d_)
        V.append(v)
        W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        v_ = []
        w_ = []
        while v > m:
            v_.append(V[v-1])
            w_.append(W[v-1])
            v >>= 1
            cnt += 1
        ret = dp[v][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_t = w_tmp[b - lsb] + w_[l-1]
            w_tmp[b] = w_t
            if w_t <= L:
                v_t = v_tmp[b - lsb] + v_[l-1]
                v_tmp[b] = v_t
                ret = max(ret, v_t + dp[v][L - w_t])
        print(ret)
    return

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

#n, m, q = map(int, input().split())
#List = list(map(int, input().split()))
#req = [list(map(int, input().split())) for _ in range(q)]
#t = t[:-1]
#print(ans[j], end = "") 改行無しで出力
#[0]*n
n = int(input())
a = list(map(int, input().split()))
q = int(input())
req = [list(map(int, input().split())) for _ in range(q)]
count = [0]*100000
sum = 0

for i in range(100000):
    count[i] = a.count(i+1)

for j in a:
    sum += j

for k in range(q):
    diff = req[k][1] - req[k][0]
    diff = diff * count[req[k][0] - 1]
    count[req[k][1] - 1] += count[req[k][0] - 1]
    count[req[k][0] - 1] = 0
    sum += diff
    print(sum)


### FIXED CODE ###

#n, m, q = map(int, input().split())
#List = list(map(int, input().split()))
#req = [list(map(int, input().split())) for _ in range(q)]
#t = t[:-1]
#print(ans[j], end = "") 改行無しで出力
#[0]*n
n = int(input())
a = list(map(int, input().split()))
q = int(input())
req = [list(map(int, input().split())) for _ in range(q)]
count = [0]*100001
sum = sum(a)

for i in a:
    count[i] += 1

for k in range(q):
    sum += (req[k][1] - req[k][0]) * count[req[k][0]]
    count[req[k][1]] += count[req[k][0]]
    count[req[k][0]] = 0
    print(sum)
### BUGGY CODE ###

l, r = map(int, input().split())
if l <= 2019 <= r:
    print(0)
    exit()
elif r*(r-1) <= 2019:
    print(l*(l+1))
    exit()

a = 2019
for i in range(l, r):
    for j in range(i+1, r+1):
        a = min(a, i*j%2019)

print(a)


### FIXED CODE ###

l, r = map(int, input().split())
if l <= 2019 <= r:
    print(0)
    exit()
elif r*(r-1) <= 2019:
    print(l*(l+1))
    exit()

a = 2019
for i in range(l, r):
    for j in range(i+1, r+1):
        a = min(a, i*j%2019)
        if a == 0:
            print(0)
            exit()

print(a)
### BUGGY CODE ###

n = int(input())
a = tuple(map(int, input().split(" ")))

sum_num = 0
for a_i in set(a):
	a_count_a_i  = a.count(a_i)
	sum_num += a_count_a_i - a_i if a_i <= a_count_a_i else a_count_a_i
print(sum_num)

### FIXED CODE ###

n = int(input())
a = tuple(map(int, input().split(" ")))

a_count = dict()
for a_i in a:
	if a_i not in a_count:
		a_count[a_i] = 0 
	a_count[a_i] += 1

sum_num = 0
for a_i in a_count:
	a_count_a_i = a_count[a_i]
	sum_num += a_count_a_i - a_i if a_i <= a_count_a_i else a_count_a_i
print(sum_num)
### BUGGY CODE ###

#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
#mod = 10**9 + 7

mod=2019
l,r=MI()
mn=inf
mods=[]

#print(mods)
if l-r>=2018:
    ans=0
else:
    for i in range(l,r+1):
        mods.append(i%mod)
    for i in range(r-l+1):
        for j in range(i+1,r-l+1):
            u=(mods[i])*(mods[j])%mod
            if u<mn:
                mn=u
    ans=mn
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import math

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

l,r=MI()
mod=[]
if r-l>=2019:
    rm=0
    print(rm)
    sys.exit()
else:
    for i in range(l,r+1):
        mod.append(i%2019)
#print(mod)
mn=10**7
for i in range(len(mod)-1):
    for j in range(i+1,len(mod)):
        #print(mod[i],end=" ")
        #print(mod[j])
        ans=(mod[i]*mod[j])%2019
        if ans<mn:
            mn=ans
print(mn)
### BUGGY CODE ###

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

ans = []
for i in range(n-k+1):
    tmp = 1
    for _ in range(k):
        tmp *= a[i]
        i += 1
    ans.append(tmp)

for i in range(len(ans)-1):
    if ans[i] < ans[i+1]:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

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

for i in range(1,n-k+1):
    if a[k+i-1] > a[i-1]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import bisect,collections,copy,itertools,math,string
def I(): return int(input())
def S(): return input()
def LI(): return list(map(int,input().split()))
def LS(): return list(input().split())
##################################################
N = I()
A = LI()
_123 = [0]*N
_123count = [0]*N
for x in A:
    _123[x-1] += 1
_123copy = copy.copy(_123)
_123copy.sort(reverse=True)
for i,x in enumerate(_123copy):
    if x==0:
        break
    if x==1:
        _123count[i] = 0
    else:
        _123count[i] = math.factorial(x)//((math.factorial(x-2))*(math.factorial(2)))
_sum = sum(_123count)
for x in A:
    temp = _123[x-1]-1
    if temp<=0:
        print(_sum)
    elif temp==1:
        print(_sum-1)
    else:
        tempminus = math.factorial(temp+1)//((math.factorial(temp-1))*(math.factorial(2)))
        tempplus = math.factorial(temp)//((math.factorial(temp-2))*(math.factorial(2)))
        print(_sum-tempminus+tempplus)


### FIXED CODE ###

import bisect,collections,copy,itertools,math,string
def I(): return int(input())
def S(): return input()
def LI(): return list(map(int,input().split()))
def LS(): return list(input().split())
##################################################
N = I()
A = LI()
_123 = [0]*N
_123count = [0]*N
for x in A:
    _123[x-1] += 1
_123copy = copy.copy(_123)
_123copy.sort(reverse=True)
_count = {}
for i,x in enumerate(_123copy):
    if x==0:
        break
    if x==1:
        _123count[i] = 0
    elif i!=0 and _123copy[i]==_123copy[i-1]:
        _123count[i] = _123count[i-1]
    else:
        _123count[i] = math.factorial(x)//((math.factorial(x-2))*(math.factorial(2)))
        _count[x] = _123count[i]
_sum = sum(_123count)
for x in A:
    temp = _123[x-1]-1
    if temp<=0:
        print(_sum)
    elif temp==1:
        print(_sum-1)
    else:
        if (temp+1) in _count:
            tempminus = _count[temp+1]
        else:
            tempminus = math.factorial(temp+1)//((math.factorial(temp-1))*(math.factorial(2)))
            _count[temp+1] = tempminus
        if (temp) in _count:
            tempplus = _count[temp]
        else:
            tempplus = math.factorial(temp)//((math.factorial(temp-2))*(math.factorial(2)))
            _count[temp] = tempplus
        print(_sum-tempminus+tempplus)
### BUGGY CODE ###

tamanho=list(map(int,input().rstrip().split()))
conjunto=set()

for i in range(tamanho[1]):
  linha=list(map(int,input().rstrip().split()))
  for j in range(1,linha[0]):
    conjunto.add(j)
  for k in range(linha[1]+1,tamanho[0]+1):
    conjunto.add(k)

print(tamanho[0]-len(conjunto))

### FIXED CODE ###

tamanho=list(map(int,input().rstrip().split()))
intervalo=[1,tamanho[0]]

for i in range(tamanho[1]):
  iterando=list(map(int,input().rstrip().split()))
  intervalo[0]=max(intervalo[0],iterando[0])
  intervalo[1]=min(intervalo[1],iterando[1])

if intervalo[0]>intervalo[1]:
  print(0)
else:
  print(intervalo[1]-intervalo[0]+1)
### BUGGY CODE ###

# C - Bugged
N = int(input())
S = [int(input()) for _ in range(N)]

lst = []
for i in range(2**N):
	ref = 0
	for j in range(N):
		if 1 & (i >> j):
			ref += S[j]
	if ref % 10 == 0:
		ref = 0
	lst.append(ref)

print(max(lst))


### FIXED CODE ###

# C - Bugged
N = int(input())
S = [int(input()) for _ in range(N)]
S = sorted(S)

ans = sum(S)

if ans % 10 != 0:
	pass
else:
	for i in range(N):
		if S[i] % 10 != 0:
			ans = ans - S[i]
			break
	else:
		ans = 0

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

from collections import deque


H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

### FIXED CODE ###

from collections import deque


def solve(H, W, Ch, Cw, Dh, Dw, maze):
    # 後の条件分岐を簡略化するためワープしても迷路外に出ないように壁で囲む
    walled_maze = ['##{}##'.format(row) for row in maze]
    walled_maze.insert(0, '##{}##'.format('#' * W))
    walled_maze.insert(0, '##{}##'.format('#' * W))
    walled_maze.append('##{}##'.format('#' * W))
    walled_maze.append('##{}##'.format('#' * W))

    INF = 10 ** 12
    path = [[INF] * (W + 4) for _ in range(H + 4)]
    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    yet = deque()
    yet.append((Ch + 2, Cw + 2, 0))    # 囲った壁の分だけプラス
    path[Ch + 2][Cw + 2] = 0
    done = deque()

    while yet:
        y, x, s = yet.popleft()
        done.append((y, x, s))
        for dy, dx in walk:
            ny = y + dy
            nx = x + dx
            if walled_maze[ny][nx] == '.' and path[ny][nx] > s:
                path[ny][nx] = s
                yet.append((ny, nx, s))
        if len(yet) == 0:
            while done:
                y, x, s = done.popleft()
                for dy, dx in warp:
                    ny = y + dy
                    nx = x + dx
                    if walled_maze[ny][nx] == '.' and path[ny][nx] > s + 1:
                        path[ny][nx] = s + 1
                        yet.append((ny, nx, s + 1))
    ans = path[Dh + 2][Dw + 2] if path[Dh + 2][Dw + 2] < INF else -1
    print(ans)


if __name__ == '__main__':
    H, W = map(int, input().split())
    Ch, Cw = map(lambda x: int(x) - 1, input().split())
    Dh, Dw = map(lambda x: int(x) - 1, input().split())
    maze = [input() for _ in range(H)]
    solve(H, W, Ch, Cw, Dh, Dw, maze)