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

import sys

sys.setrecursionlimit(1000000)


def dfs(g: {}, v: int, path_list: [], added: {}):
    path_list.append(v)
    for next_v in g[v]:
        # # next_v が探索済だったらスルー
        if next_v in path_list:
            continue
        # 距離３なら追加可能か確認して次へ
        if len(path_list) == 3:
            if path_list[0] not in g[next_v]:
                dic_a = added.setdefault(path_list[0], set())
                dic_a.add(next_v)
                dic_b = added.setdefault(next_v, set())
                dic_b.add(path_list[0])
        # 距離1なら複製して次へ
        elif len(path_list) == 1:
            copied = [v]
            dfs(g, next_v, copied, added)
        # 距離2なら複製して次へ
        elif len(path_list) == 2:
            copied = path_list.copy()
            dfs(g, next_v, copied, added)


def main():
    n, m = map(int, input().split())

    g = {}
    for i in range(m):
        a, b = map(int, input().split())
        dic_a = g.setdefault(a-1, set())
        dic_a.add(b-1)
        dic_b = g.setdefault(b-1, set())
        dic_b.add(a-1)
    count = 0
    while True:
        added = {}
        for i in range(n):
            dfs(g, i, [], added)
        added_cnt = 0
        for _set in added.values():
            added_cnt += len(_set)
        if added_cnt == 0:
            break
        count += added_cnt
        for k, v in added.items():
            dic_a = g.setdefault(k, set())
            for v_item in v:
                dic_a.add(v_item)
    print(int(count/2))



main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(100000000)


def dfs(g: {}, v: int, seen: [], current_color: int):
    seen[v] = current_color
    for next_v in g[v]:
        # next_v が探索済だったらスルー
        if seen[next_v] != -1:
            if current_color == seen[next_v]:
                return False
            continue
        seen[next_v] = 1-current_color
        # 再帰的に探索
        if not dfs(g, next_v, seen, 1 - current_color):
            return False
    return True


def main():
    n, m = map(int, input().split())

    g = {}
    for i in range(m):
        a, b = map(int, input().split())
        dic_a = g.setdefault(a-1, [])
        dic_a.append(b-1)
        dic_b = g.setdefault(b-1, [])
        dic_b.append(a-1)
    # -1:not clear, 0:white, 1:black
    seen = [-1] * n

    is_bipartite = True
    for i in range(n):
        if seen[i] != -1:
            continue
        if not dfs(g, 0, seen, 0):
            is_bipartite = False
            break

    if is_bipartite:
        white = len([x for x in seen if x == 0])
        black = n - white

        print(black*white - m)
    else:
        print(int((n-1)*n / 2) - m)

main()
### BUGGY CODE ###

N = int(input())
each_edge = [set() for i in range(N)]
ans = []
kouho = set([i+1 for i in range(N)])
for i in range(N-1):
    a, b = map(int, input().split())
    if not each_edge[a-1] and not each_edge[b-1]:
        tmp = 1
    else:
        aset = each_edge[a-1]
        bset = each_edge[b-1]
        tmp = sorted(list(kouho.difference(aset | bset)))[0]
    each_edge[a-1].add(tmp)
    each_edge[b-1].add(tmp)
    ans.append(tmp)
K = -1
for i in each_edge:
    K = max(K, len(i))
print(K)
for line in ans:
    print(line)


### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline


def main():
    N = int(input().strip())
    edges = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().strip().split())
        edges[a-1].append([b-1, i])
        edges[b-1].append([a-1, i])
    color = [-1 for i in range(N-1)]
    trgt = deque([[0, -1], ])
    while len(trgt) > 0:
        now, parent_color = trgt.pop()
        cand_color = 0
        for node, edge_num in edges[now]:
            if color[edge_num] == -1:
                cand_color += 1
                if cand_color == parent_color:
                    cand_color += 1
                color[edge_num] = cand_color
                trgt.append([node, cand_color])
    print(max(color))
    print("\n".join(map(str, color)))


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

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

c.sort()

