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

import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def solve():
    N, K = MI()
    A = LI()
    for i in range(K):
        B = [0] * N
        for idx, a in enumerate(A):
            l = max(0, idx - a)
            r = idx + a + 1
            # print(idx, a, l, r)
            B[l] += 1
            if N > r:
                B[r] -= 1
        # print(B)
        B = list(accumulate(B))
        # print(B)
        if all([j == N for j in B]):
            printlist(B)
            return
        A = B
    printlist(A)

if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def solve():
    N, K = MI()
    A = LI()
    for i in range(K):
        B = [0] * N
        for idx, a in enumerate(A):
            l = max(0, idx - a)
            r = idx + a + 1
            # print(idx, a, l, r)
            B[l] += 1
            if N > r:
                B[r] -= 1
        # print(B)
        B = list(accumulate(B))
        # print(B)
        if all([j == N for j in B]):
            printlist(B)
            return
        A = B
    printlist(A)



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

N=int(input())
A=[]
ans=0
for i in range(N):
    s=input()
    s=sorted(s)
    ans+=A.count(s)
    A.append(s)

print(ans)

### FIXED CODE ###

N=int(input())
P=[]
for i in range(N):
    s=input()
    s=sorted(s)
    P.append(s)

P=sorted(P)
last=P[0]
cnt=0
ans=0
for i in range(1,N):
    if P[i]==last:
        cnt+=1
        ans+=cnt
    else:
        last=P[i]
        cnt=0
print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
cnt = 1

if 2 not in A:
  print(-1)
  exit()

a = A[0]
while a != 2: 
  a = A[a-1]
  cnt += 1
  if a == 1:
    print(-1)
    exit()
print(cnt)


### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
cnt = 0

if 2 not in a:
  print(-1)
  exit()

x = 1
for i in range(n-1):
 
  x = a[x-1]
  cnt += 1

            
  if x == 2:
    print(cnt)
    exit()

print(-1)
### BUGGY CODE ###

