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

def main():
    N, M = map(int, input().split())
    connect_list = [0] * N

    max_road_num = 0
    for i in range(M):
        A, B = map(int, input().split())
        A = A - 1
        B = B - 1
        
        A_road_num = connect_list[A]
        B_road_num = connect_list[B]

        if A_road_num == 0 and B_road_num == 0:
            max_road_num = max_road_num + 1
            connect_list[A] = max_road_num
            connect_list[B] = max_road_num
        elif A_road_num != 0 and B_road_num == 0:
            connect_list[B] = connect_list[A]
        elif A_road_num == 0 and B_road_num != 0:
            connect_list[A] = connect_list[B]
        else:
            connect_list = [A_road_num if B_road_num == road_num else road_num for road_num in connect_list]

    answer = 0
    set_connect_list = set(connect_list)
    set_connect_list.discard(0)
    if len(set_connect_list) != 1:
        answer = len(set_connect_list) - 1

    print(answer + connect_list.count(0))

if __name__ == "__main__":
    main()

### FIXED CODE ###

def root(list_parent, x):
    if(list_parent[x] == x):
        return x
    else:
        list_parent[x] = root(list_parent, list_parent[x])
        return list_parent[x]

def unite(list_parent, x, y):
    x = root(list_parent, x)
    y = root(list_parent, y)

    if(x == y):
        return list_parent

    if x > y:
        list_parent[y] = x
    else:
        list_parent[x] = y

    return list_parent

def main():
    N, M = map(int, input().split())

    list_parent = []
    for i in range(N):
        list_parent.append(i)

    for i in range(M):
        A, B = map(int, input().split())
        list_parent = unite(list_parent, A-1, B-1)

    set_root = set()
    for i in list_parent:
        root_i = root(list_parent, i)
        if root_i not in set_root:
            set_root.add(root_i)

    print(len(set_root) - 1)

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

n,k=map(int,input().split())
A=list(map(int,input().split()))
A=[0]+A
B=[]
C=[0]+[-1]*n
now_city=1
seen=set()

#【ループ回数】200000
for i in range(1,len(A)):
    now_city=A[now_city]
    #【ループ回数】B 内で now_city があるかを探索
    if now_city in B:
        route=B[C[now_city]-1:i-1]
        break
    B.append(now_city)
    C[now_city]=i
if k <= len(B):
    print(B[k-1])
else:
    k = k- len(B)
    x = k % len(route)
    if x ==0:
        print(route[-1])
    else:
        print(route[x-1])

### FIXED CODE ###

n,k = map(int,input().split())
s = list(map(int,input().split()))
# print(s)
now_city = 1
s_l_city = 1
t = [0] #何回そこを通ったか
f = [0] #何回目にそこを通ったか
a=0
b = 0#サイクルありなし
f_l=0#ループの最初

#【ループ回数】200000
for i in range(n):
    t.append(0)
    f.append(-1)
# print(s)
sycle = 0
#【ループ回数】200000
for i in range(1,n+10):
    now_city = s[now_city-1]

    if t[now_city-1]==1:
        #  print(i,f[j])
         sycle=i-f[now_city-1]
         f_l=f[now_city-1]
        #  f_l=i
        #  a = 1
         b = i
        #  s_l_city=now_city
        #  print("ループの最初の数字",now_city,"最初は"+str(f_l)+"回目","周期は",sycle)
         break
    t[now_city-1]+=1
    f[now_city-1]=i
# print(t)
# print(f_l)
# print(f_l,sycle,s_l_city)

if k>b:
    # now_city=s_l_city
    for _ in range((k-f_l)%sycle):

        now_city = s[now_city-1]
    # print((k-f_l)%sycle)
    print(now_city)
else:
    # print("ループなし")
    now_city=1
    for _ in range(k):
        now_city=s[now_city-1]
    print(now_city)
### BUGGY CODE ###

from itertools import permutations
N,M,R=map(int, input().split())
G=[[] for _ in range(N)]
r=list(map(int, input().split()))
for i in range(M):
    a,b,c=map(int, input().split())
    G[a-1].append((b-1,c))
    G[b-1].append((a-1,c))

from heapq import heappop, heappush