ans = 10**9
for i in range(n-k+1):
    ans = min(ans,max(c[i:k+i])-min(c[i:k+i]))

print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
c = [int(input()) for _ in range(n)]
c.sort()
ans = []
for i in range(n-k+1):
    ans.append(c[i+k-1]-c[i])
print(min(ans))
### BUGGY CODE ###

from collections import Counter

N = int(input())
S = input()

counter = Counter(S)

cnt = 0
for i in range(N):
    for j in range(i+1, N):
        k = j + j - i
        if 0 <= k < N:
            if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
                cnt += 1

print(counter["R"]*counter["G"]*counter["B"] - cnt)

### FIXED CODE ###

N = int(input())
S = input()

r = S.count("R")
g = S.count("G")
b = S.count("B")

cnt = 0
for i in range(N):
    for j in range(i+1, N):
        k = j + j - i
        if 0 <= k < N:
            if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
                cnt += 1

print(r*g*b - cnt)
### BUGGY CODE ###

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

s=1
for i in ls:
    s*=i

if s>10**18:
    print(-1)
else:
    print(s)

### FIXED CODE ###

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

s=1
over=False

if 0 in ls:
    s=0
else:
    for i in ls:
        s*=i
        if s>10**18:
            over=True
            break


if over:
    print(-1)
else:
    print(s)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
ga, sa, ba = map(int, input().split())
gb, sb, bb = map(int, input().split())
A = [10**18] * 3
B = [10**18] * 3
dg = abs(ga - gb)
ds = abs(sa - sb)
db = abs(ba - bb)
if ga < gb:
    A[0] = ga
elif ga > gb:
    B[0] = gb
if sa < sb:
    A[1] = sa
elif sa > sb:
    B[1] = sb
if ba < bb:
    A[2] = ba
elif ba > bb:
    B[2] = bb
m = -1
for i in range(N+1):
    if A[0] * i > N:
        break
    for j in range(N+1):
        if A[0] * i + A[1] * j > N:
            break
        k = (N - A[0] * i - A[1] * j) // A[2]
        m = max(m, dg * i + ds * j + db * k)
N += m
m = -1
for i in range(N+1):
    if B[0] * i > N:
        break
    for j in range(N+1):
        if B[0] * i + B[1] * j > N:
            break
        k = (N - B[0] * i - B[1] * j) // B[2]
        m = max(m, dg * i + ds * j + db * k)
N += m
print(N)



### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
ga, sa, ba = map(int, input().split())
gb, sb, bb = map(int, input().split())
INF = 10**18
A = [INF] * 3
B = [INF] * 3
values = [abs(ga - gb), abs(sa - sb), abs(ba - bb)]
if ga < gb:
    A[0] = ga
elif ga > gb:
    B[0] = gb
if sa < sb:
    A[1] = sa
elif sa > sb:
    B[1] = sb
if ba < bb:
    A[2] = ba
elif ba > bb:
    B[2] = bb

def calc(X):
    dp = [0] * (N+1)
    dp[0] = 0
    for x, v in zip(X, values):
        for i in range(N+1-x):
            dp[i+x] = max(dp[i+x], dp[i] + v)
    return dp[-1]

N += calc(A)
N += calc(B)
print(N)
### BUGGY CODE ###

S = input()
S = S[::-1]
mod = 10 ** 9 + 7

dp = [[0 for _ in range(13)] for _ in range(len(S) + 1)]
dp[0][0] = 1
for i, S_i in enumerate(S):
    rem13 = (10 ** i) % 13
    for j in range(13):
        if S_i == '?':
            for k in range(10):
                dp[i + 1][j] = (dp[i + 1][j] + dp[i][(j - rem13 * k) % 13]) % mod
        else:
            dp[i + 1][j] = (dp[i + 1][j] + dp[i][(j - rem13 * int(S_i)) % 13]) % mod

print(dp[-1][5])


### FIXED CODE ###

S = input()
S = S[::-1]
mod = 10 ** 9 + 7