n = int(input())
L = sorted(list(map(int,input().split())),reverse= True)
cnt = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        m = n-1
        M = j+1
        while M <= m:
            if L[i] < L[(m+M)//2]+L[j]:
                cnt += (m+M)//2-M+1
                M = (m+M)//2+1
            else:
                m = (m+M)//2-1

print(cnt)




### FIXED CODE ###

import bisect
n = int(input())
L = list(map(int,input().split()))
L.sort()

ans = 0

for i in range(n-1):
    for j in range(i+1,n):
        index = bisect.bisect_left(L,L[i]+L[j])
        ans += index - (j+1)

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

s=input()
count=0
for i in range(len(s)):
    for j in range(i+1,len(s)+1):
        if int(s[i:j])%2019 == 0:
            count+=1

print(count) 

### FIXED CODE ###

s=input()
tmpsum=0
ruiseki=[0]
dic={}
so=2019

for i in range(1,len(s)+1):
    tmpsum+=(int(s[-i])*pow(10,i-1,so)) % so
    tmpsum%=so
    ruiseki.append(tmpsum)

for rui in ruiseki:
    if rui in dic:
        dic[rui]=dic[rui]+1
    else:
        dic[rui]=1


output=0
for val in dic.values():
    output+=val*(val-1)/2

print(int(output))
### BUGGY CODE ###

def gcd(p, q):  # p > qのこと！
    if p % q == 0:
        # print('result: ' + str(q))
        return q
    else:
        return gcd(q, p % q)


K = int(input())

ans = 0

for i in range(1, K+1):
    for j in range(1, K+1):
        gcd_ij = gcd(max(i, j), min(i, j))
        for k in range(1, K+1):
            gcd_ijk = gcd(max(gcd_ij, k), min(gcd_ij, k))
            # print(i, j, k, gcd_ij, gcd_ijk)
            ans += gcd_ijk

print(ans)

# print(max(2, 3))
# print(min(2, 3))
#
# print(gcd(max(2, 3), min(2, 3)))


### FIXED CODE ###


from math import gcd

def gcd2(p, q):  # p > qのこと！
    if p % q == 0:
        # print('result: ' + str(q))
        return q
    else:
        return gcd(q, p % q)


K = int(input())

ans = 0

for i in range(1, K+1):
    for j in range(1, K+1):
        # gcd_ij = gcd2(max(i, j), min(i, j))
        gcd_ij = gcd(i, j)
        for k in range(1, K+1):
            # gcd_ijk = gcd2(max(gcd_ij, k), min(gcd_ij, k))
            gcd_ijk = gcd(gcd_ij, k)
            # print(i, j, k, gcd_ij, gcd_ijk)
            ans += gcd_ijk

print(ans)

# print(max(2, 3))
# print(min(2, 3))
#
# print(gcd(max(2, 3), min(2, 3)))
### BUGGY CODE ###

MOD=10**9+7

N=int(input())
C=list(map(int, input().split()))
C.sort(reverse=True)
out=0
for i in range(N):
  out+=(pow(2, N-1)+pow(2, N-2)*i)*C[i]
  out%=MOD
  
out=out*pow(2, N, MOD)
print(int(out%MOD))

### FIXED CODE ###

MOD=10**9+7

N=int(input())
if N==1:
  C=int(input())
  print(2*C%MOD)
  exit()
C=list(map(int, input().split()))
C.sort(reverse=True)
out=0
tmp1=pow(2, N-1, MOD)
tmp2=pow(2, N-2, MOD)
for i in range(N):
  out+=(tmp1+tmp2*i)*C[i]
  out%=MOD
  
out=out*pow(2, N, MOD)
print(int(out%MOD))
### BUGGY CODE ###

N = int(input())
masu = list(map(int, input().split()))
masu2 = [None] * N
cnt_max = 0
for i in range(N):
    cnt = 0
    for j in range(i, N-1):
        if masu[j] < masu[j+1]:
            break
        cnt += 1
    masu2[i] = cnt
print(max(masu2))

### FIXED CODE ###

N = int(input())
masu = list(map(int, input().split()))
cnt = 0
masu2 = []
for i in range(N-1):
    if masu[i] < masu[i+1]:
        masu2.append(cnt)
        cnt = 0
    else:
      cnt += 1
else:
  masu2.append(cnt)
print(max(masu2))
### BUGGY CODE ###

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

def zenbu(m, B):
    dp = [-10**9]*m
    if dp[m-1] > -10**9:
        return dp[m-1]
    elif m == 1:
        dp[0] = B[0]
        return dp[0]
    elif m == 2:
        dp[1] = max(B[0],B[1])
        return dp[1]
    elif m == 3:
        dp[2] = max(B[0],B[1],B[2])
        return dp[2]
    elif m%2 == 0: #偶数の場合
        temp = 0
        for i in range(m//2-1):
            temp += B[i*2]
        dp[m-1] = max(temp+ max(B[m-2],B[m-1]), zenbu(m-2, B)+ B[m-1])
        return dp[m-1]
    else:#奇数の場合
        temp = 0
        for i in range((m-1)//2):
            temp += B[i*2]
        dp[m-1] = max(temp, zenbu(m-2,B)+ B[m-1], zenbu(m-3,B)+ max(B[m-2],B[m-1]))
        return dp[m-1]

ans = zenbu(n,A)

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
if N%2 == 0:
  dp = [[0]*2 for _ in range(N)] #0index
  dp[0][0] = A[0]
  dp[1][1] = A[1]
  for i in range(2,N):
    dp[i][0] = dp[i-2][0]+A[i]
    if i-3>=0:
      dp[i][1] = max(dp[i-2][1],dp[i-3][0])+A[i]
    else:
      dp[i][1] = max(dp[i-2][1],0)+A[i]
  ans = max(dp[-2][0],dp[-1][1])
  print(ans)
#i個目を使ってj(0-2)回多く飛んでいる。
else: #N%2 == 1:
  dp = [[0]*3 for _ in range(N)] #0index
  dp[0][0] = A[0]
  dp[1][1] = A[1]
  dp[2][2] = A[2]
  dp[2][0] = A[0]+A[2]
  #print(dp)
  for i in range(3,N):
    dp[i][0] = dp[i-2][0]+A[i]
    if i-3 >= 0:
      dp[i][1] = max(dp[i-2][1],dp[i-3][0])+A[i]
    else:
      dp[i][1] = max(dp[i-2][1],0)+A[i]
    if i-4 >= 0:
      dp[i][2] = max(dp[i-2][2],dp[i-3][1],dp[i-4][0])+A[i]
    elif i-3 >= 0:
      dp[i][2] = max(dp[i-2][2],dp[i-3][1],0)+A[i]
  #else:
  #  dp[i][2] = max(dp[i-2][2],0,0)+A[i]
  #print(dp[-1],dp[-2],dp[-3])

  ans = max(dp[-3][0],dp[-2][1],dp[-1][2])
  print(ans)
  exit()
### BUGGY CODE ###

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

b=0

def f(n):
  return n*(1+n)/2/n

for i in range(n-k+1):
  t=sum(s[i:i+k])
  if t>b:
    b=t
print((b+k)/2)






### FIXED CODE ###

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

m=sum(s[0:k])
r=[m,]
b=m

for i in range(n-k):
  b=b-s[i]+s[i+k]
  r.append(b)
r.sort()
print((r[-1]+k)/2)
### BUGGY CODE ###

from sys import stdin

s = stdin.readline().rstrip()
n = int(stdin.readline().rstrip())
li = []

for i in range(1,len(s)+1):
    for j in range(len(s)-i+1):
        li.append(s[j:j+i])
li = list(set(li))
li.sort()
print(li[n-1])

### FIXED CODE ###

from sys import stdin

s = stdin.readline().rstrip()
n = int(stdin.readline().rstrip())
li = []

for i in range(1,6):
    for j in range(len(s)-i+1):
        li.append(s[j:j+i])
li = list(set(li))
li.sort()
print(li[n-1])
### BUGGY CODE ###

class SegTree():
    def __init__(self, initial, operation, identity):
        n = len(initial)
        self.initial = initial
        self.operation = operation
        self.identity = identity
        self.num = 1 << (len(bin(n - 1)) - 2)
        self.tree = [identity] * (2 * self.num - 1)
        for i in range(n):
            self.tree[i + self.num - 1] = self.initial[i]
        for i in reversed(range(self.num - 1)):
            self.tree[i] = min(self.tree[2*i + 1], self.tree[2*i + 2])
    
    def update(self, k, x):
        k += self.num - 1
        self.tree[k] = x
        while k >= 1:
            k = (k - 1) // 2
            self.tree[k] = self.operation(self.tree[2*k + 1], self.tree[2*k + 2])
    
    def query(self, l, r):
        res = self.identity
        l += self.num - 1
        r += self.num - 1
        while l < r:
            if l % 2 == 0:
                res = self.operation(res, self.tree[l])
                l += 1
            if r % 2 == 0:
                res = self.operation(res, self.tree[r - 1])
            l = (l - 1) // 2
            r = (r - 1) // 2
        return res

N, Q = [int(i) for i in input().split()]

H, W = SegTree([N]*N, min, N), SegTree([N]*N, min, N)
revd = 0
for _ in range(Q):
    t, x = [int(i) for i in input().split()]
    if t == 1:
        h = H.query(x, N + 1)
        w = W.query(h, N + 1)
        revd += h - 2
        W.update(h, min(x, w))
    else:
        w = W.query(x, N + 1)
        h = H.query(w, N + 1)
        revd += w - 2
        H.update(w, min(x, h))

ans = (N - 2)*(N - 2) - revd
print(ans)

### FIXED CODE ###

class SegTree():
    def __init__(self, initial, operation, identity):
        n = len(initial)
        self.initial = initial
        self.operation = operation
        self.identity = identity
        self.num = 1 << (len(bin(n - 1)) - 2)
        self.tree = [identity] * (2 * self.num - 1)
        for i in range(n):
            self.tree[i + self.num - 1] = self.initial[i]
        for i in reversed(range(self.num - 1)):
            self.tree[i] = min(self.tree[2*i + 1], self.tree[2*i + 2])
    
    def update(self, k, x):
        k += self.num - 1
        self.tree[k] = x
        while k >= 1:
            k = (k - 1) // 2
            self.tree[k] = self.operation(self.tree[2*k + 1], self.tree[2*k + 2])
    
    def query(self, l, r):
        res = self.identity
        l += self.num - 1
        r += self.num - 1
        while l < r:
            if l % 2 == 0:
                res = self.operation(res, self.tree[l])
                l += 1
            if r % 2 == 0:
                res = self.operation(res, self.tree[r - 1])
            l = (l - 1) // 2
            r = (r - 1) // 2
        return res

N, Q = [int(i) for i in input().split()]

H, W = SegTree([N]*N, min, N), SegTree([N]*N, min, N)
revd = 0
for _ in range(Q):
    t, x = [int(i) for i in input().split()]
    if t == 1:
        h = H.query(x, N + 1)
        w = W.query(h, N + 1)
        revd += h - 2
        W.update(h, min(x, w))
    else:
        w = W.query(x, N + 1)
        h = H.query(w, N + 1)
        revd += w - 2
        H.update(w, min(x, h))

ans = (N - 2)*(N - 2) - revd
print(ans)
### BUGGY CODE ###

K = int(input())

if (K%10) % 2 == 0:
    print(-1)

elif (K%10) % 5 == 0:
    print(-1)
else:
    num = 7
    for i in range(K):
        if num % K == 0:
            print(str(i+1))
            break
        num = num *10 + 7
    else:
        print(-1)


### FIXED CODE ###

K = int(input())

t = 7
for i in range(K):
    if t % K == 0:
        print(i + 1)
        break
    t = (t * 10 + 7) % K
else:
    print(-1)
### BUGGY CODE ###

a,b,x=map(int,input().split())
ans=0
for i in range(a,b+1):
    if i%x==0:
        ans += 1
print(ans)

### FIXED CODE ###

a,b,x=map(int,input().split())
if a%x==0:
    print(b//x-a//x+1)
else:
    print(b//x-a//x)
### BUGGY CODE ###

n, m = map(int, input().split())
card = [0] * n
l = []
r = []

for i in range(m):
    l1, r1 = map(int, input().split())
    l.append(l1)
    r.append(r1)

for i in range(m):
    for j in range(l[i], r[i]+1):
        card[j-1] += 1


ans = 0
for c in card:
    if c >= m:
        ans += 1
print(ans)


### FIXED CODE ###

from itertools import accumulate

n, m = map(int, input().split())
card = [0] * (n + 1)

for _ in range(m):
    l, r = map(int, input().split())
    card[l-1] += 1
    card[r] -= 1

ans = 0
for i in accumulate(card):
    if i == m:
        ans += 1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

sys.setrecursionlimit(10**5 + 5)  # 再帰回数の上限！！

n = int(input())
A = [-1] + [int(input()) - 1 for i in range(n-1)]

M = [[] for i in range(n)]
for i in range(1, n):
    M[A[i]].append(i)

# 0-indexedの場合
V = [0] * n

# print(M)

def des(x):
    D = []
    V[x] = 1
    for i in M[x]:
        if V[i] == 0:
            V[i] = 1
            D.append(des(i))
    if len(D) > 1:
        D.sort(reverse=True)
    # print(x,D)
    for i in range(len(D)):
        D[i] += i+1
    if len(D) == 0:
        ans = 0
    else:
        ans = max(D)
    return ans

print(des(0))

### FIXED CODE ###

import sys
input = sys.stdin.readline

sys.setrecursionlimit(10**5 + 5)  # 再帰回数の上限！！

n = int(input())
A = [-1] + [int(input()) - 1 for i in range(n-1)]

M = [[] for i in range(n)]
for i in range(1, n):
    M[A[i]].append(i)

# 0-indexedの場合
V = [0] * n

# print(M)

def des(x):
    D = []
    V[x] = 1
    for i in M[x]:
        if V[i] == 0:
            V[i] = 1
            D.append(des(i))
    D.sort(reverse=True)
    # print(x,D)
    for i in range(len(D)):
        D[i] += i+1
    if len(D) == 0:
        ans = 0
    else:
        ans = max(D)
    return ans

print(des(0))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
s = 0
for i in range(n):
    for j in range(i + 1, n):
        s += a[i] * a[j]
        s %= 1000000007
print(s % 1000000007)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
s1 = sum(a)
s2 = 0
ans = 0
for i in range(n - 1):
    s2 += a[i]
    ans += a[i] * (s1 - s2)
print(ans % 1000000007)
### BUGGY CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxint


def max_heapify(heap, i, heap_size):
    L = i * 2
    R = L + 1
    if L <= heap_size and heap[L][0] < heap[i][0]:
        largest = L
    else:
        largest = i
    if R <= heap_size and heap[R][0] < heap[largest][0]:
        largest = R
    if largest != i:
        heap[i], heap[largest] = heap[largest], heap[i]
        max_heapify(heap, largest, heap_size)


def main():
    num = int(stdin.readline())

    L = []
    for _ in xrange(num):
        it = iter(int(s) for s in stdin.readline().split()[1:])
        L.append([(next(it), next(it)) for _ in xrange(next(it))])

    weight = [[maxint, i] for i in xrange(num)]
    weight[0][0] = 0
    V = set(xrange(1, num))
    W = weight[:]
    wn = num
    index = 0

    while V:
        for v, cost in L[index]:
            if v not in V:
                continue
            weight[v][0] = min(weight[v][0], cost + weight[index][0])

        for i in xrange(wn//2, 0, -1):
            max_heapify(W, i, wn-1)
        index = W[1][1]
        W[1] = W[-1]
        wn -= 1
        del W[-1]
        V.remove(index)

    for d, i in weight:
        print(i, d)


main()

### FIXED CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxsize


def main():
    num = int(stdin.readline())

    edges = []
    for _ in range(num):
        ns = [int(s) for s in stdin.readline().split()]
        for i in range(ns[1]):
            edges.append((ns[0], ns[2*i+2], ns[2*i+3]))

    dis = [maxsize] * num
    dis[0] = 0

    while 1:
        update = False
        for from_, to, cost in edges:
            if dis[from_] < maxsize and dis[to] > cost + dis[from_]:
                dis[to] = cost + dis[from_]
                update = True

        if not update:
            break

    for i, d in enumerate(dis):
        print(i, d)


main()
### BUGGY CODE ###

import numpy as np

# 入力
N, W = map(int, input().split())
wv = np.array([[int(i) for i in input().split()] for j in range(N)])

# DPテーブル
dp = np.zeros((N+1)*(W+1), dtype=int).reshape((N+1), (W+1))

# DPループ
for i in range(N):    # i番目の荷物について検討する
    for sum_w in range(W+1):    # 遷移の行き先の総重量
        # i番目の荷物を選ぶ場合
        if sum_w - wv[i][0] >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w-wv[i][0]]+wv[i][1])
        
        # i番目の荷物を選ばない場合
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])
        
# 二次元リストの一番右下が最適解
print(dp[N][W])

### FIXED CODE ###

import numpy as np

# 入力
N, W = map(int, input().split())
wv = np.array([[int(i) for i in input().split()] for j in range(N)])

# DPテーブル
dp = np.zeros((N+1)*(W+1), dtype=int).reshape((N+1), (W+1))

# DPループ
for i in range(N):    # i番目の荷物について検討する
    dp[i+1][:wv[i-1][0]] = dp[i][:wv[i-1][0]]
    dp[i+1][wv[i-1][0]:] = np.maximum(dp[i][wv[i-1][0]:], dp[i][:(W+1)-wv[i-1][0]] + wv[i-1][1])
        
# 二次元リストの一番右下が最適解
print(dp[N][W])
### BUGGY CODE ###

#3問目
NM = input().split()
N,M = int(NM[0]), int(NM[1])
A = []
dp = [0] * (N+1)
dp[0] = 1
dp[1] = 1
MOD = 1000000007
for _ in range(M):
    A.append(int(input()))
    
if(1 in A):
    dp[1] = 0

for i in range(2, N+1):
    #貰うdp
    if(i in A):
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + dp[i-2]
    dp[i] = dp[i] % MOD
    
print(dp[N])

### FIXED CODE ###

N, M = map(int, input().split())
a = set([int(input()) for _ in range(M)])
INF = 1000000007

dp = [0] * (N + 1)
dp[0] = 1
if 1 not in a:
	dp[1] = 1
else:
	dp[1] = 0
for i in range(2, N + 1):
	if i in a:
		continue
	dp[i] = dp[i - 1] + dp[i - 2]
	dp[i] %= INF

print(dp[N])
### BUGGY CODE ###

import copy

H, W = map(int, input().split())
state = []
for i in range(H):
    row_list = list(input())
    state.append(row_list)


def light(row, col, state):
    lighted_count = 0
    col1 = copy.copy(col)
    next = '.'
    while next == '.':
        lighted_count += 1
        col1 += 1
        if col1 >= W:
            break
        next = state[row][col1]
    
    col2 = copy.copy(col)
    next = '.'
    while next == '.':
        lighted_count += 1
        col2 -= 1
        if col2 < 0:
            break
        next = state[row][col2]

    row1 = copy.copy(row)
    next = '.'
    while next == '.':
        lighted_count += 1
        row1 += 1
        if row1 >= H:
            break
        next = state[row1][col]

    row2 = copy.copy(row)
    next = '.'
    while next == '.':
        lighted_count += 1
        row2 -= 1
        if row2 < 0:
            break
        next = state[row2][col]

    lighted_count -= 3
    return lighted_count



def blank_fun(state):
    blank_list = []
    for h in range(H):
        for w in range(W):
            if state[h][w] == '.':
                blank_list.append([h, w])
    return blank_list


blank_list = blank_fun(state)
blank_count = 0
for blank in blank_list:
    row = blank[0]
    col = blank[1]
    blank_count_now = light(row, col, state)

    if blank_count_now > blank_count:
        blank_count = blank_count_now


print(blank_count)






### FIXED CODE ###

import copy
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
S = [[1 if a == '.' else 0 for a in list(input())]  for _ in range(H)]

def main():
    R = copy.deepcopy(S)
    for h in range(H):
        s = 0
        for w in range(W):
            if R[h][w] == 1:
                s += 1
                R[h][w] = s
            else:
                s = 0
        l = 0
        for w in range(W-1, -1, -1):
            if R[h][w] > 0:
                l = max(l, R[h][w])
                R[h][w] = l
            else:
                l = 0

    L = copy.deepcopy(S)
    for w in range(W):
        s = 0
        for h in range(H):
            if L[h][w] == 1:
                s += 1
                L[h][w] = s
            else:
                s = 0
        l = 0
        for h in range(H-1, -1, -1):
            if L[h][w] > 0:
                l = max(l, L[h][w])
                L[h][w] = l
            else:
                l = 0
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, L[h][w]+R[h][w]-1)
    print(ans)

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

import sys

def r(n, k, sl):

    sl.sort(key=lambda x: -x[1])
    tl, dl = zip(*sl)

    gmk = set()
    ce = []
    for s in sl[:k]:
        if s[0] in gmk:
            ce.append(s)
        gmk.add(s[0])

    gop = sum(dl[:k])
    bmk = max(len(set(tl)), k)

    gscr = len(gmk)**2 + gop

    ce.sort(key=lambda x: x[1])
    for c in ce[:bmk-len(gmk)]:
        for s in sl[k:]:
            if s[0] in gmk:
                continue
            k += 1
            gmk.add(s[0])
            gop = gop - c[1] + s[1]
            nscr = len(gmk)**2 + gop
            gscr = max(gscr, nscr)
            break

    return gscr


def main():
    input = sys.stdin.readline
    n, k = list(map(int, input().split()))
    sl = [list(map(int, input().split())) for _ in range(n)]
    print(r(n, k, sl))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

def r(n, k, sl):

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

    gmk = set()
    gop = 0
    ce = []
    for ti, di in sl[:k]:
        if ti in gmk:
            ce.append(di)
        gmk.add(ti)
        gop += di

    gscr = len(gmk)**2 + gop

    for ti, di in sl[k:]:
        if 0 >= len(ce):
            break
        if ti in gmk:
            continue
        gmk.add(ti)
        odi = ce.pop()
        gop = gop - odi + di
        nscr = len(gmk)**2 + gop
        gscr = max(gscr, nscr)

    return gscr


def main():
    input = sys.stdin.readline
    n, k = list(map(int, input().split()))
    sl = [tuple(map(int, input().split())) for _ in range(n)]
    print(r(n, k, sl))


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

h,w=map(int,input().split())
count=0
for i in range(1,h+1):
    for j in range(1,w+1):
        if (i+j)%2==0:
            count=count+1
print(count)

### FIXED CODE ###

h,w=map(int,input().split())
if h ==1 or w==1:
    print(1)
else:
    if h%2==0:
        hk=h//2
        hg=h//2
    else:
        hk=h//2+1
        hg=h//2
    if w%2==0:
        wk=w//2
        wg=w//2
    else:
        wk=w//2+1
        wg=w//2
    print((hk*wk)+(hg*wg))