class Dijkstra:
    """
    shortest_distance(g): startノードからgoalノードまでの最短距離
    """
    def __init__(self, graph, start, goal):
        """
        graph: 隣接リストによるグラフG[from]=(to,距離)
        start: 始点のノード番号
        goal: 終点のノード番号
        """
        self.g = graph
        self.V = len(graph)

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = [float('inf')] * (self.V)
        self.dist[start] = 0

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (0, start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            # goalノードならそこで終了
            if u == goal:
                break
            if dist_u > self.dist[u]:
                continue
            for v, weight in self.g[u]:
                alt = self.dist[u] + weight
                if alt < self.dist[v] :
                    self.dist[v] = alt
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]


#print(G)

ans=float("INf")
for t in permutations(r):
    sub=0
    #print(t)
    for i in range(R):
        if i==0:
            now=t[i]
        d=Dijkstra(G,now-1,t[i]-1)
        sub+=d.shortest_distance(t[i]-1)
        now=t[i]
        #print(now)
    ans=min(ans, sub)
print(ans)

### FIXED CODE ###

import itertools
N,M,R=map(int, input().split())
r=list(map(int, input().split()))
G = [[float("inf")]*N for i in range(N)] 
for i in range(M):
    a,b,c=map(int, input().split())
    G[a-1][b-1]=c
    G[b-1][a-1]=c

def warshall_floyd(G):
    #d[i][j]: iからjへの最短距離
    for k in range(N):
        for i in range(N):
            for j in range(N):
                G[i][j] = min(G[i][j],G[i][k] + G[k][j])
    return G
G=warshall_floyd(G)
ans=10**8
for L in itertools.permutations(r):
    L=list(L)
    sub=0
    for i in range(1,R):
        s=L[i-1]
        t=L[i]
        sub+=G[s-1][t-1]
    ans=min(ans, sub)
print(ans)
### BUGGY CODE ###

s = input()
ans = 0
#sが全部Wか全部Bになるまでループ
while s.count('W')!=0 and s.count('B')!=0:
    #一番右がBならWを置き、sの一番右のWまでWにする
    if s[-1] == 'B':
        W_usiro = s.rfind('W')
        s = s[0:W_usiro+1] + s[W_usiro+1:].replace('B','W') + 'W'
    #一番右がWならBを置き、sの一番右のBまでBにする
    else:
        B_usiro = s.rfind('B')
        s = s[0:B_usiro+1] + s[B_usiro+1:].replace('W','B') + 'B'

    ans += 1

print(ans)

### FIXED CODE ###

s = input()
ans = 0
now = s[0]
for i in range(1,len(s)):
    if now != s[i]:
        ans += 1
        now = s[i]

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

MOD = 998244353

lim = 200000
inv_t = [-1 for i in range(lim+1)]
factrial = [-1 for i in range(lim+1)]
factrial_inv = [-1 for i in range(lim+1)]


def set_inv(max=lim):
    inv_t[0] = 0
    for i in range(1, max):
        inv_t[i] == mod_inv(i)


def mod_inv(x, mod=MOD):
    y, u, v, _x = mod, 1, 0, x
    while y:
        t = _x//y
        _x -= t*y
        _x, y = y, _x
        u -= t*v
        u, v = v, u
    u %= mod
    if u < 0:
        u += mod
    return u


def mod_pow(a, n, mod=MOD):
    res = 1
    while n:
        if n & 1:
            res = res*a % mod
        a = a*a % mod
        n >>= 1
    return res


def set_factrial(max=lim, mod=MOD):
    c = 1
    global factrial
    global factrial_inv
    factrial = [-1 for i in range(lim+1)]
    factrial_inv = [-1 for i in range(lim+1)]

    factrial[0] = factrial_inv[0] = 1
    for i in range(1, max):
        c *= i
        c %= mod
        factrial[i] = c
        factrial_inv[i] = mod_inv(c, mod)


def comb(a, b, mod=MOD):
    if not(factrial[0] in locals()):
        set_factrial()
    return (factrial[a]*factrial_inv[b]*factrial_inv[a-b]) % mod


n, m, k = [int(_) for _ in input().split()]
ans = 0
for i in range(k+1):
    ans += m*comb(n-1, i)*mod_pow(m-1, n-1 - i)
    ans %= MOD
    # print(ans)
print(ans)


### FIXED CODE ###