dp = [[0 for _ in range(13)] for _ in range(len(S) + 1)]
dp[0][0] = 1
rem13 = 1
for i in range(len(S)):
    rem13 = (10 ** (i % 6)) % 13
    for j in range(13):
        if S[i] == '?':
            for k in range(10):
                dp[i + 1][j] += dp[i][(j - rem13 * k) % 13]
        else:
            dp[i + 1][j] += dp[i][(j - rem13 * int(S[i])) % 13]
    for j in range(13):
        dp[i+1][j] %= mod

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

import sys
sys.setrecursionlimit(10**6)

N = int(input())
A = [int(a) for a in input().split()]

dp = [["0"]*N for _ in range(N)]
        
def f(i, j):
    if i > j or i < 0 or i >= N or j < 0 or j >= N:
        return 0
    
    if i == j:
        dp[i][j] = A[i]
        return A[i]
        
    if dp[i][j] != "0":
        return dp[i][j]
    
    dp[i][j] = max(A[i]-f(i+1, j), A[j]-f(i, j-1))
    return dp[i][j]

ans = f(0, N-1)
print(ans)

### FIXED CODE ###

N = int(input())
A = [int(a) for a in input().split()]

dp = [[0]*N for _ in range(N)]
        
for k in range(N):
    for i in range(N-k):
        if k == 0:
            dp[i][i] = A[i]
            continue
    
        dp[i][i+k] = max(A[i]-dp[i+1][i+k], A[i+k]-dp[i][i+k-1])

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

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

white = []
black = []

length = sum([a.count(".") for a in A])
cnt = 0

for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            black.append([i,j])
        else:
            white.append([i,j])

while (length > 0):
    gray = []
       
    for l in black:
        if l[1] != 0:
            c1 = [l[0],l[1]-1]
            if A[c1[0]][c1[1]] == "." and c1 not in gray:
                gray.append(c1)
        if l[1] != W-1:
            c2 = [l[0],l[1]+1]
            if  A[c2[0]][c2[1]] == "." and c2 not in gray:
                gray.append(c2)
        if l[0] != 0:
            c3 = [l[0]-1,l[1]]
            if  A[c3[0]][c3[1]] == "." and c3 not in gray:
                gray.append(c3)
        if l[0] != H-1:
            c4 = [l[0]+1,l[1]]
            if  A[c4[0]][c4[1]] == "." and c4 not in gray:
                gray.append(c4)
    
    black = []
    for l in gray:
        black.append(l)
        white.remove(l)
        A[l[0]][l[1]] = "#"
        
    cnt += 1
    length = len(white)
    
print(cnt)

### FIXED CODE ###

H,W = list(map(int,input().split()))
A = [list(str(input())) for i in range(H)]
 
black = []
 
cnt = 0
 
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            black.append([i,j])
 
length = len(black)
            
while (length < H*W):
    gray = []
    for l in black:
        if l[1] != 0:
            c1 = (l[0],l[1]-1)
            if A[c1[0]][c1[1]] == ".":
                gray.append(c1)
                A[c1[0]][c1[1]] = "#"
        if l[1] != W-1:
            c2 = (l[0],l[1]+1)
            if  A[c2[0]][c2[1]] == ".":
                gray.append(c2)
                A[c2[0]][c2[1]] = "#"
        if l[0] != 0:
            c3 = (l[0]-1,l[1])
            if  A[c3[0]][c3[1]] == ".":
                gray.append(c3)
                A[c3[0]][c3[1]] = "#"
        if l[0] != H-1:
            c4 = (l[0]+1,l[1])
            if  A[c4[0]][c4[1]] == ".":
                gray.append(c4)
                A[c4[0]][c4[1]] = "#"
    
    gray = list(set(gray))
    black = [l for l in gray]
    
    cnt += 1
    length += len(black)
    
print(cnt)
### BUGGY CODE ###

N, *d = map(int, open(0).read().split())
for i in range(N):
    temp=d[i]
    d[i]=0
    print(max(d))
    d[i]=temp

### FIXED CODE ###

N, *d = map(int, open(0).read().split())
m=d.index(max(d))
c=[max(d)] *N
d[m]=0
y=max(d)
c[m]=y
for i in range(len(c)):
    print(c[i])
### BUGGY CODE ###

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

INF = 10 ** 18
DP = [INF] * n
DP[0] = 0

for i in range(n):
    for j in range(1, k+1):
        if i + j >= n:
            break
        DP[i+j] = min(DP[i+j], DP[i] + abs(H[i+j] - H[i]))

print(DP[n-1])

### FIXED CODE ###

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

INF = 10 ** 18
DP = [INF] * n
DP[0] = 0

for i in range(n):
    for j in range(1, k+1):
        if i + j >= n:
            break
        DP[i+j] = min(DP[i+j], DP[i] + abs(H[i+j] - H[i]))

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

n=int(input())
a=list(map(int,input().split()))
f=0
s=0
mx=max(a)

stk=[]
ed=[0,0]
for i in a:
  if i in stk:
    stk.remove(i)
    ed.append(i)
  else:
    stk.append(i)
ans=sorted(ed,reverse=True)
print(ans[0]*ans[1])


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
ans=0
b=-1
for i in a:
  if i==b:
    if ans!=0:
      ans*=i
      break
    else:
      ans=i
      b=-1
      continue
  b=i
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
l =[]
for i in range(n):
    l.append(str(a.index(i+1)+1))
print(" ".join(l))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
l =[0]*n
for i,t in enumerate(a):
    l[t-1] = str(i+1)
print(" ".join(l))
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
cost=[float('inf') for i in range(n)]
cost[0]=0
for i in range(n):
  for j in range(1,k+1):
    if i+j==n:
      break
    a=cost[i]+abs(h[i]-h[i+j])
    if cost[i+j]>a:
      cost[i+j]=a
print(cost[-1])

### FIXED CODE ###

import numpy as np
n,k=map(int,input().split())
h=np.array(list(map(int,input().split())),dtype=np.int64)
dp=np.full(n,10**10,dtype=np.int64)
dp[0]=0
for i in range(n-1):
  cost=np.abs(h[i]-h[i+1:i+k+1])
  np.minimum(dp[i+1:i+k+1],dp[i]+cost,out=dp[i+1:i+k+1])
print(dp[-1])
### BUGGY CODE ###

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

dic = {}
for i in range(n):
    dic[p[i]] = i+1
    
ans = 0
big = {0,n+1}
big.add(dic[n])
for i in range(n-1,0,-1):
    i_no = dic[i]
    bigger = big & set(range(i_no+1,n+2,1))
    smaller = big & set(range(i_no-1,-1,-1))

    if len(bigger)==1:
        r1 = n+1
        r2 = n+1
    else:
        r1 = min(bigger)
        bigger.discard(r1)
        r2 = min(bigger)

    if len(smaller)==1:
        l1 = 0
        l2 = 0
    else:
        l1 = max(smaller)
        smaller.discard(l1)
        l2 = max(smaller)

    ans += i*((r2-r1)*(i_no-l1)+(r1-i_no)*(l1-l2))
    
    big.add(dic[i])
    
print(ans)


### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
p_ind = [ (p[i], i+1) for i in range(n) ]
p_ind.sort(reverse=True)