MOD = 10000000007
lim = 200000
MOD = 998244353

inv_t = [-1 for i in range(lim+1)]
factrial = [-1 for i in range(lim+1)]
factrial_inv = [-1 for i in range(lim+1)]


def set_inv(max=lim):
    inv_t[0] = 0
    for i in range(1, max):
        if inv_t[i] == -1:
            _ = mod_inv(i)
            inv_t[i] = _


def mod_inv(x, mod=MOD):
    y, u, v, _x = mod, 1, 0, x
    while y:
        t = _x//y
        _x -= t*y
        _x, y = y, _x
        u -= t*v
        u, v = v, u
    u %= mod
    if u < 0:
        u += mod
    return u


def mod_pow(a, n, mod=MOD):
    res = 1
    while n:
        if n & 1:
            res = res*a % mod
        a = a*a % mod
        n >>= 1
    return res


def set_factrial(max=lim, mod=MOD):
    c = 1
    factrial[0] = factrial_inv[0] = 1
    for i in range(1, max):
        c *= i
        c %= mod
        factrial[i] = c
        factrial_inv[i] = mod_inv(c, mod)


def comb(a, b, mod=MOD):
    if factrial == -1:
        set_factrial()
    return (factrial[a]*factrial_inv[b]*factrial_inv[a-b]) % MOD


n, m, k = [int(_) for _ in input().split()]
ans = 0
set_inv()
set_factrial()
for i in range(k+1):
    ans += m*comb(n-1, i)*mod_pow(m-1, n-1 - i)
    ans %= MOD
    # print(ans)
print(ans)
### BUGGY CODE ###

s = list(input())
k = int(input())
ansnum = 0
while(ansnum < k):
    #print(s)
    for j in range(k):
        # listj = []
        # for i in range(len(s)-j):
        #     #print(s[i:i+j+1])
        #     listj.append(s[i:i+j+1])
        listj = [s[i:i+j+1] for i in range(len(s)-j)]
        listj.sort()
        #print('listj:',listj)
        # print('j:',j)
        if len(listj) >= 2 and listj[0] == listj[1]:
            # print('choufuku')
            pass
        else:
            # j+1文字で重複なしの場合(j=0,1,2,3,4)
            s = ''.join(s)
            lens = len(s)
            for i in range(len(listj)):
                num = s.index(''.join(listj[i]))
                a = lens - num
                # print('index:',num)
                # print('ansnum:',ansnum)
                if a < k - ansnum:
                    ansnum += a
                else:
                    ans = s[num:num + k-ansnum]
                    ansnum = k + 1
                    break
        if ansnum > k:
            break

#print('ans:',ans)
print(ans)

### FIXED CODE ###

s = list(input())
k = int(input())
subs = []
for i in range(min(k,len(s))):
  for j in range(len(s)-i):
    subs.append(''.join(s[j:j+i+1]))
subs = list(set(subs))
subs.sort()
#print(subs)
print(subs[k-1])
### BUGGY CODE ###

N = int(input())
robot_list = []
for i in range(N):
  robot_list.append(list(map(int, input().split())))

def choose_coordinate(now_edge):
  global robot_list
  global res
  next_edge = pow(10, 10)

  for i in range(N):
    robot_right_edge = robot_list[i][0] + robot_list[i][1]
    robot_left_edge = robot_list[i][0] - robot_list[i][1]
    if robot_left_edge >= now_edge and robot_right_edge <= next_edge:
      next_edge = robot_right_edge
    
  if next_edge == pow(10, 10):
    return
  else:
    res += 1
    choose_coordinate(next_edge)

res = 0
choose_coordinate(- pow(10,10))

print(res)

### FIXED CODE ###

N = int(input())
robot_list = []
for i in range(N):
  X, L = map(int, input().split())
  left_edge = X - L
  right_edge = X + L
  robot_list.append([left_edge, right_edge])

robot_list.sort(key=lambda x: x[1])

res = 0
index = - pow(10, 10)
for i in range(N):
  if robot_list[i][0] >= index:
    index = robot_list[i][1]
    res += 1

print(res)
### BUGGY CODE ###

import math
N, K = map(int, input().split())
P = list(map(int, input().split()))

INDEX = -1
MA = 0
for i in range((N - K + 1)//2):
    M = 0
    L = 0
    for j in range(K):
        M += P[i + j]
        L += P[-1-i-j]
    # print(L)
    if M > MA:
        MA = M
        INDEX = i
    if L > MA:
        MA = L
        INDEX = N-K-i

ans = 0
for i in range(K):
    ans += P[i+INDEX] * (P[i+INDEX]+1) / (2*P[i+INDEX])

print("{:.12f}".format(ans))


### FIXED CODE ###

import math
N, K = map(int, input().split())
P = list(map(int, input().split()))

INDEX = 0
total = 0
for i in range(K):
    total += P[i]

tmp = total
for i in range(N - K):
    tmp = tmp - P[i] + P[i + K]
    
    if tmp > total:
        total = tmp
        INDEX = i+1


# MA = 0
# for i in range(N - K + 1):
#     M = 0
#     for j in range(K):
#         M += P[i + j]
    
#     if M > MA:
#         MA = M
#         INDEX = i

ans = 0
for i in range(K):
    ans += P[i+INDEX] * (P[i+INDEX]+1) / (2*P[i+INDEX])

print("{:.12f}".format(ans))
### BUGGY CODE ###

import bisect
n = int(input())
p = list(map(int,input().split()))
l = []
c = 0
for i in p:
  ind = bisect.bisect_left(l,i)
  l.insert(ind, i)
  if ind == 0:
    c += 1
print(c)

### FIXED CODE ###

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

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

ans = 0
for i in range(min(a), max(a) + 1):
    temp = [abs(x - i) for x in a]
    ans = max(ans, temp.count(0) + temp.count(1))

print(ans)


### FIXED CODE ###

from collections import Counter

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

x = []
for i in a:
    x.append(i)
    x.append(i + 1)
    x.append(i - 1)

ans = max(Counter(x).values())
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())

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


for i in range(m):
    a[a.index(max(a))]//=2
print(sum(a))


### FIXED CODE ###

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