# 平方分割します。
max_n = 10**5
div_n = int(max_n**(1/2))+1
a = [[] for _ in range(div_n)]
a[0] = [0,0]
a[(n+1)//div_n].append(n+1)
a[(n+1)//div_n].append(n+1)
a_count = [0] * (div_n)
a_count[0] += 2
a_count[(n+1)//div_n] += 2

import bisect
ans = 0
for tmp in p_ind:
    val, i = tmp
    group = i//div_n
    j = bisect.bisect(a[group],i)
    #left
    if(j>1):
        left1 = a[group][j-1]
        left2 = a[group][j-2]
    elif(j==1):
        left1 = a[group][j-1]
        lg = group-1
        while(True):
            if(a_count[lg]>0):
                break
            lg -=1
        left2 = a[lg][-1]
    else:
        lg = group-1
        while(True):
            if(a_count[lg]>0):
                break
            lg -=1
        if(a_count[lg]>=2):
            left1 = a[lg][-1]
            left2 = a[lg][-2]
        else:
            left1 = a[lg][-1]
            while(True):
                lg -=1
                if(a_count[lg]>0):
                    break
            left2 = a[lg][-1]
    #right
    if(a_count[group]>=j+2):
        right1 = a[group][j]
        right2 = a[group][j+1]
    elif(a_count[group]>=j+1):
        right1 = a[group][j]
        rg = group
        while(True):
            rg += 1
            if(a_count[rg]>0):
                break
        right2 = a[rg][0]
    else:
        rg = group
        while(True):
            rg += 1
            if(a_count[rg]>0):
                break
        if(a_count[rg]>=2):
            right1 = a[rg][0]
            right2 = a[rg][1]
        else:
            right1 = a[rg][0]
            while(True):
                rg += 1
                if(a_count[rg]>0):
                    break
            right2 = a[rg][0]

    ans += ((right2 - right1)* (i - left1) + (right1 - i)* (left1 - left2)) * val
    a[group].insert(j,i)
    a_count[group] += 1

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

from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    S = input()
    cnt = 0
    start = 0
    while start+4 < len(S):
        for i in range(start+4,len(S)+1):
            if S[i-1] == 0:
                break
            if int(S[start:i]) % 2019 == 0:
                cnt += 1
                break
        start += 2
    print(cnt)
if __name__ == '__main__':
  main()


### FIXED CODE ###

S = input()
lenS = len(S)
count = [0] * 2019
count[0] = 1
num = 0
d = 1
for i in range(lenS):
    num += int(S[lenS - i - 1]) * d
    count[num%2019] += 1
    d *= 10
    d %= 2019
ans = 0
for i in count:
    ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())))
Q = int(input())
ans = []
for q in range(Q):
    b, c = map(int, input().split())
    a = np.where(a==b, c, a)
    ans.append(sum(a))
for q in range(Q):
    print(ans[q])


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
MX = 100005
cnt = [0]*MX
for i in a:
    cnt[i] += 1
tot = 0
for i in range(1, MX):
    tot += cnt[i] * i
q = int(input())
for i in range(q):
    b, c = map(int, input().split())
    tot += (c - b) * cnt[b]
    cnt[c] += cnt[b]
    cnt[b] = 0
    print(tot)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
    n, m = map(int, input().split())
    data = [list(map(int, input().split())) for _ in range(m)]
    rule = [[] for _ in range(n)]
    for i in range(m):
        rule[data[i][0] - 1].append(data[i][1])
        rule[data[i][1] - 1].append(data[i][0])
    res = rule[0][:]
    ans = 0
    for j in range(n - 1):
        if j + 2 not in res:
            res.extend(rule[j + 1])
        else:
            ans += 1
            res = []
            res.extend(rule[j + 1])
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    n, m = map(int, input().split())
    data = [list(map(int, input().split())) for _ in range(m)]
    rule = [[] for _ in range(n)]
    for i in range(m):
        rule[data[i][0] - 1].append(data[i][1])
        rule[data[i][1] - 1].append(data[i][0])
    res = rule[0][:]
    ans = 0
    for j in range(n - 1):
        if j + 2 not in res:
            res.extend(rule[j + 1])
        else:
            ans += 1
            res = rule[j + 1][:]
    print(ans)


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

n = int(input())
l = list(map(int, input().split()))
d = {}
s_sum = {}
s_ans = {}
s = list(set(l))
m = 0
for i in range(len(s)):
    v = l.count(s[i])
    d[s[i]] = v
    if v > 1:
        a = v * (v-1) // 2
        s_ans[s[i]] = a
        m += a
    else:
        s_ans[s[i]] = 0
for i in range(len(l)):
    if not d[l[i]] > 1:
        print(m)
    elif l[i] in s_sum:
        print(s_sum[l[i]])
    else:
        a = d[l[i]] - 1
        ans = m - s_ans[l[i]]
        if a > 1:
            ans += a * (a-1) // 2
        s_sum[l[i]] = ans
        print(ans)

### FIXED CODE ###

import collections

def count_defaultdict(it):
    counter = collections.defaultdict(int)
    for x in it:
        counter[x] += 1
    return dict(counter)

_ = int(input())
l = list(map(int, input().split()))
all_sum = 0
count = count_defaultdict(l)
for _, v in count.items():
    all_sum += v * (v - 1) // 2
for i in range(len(l)):
    if count[l[i]] > 1:
        v = count[l[i]]
        print(all_sum - v * (v-1) // 2 + (v-1) * (v-2)//2)
    else:
        print(all_sum)
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
A.sort(reverse = True)
ans = 0
while A:
    a = A.pop(-1)
    if not A or a != A[-1]:
        ans += 1
    A = [i for i in A if i%a != 0]
print(ans)


### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
A.sort()
B = [True]*(A[-1]+1)
i = 0
for i in range(N):
  if i < N-1 and A[i] == A[i+1]:
    B[A[i]] = False
  if A[-1] < 2*A[i]:
    continue
  M = A[-1]//A[i]+1
  for j in range(2,M):
    B[j*A[i]] = False

ans = 0
for a in A:
  if B[a]:
    ans += 1
print(ans)
### BUGGY CODE ###

n,q = map(int, input().split())
s = input()
for _ in range(q):
  l,r = map(int, input().split())
  print(s[l-1:r].count('AC'))

### FIXED CODE ###

n,q = map(int, input().split())
s = input()
c = [0]*n
for i in range(1,n):
  c[i] += c[i-1]
  if s[i-1:i+1]=='AC': c[i] += 1

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

# -*- coding: utf-8 -*-
import fractions
import numpy as np
 
mod = 10**9+7
 
n = int(input())
a = list(map(int, input().split()))
 
div = a[0]
for i in a:
    div = div*i//fractions.gcd(div, i)

ans = 0
for i in a:
    ans += div//i

print(ans%mod)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import fractions
 
mod = 10**9+7
 
n = int(input())
a = list(map(int, input().split()))
 
div = a[0]
for i in a[1:]:
    div = div*i//fractions.gcd(div, i)

ans = 0
for i in a:
    ans += div//i

print(ans%mod)
### BUGGY CODE ###

# coding:utf-8

import sys
from collections import deque

INF = float('inf')
MOD = 10 ** 9 + 7
dy, dx = (0, -1, 0, 1), (1, 0, -1, 0)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    h, w = LI()
    B = [list(SI()) for _ in range(h)]

    D = deque()
    for i, row in enumerate(B):
        for j, c in enumerate(row):
            if c == '#':
                D.append((i, j, 0))

    while D:
        y, x, cnt = D.popleft()
        for i in range(4):
            yy = y + dy[i]
            xx = x + dx[i]

            if 0 <= yy < h and 0 <= xx < w:
                if B[yy][xx] == '#':
                    continue
                B[yy][xx] = '#'
                D.append((yy, xx, cnt + 1))

    print(cnt)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# coding:utf-8

import sys
from collections import deque

INF = float('inf')
MOD = 10 ** 9 + 7
dy, dx = (0, -1, 0, 1), (1, 0, -1, 0)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    h, w = LI()
    B = [list(SI()) for _ in range(h)]

    D = deque()
    for i, row in enumerate(B):
        for j, c in enumerate(row):
            if c == '#':
                D.append((i, j, 0))

    while D:
        y, x, cnt = D.popleft()
        for i in range(4):
            yy = y + dy[i]
            xx = x + dx[i]

            if 0 <= yy < h and 0 <= xx < w:
                if B[yy][xx] == '#':
                    continue
                B[yy][xx] = '#'
                D.append((yy, xx, cnt + 1))

    print(cnt)




if __name__ == '__main__':
    main()