a=[-1*i for i in a]
heapq.heapify(a)
for i in range(m):
    ma=heapq.heappop(a)
    ma*=-1
    heapq.heappush(a,-1*(ma//2))
print(sum(a)*-1)
### BUGGY CODE ###

n = int(input())
s = [str(input()) for i in range(n)]
d = {}
for name in s:
    if name in d.keys():
        d[name] = d[name] + 1
    else:
        d.setdefault(name, 1)
max_k_list = [kv[0] for kv in d.items() if kv[1] == max(d.values())]
for i in sorted(max_k_list):
    print(i)

### FIXED CODE ###

n = int(input())
s = [str(input()) for i in range(n)]
sorted_s = sorted(s)
count = 1
max = 1
ans_list = []
prev = sorted_s[0]
for i in sorted_s[1:]:
    if i == prev:
        count += 1
    else:
        if count > max:
            ans_list = [prev]
            max = count
        elif count == max:
            ans_list.append(prev)
        prev = i
        count = 1
if count > max:
    ans_list = [prev]
elif count == max:
    ans_list.append(prev)
for i in ans_list:
    print(i)
### BUGGY CODE ###

n=int(input())
a=[int(i) for i in input().split()]
x=0
y=0
l=float("inf")
for i in range(n-1):
  x+=a[i]
  y=sum(a)-x
  l=min(l,abs(x-y))
print(l)

### FIXED CODE ###

n=int(input())
a=[int(i) for i in input().split()]
x=0
y=sum(a)
l=float("inf")
for i in range(n-1):
  x+=a[i]
  y=y-a[i]
  l=min(l,abs(x-y))
print(l)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
p=int(input())
A=[int(i) for i in input().split()]
mod=p
B=[0]*p
for i in range(p):
  C=[1]*p
  B[0]=(B[0]-A[i])%mod
  for j in range(1,p):
    C[j]=(C[j-1]*i)%mod
    B[j]=(B[j]-A[i]*C[j])%mod
    if j==p-1:
      B[j]=(B[j]+A[i])%mod
B=B[::-1]
print(*B)
    


### FIXED CODE ###

import sys
input = sys.stdin.readline
p=int(input())
A=[int(i) for i in input().split()]
B=[0]*p

P=[[0]*p for _ in range(p)]
for i in range(1,p): 
  for j in range(1,p):
    if j==1:
      P[i][j]=i
    else:
      P[i][j]=(P[i][j-1]*i)%p

for i in range(p):
  a=A[i]
  B[0]-=a
  for j in range(1,p):
    B[j]-=a*P[i][j]
    if j==p-1:
      B[j]+=a
B=B[::-1]
for i in range(p):
  B[i]%=p
print(*B)
### BUGGY CODE ###

n, k, *h = map(int, open(0).read().split())
dp = [float('inf')] * n
dp[0] = 0
for i in range(1, n):
    min_i = max(0, i-k)
    dp[i] = min([dp[j] + abs(h[i] - h[j]) for j in range(min_i, i)])
print(dp[n-1])

### FIXED CODE ###

def main():
    n, k, *h = map(int, open(0).read().split())
    dp = [float('inf')] * n
    dp[0] = 0
    for i in range(1, n):
        min_i = max(0, i-k)
        dp[i] = min([dp[j] + abs(h[i] - h[j]) for j in range(min_i, i)])
    print(dp[n-1])
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import itertools
N,M=list(map(int,input().split()))

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
def factorize_list(n):
    result = []
    for val,perm in factorize(n):
        result+= [val]*perm
    return result

factorized = factorize_list(M)

def mul(args):
    r =1
    for v in args:
        r*= v
    return r


result=1
for i in range(len(factorized)+1):
    for vals in set(itertools.combinations(factorized,i)):
        A= mul(vals)
        B= M//A
        #print(A,B,vals)
        if A>=N:
            result = max(B,result)


print(result)

### FIXED CODE ###

import itertools


def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
def factorize_list(n):
    result = []
    for val,perm in factorize(n):
        result+= [val]*perm
    return result



def mul(args):
    r =1
    for v in args:
        r*= v
    return r

def getcomb(l):
    if len(l)==0:
        return [1]
    result = []
    v,perm = l[0]
    for i in range(perm+1):
        result+= [(v**i)*val for val in getcomb(l[1:])]
    return result


N,M=list(map(int,input().split()))
factorized = factorize(M)
result=1
for i in range(len(factorized)//2+1):
    for vals in getcomb(factorized):
        A= vals
        B= M//A
        #print(A,B,vals)
        if A>=N:
            result = max(B,result)
        if B>=N:
            result = max(A,result)


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

def mpower(a, b, n):
    if b == 0:
        return 1
    if b == 1:
        return a % n
    a1 = a
    k = 1
    while a1 < n and k < b:
        a1 = a1 * a
        k = k + 1

    a1 = a1 % n
    b1 = b // k
    a2 = a
    b2 = b % k
    return (mpower(a1, b1, n)*mpower(a2, b2, n)) % n


def main():
    n = int(input())
    x = input()
    k = int(x, 2)
    p = x.count("1")
    if p > 1:
        kp0 = k % (p - 1)
    kp1 = k % (p + 1)
    f = [0] * (n + 1)
    for i in range(1, n + 1):
        f[i] = f[i % bin(i).count("1")] + 1
    for i in range(n):
        if x[i] == "1":
            pi = p - 1
            if pi == 0:
                print(0)
                continue
            print(f[(kp0 - mpower(2, n - i - 1, pi)) % pi] + 1)
        else:
            pi = p + 1
            print(f[(kp1 + mpower(2, n - i - 1, pi)) % pi] + 1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    x = input()
    k = int(x, 2)
    p = x.count("1")
    if p > 1:
        kp0 = k % (p - 1)
    kp1 = k % (p + 1)
    f = [0] * (n + 1)
    for i in range(1, n + 1):
        f[i] = f[i % bin(i).count("1")] + 1
    for i in range(n):
        if x[i] == "1":
            pi = p - 1
            if pi == 0:
                print(0)
                continue
            print(f[(kp0 - pow(2, n - i - 1, pi)) % pi] + 1)
        else:
            pi = p + 1
            print(f[(kp1 + pow(2, n - i - 1, pi)) % pi] + 1)


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

def main():

    s = input()
    q = int(input())

    query = []
    ctn = 0
    flag = 0
    for _ in range(q):
        temp = input().split()
        if len(temp) == 3 and flag:
            if ctn % 2 == 1:
                query.append(["1"])
            query.append(temp)
            ctn = 0
        elif len(temp) == 3:
            query.append(temp)
        else:
            if flag == 1:
                ctn += 1
            else:
                flag = 1
                ctn += 1
    if flag and ctn % 2 == 1:
        query.append(["1"])

    for q in query:
        if q[0] == "1":
            s = s[::-1]
        else:
            if q[1] == "1":
                s = q[2] + s
            else:
                s = s + q[2]

    print(s)

main()

### FIXED CODE ###

from collections import deque

def main():

    s = deque(input())
    q = int(input())

    flag = 0
    query = []

    for _ in range(q):
        temp = input().split()
        if len(temp) == 1:
            flag += 1
        else:
            query.append(temp + [flag%2])

    for q in query:
        if q[-1] == 0:
            if q[1] == "1":
                s.appendleft(q[2])
            else:
                s.append(q[2])
        else:
            if q[1] == "1":
                s.append(q[2])
            else:
                s.appendleft(q[2])

    if flag % 2 == 1:
        print("".join(list(s)[::-1]))
    else:
        print("".join(s))

main()
### BUGGY CODE ###

n,p=map(int,input().split())
l=[]
x=int(p**(1/n))
for i in range(x+1,0,-1):
  if p%(i**n)==0:
    print(i)
    break

### FIXED CODE ###

n,p=map(int,input().split())
l=[]
if n>41:
  print(1)
else:
  x=int(p**(1/n))
  for i in range(x+1,0,-1):
    if p%(i**n)==0:
      print(i)
      break
### BUGGY CODE ###

import sys

readline = sys.stdin.readline
h, w = map(int, readline().split())
grid = [readline() for _ in range(h)]
light = [[0] * w for _ in range(h)]

# row
for i in range(h):
    start = -1
    for j in range(w):
        if grid[i][j] == '.' and start == -1:
            start = j
        elif grid[i][j] == '#' and start != -1:
            length = j - start
            light[i][start:j] = [length] * length
            start = -1
    if start != -1:
        length = w - start
        light[i][start:w] = [length] * length
# column
for i in range(w):
    start = -1
    for j in range(h):
        if grid[j][i] == '.' and start == -1:
            start = j
        elif grid[j][i] == '#' and start != -1:
            length = j - start
            for k in range(start, j):
                light[k][i] += length
            start = -1
    if start != -1:
        length = h - start
        for k in range(start, h):
            light[k][i] += length
ans = max(max(row) for row in light)
print(ans-1)


### FIXED CODE ###

import sys

readline = sys.stdin.readline
h, w = map(int, readline().split())
grid = [readline() for _ in range(h)]
light = [[0] * w for _ in range(h)]

# row
for i in range(h):
    start = -1
    for j in range(w):
        if grid[i][j] == '.' and start == -1:
            start = j
        elif grid[i][j] == '#' and start != -1:
            length = j - start
            light[i][start:j] = [length] * length
            start = -1
    if start != -1:
        length = w - start
        light[i][start:w] = [length] * length
# column
for i in range(w):
    start = -1
    for j in range(h):
        if grid[j][i] == '.' and start == -1:
            start = j
        elif grid[j][i] == '#' and start != -1:
            length = j - start
            for k in range(start, j):
                light[k][i] += length
            start = -1
    if start != -1:
        length = h - start
        for k in range(start, h):
            light[k][i] += length
ans = max(max(row) for row in light)
print(ans-1)
### BUGGY CODE ###

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

for i in range(k):
    ans=[0]*(n)
    for j in range(n):
        l=max(0,j-a[j])
        r=j+1+a[j]
        ans[l]+=1
        if r<n:
            ans[r]-=1
    for z in range(n-1):
        ans[z+1]+=ans[z]
    a=ans
    if ans[0]==n and ans[n-1]==0:
        print(" ".join(list(map(str,ans))))
        sys.exit()
print(" ".join(list(map(str,ans))))

### FIXED CODE ###

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

for i in range(min(k,500)):
    ans=[0]*(n)
    for j in range(n):
        l=max(0,j-a[j])
        r=j+1+a[j]
        ans[l]+=1
        if r<n:
            ans[r]-=1
    for z in range(n-1):
        ans[z+1]+=ans[z]
    a=ans
print(" ".join(list(map(str,ans))))