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

from collections import defaultdict
import sys


sys.setrecursionlimit(10 ** 6)


def find_path(adj, to_node, node, parent=None):
    if node == to_node:
        return [to_node]
    path = None
    for child in adj[node]:
        if child == parent:
            continue
        p = find_path(adj, to_node, child, node)
        if p is None:
            continue
        p = p + [node]
        if path is None or len(path) > len(p):
            path = p
    return path


def depth(adj, node, parent=None):
    ret = 0
    for child in adj[node]:
        if child == parent:
            continue
        d = depth(adj, child, node) + 1
        ret = max(ret, d)
    return ret


def main():
    N, U, V = list(map(int, input().split(' ')))
    U -= 1
    V -= 1
    adj = defaultdict(list)
    for _ in range(N - 1):
        A, B = list(map(lambda x: int(x) - 1, input().split(' ')))
        adj[A].append(B)
        adj[B].append(A)
    path = find_path(adj, U, V)  # to U from V
    path.reverse()
    dist = len(path) - 1
    partial_depth = depth(adj, path[(dist // 2) + 1], path[dist // 2])
    print(partial_depth + (dist // 2))


if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import defaultdict
import sys


sys.setrecursionlimit(10 ** 6)


def depth(adj, node, parent=None):
    ret = 0
    for child in adj[node]:
        if child == parent:
            continue
        d = depth(adj, child, node) + 1
        ret = max(ret, d)
    return ret


def main():
    N, U, V = list(map(int, input().split(' ')))
    U -= 1
    V -= 1
    adj = defaultdict(list)
    for _ in range(N - 1):
        A, B = list(map(lambda x: int(x) - 1, input().split(' ')))
        adj[A].append(B)
        adj[B].append(A)

    path = [-1] * N

    def find_path_on_tree(to_node, node, parent=None, d=0):
        if node == to_node:
            path[d] = node
            return True
        for child in adj[node]:
            if child == parent:
                continue
            if not find_path_on_tree(to_node, child, node, d + 1):
                continue
            path[d] = node
            return True
        return False

    find_path_on_tree(U, V)  # to U from V
    path = [node for node in path if node != -1]
    dist = len(path) - 1
    partial_depth = depth(adj, path[(dist // 2) + 1], path[dist // 2])
    print(partial_depth + (dist // 2))


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

from collections import defaultdict
S = input()[::-1]
mod = 2019
d = defaultdict(int)
s = ""
for i in range(len(S)):
    s = S[i] + s
    d[int(s) % mod] += 1
ans = 0
for k, v in d.items():
    ans += v * (v - 1) // 2
    if k == 0:
        ans += v
print(ans)

### FIXED CODE ###

import collections
S = input()[::-1]
N = len(S)
mod = 2019

ans = 0
x = [0] * N
x[0] = int(S[0]) % mod
ruijo = 10

for i in range(1, N):
    x[i] = (ruijo * int(S[i]) + x[i - 1]) % mod
    if x[i] % mod == 0:
        ans += 1
    ruijo *= 10
    ruijo %= mod
    
d = collections.Counter(x)

for i in d.values():
    ans += i * (i - 1) // 2
    
print(ans)
### BUGGY CODE ###

#s=raw_input()
l=list(input())
q=int(input())

r=False
for i in range(0, q):
    t=input()
    if t[0] == "1":
        r = not r
        #s = s[::-1]
    else:
        if t[2] == "1" and r is False or t[2] == "2" and r is True:
            #s = t[4] + s
            l.insert(0,t[4])
        else:
            #s = s + t[4]
            l.append(t[4])

if r is True:
    #s = s[::-1]
    l = l[::-1]

#print s
print("".join(l))


### FIXED CODE ###

from collections import deque
#s=raw_input()

l=deque(list(input()))
q=int(input())

r=False
for i in range(0, q):
    t=input()
    if t[0] == "1":
        r = not r
        #s = s[::-1]
    else:
        if t[2] == "1" and r is False or t[2] == "2" and r is True:
            #s = t[4] + s
            l.appendleft(t[4])
        else:
            #s = s + t[4]
            l.append(t[4])

if r is True:
    #s = s[::-1]
    l = list(l)[::-1]

#print s
print("".join(l))
### BUGGY CODE ###

n = int(input())

count = 0
List = []
for i in range(n):
    s = input()
    if s not in List:
        count += 1
        List.append(s)

print(count)

### FIXED CODE ###

n = int(input())
List = [[] for i in range(10)]
for i in range(n):
    s = input()
    List[len(s) - 1].append(s)

count = 0
for each_list in List:
    each_list = list(set(each_list))
    count += (len(each_list))



print(count)
### BUGGY CODE ###

N = int(input())
p = list(map(float,input().split()))
DP = [[0 for i in range((N+1)//2)] for i in range(N)]
DP[0][0] = p[0]
if N > 1:
    DP[0][1] = 1-p[0]
for i in range(1,N):
    for j in range((N+1)//2):
        DP[i][j] += p[i]*DP[i-1][j]
        if j != 0:
            DP[i][j] += (1-p[i])*DP[i-1][j-1]
print(sum(DP[-1]))

### FIXED CODE ###

N = int(input())
p = list(map(float,input().split()))
DP = [[0 for i in range((N+1)//2)] for i in range(N)]
DP[0][0] = p[0]
if N > 1:
    DP[0][1] = 1-p[0]
for i in range(1,N):
    for j in range((N+1)//2):
        DP[i][j] += p[i]*DP[i-1][j]
        if j != 0:
            DP[i][j] += (1-p[i])*DP[i-1][j-1]
print(sum(DP[-1]))
### BUGGY CODE ###

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            #i & -iでLSB(least significant bit/最下位 bit)が求まる
            #区間和はLSBだけ引いていく
            i -= i & -i
        return s

    #a_i(1<=i<=n)にxを加算
    #点に対する更新
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

def invnumber(n, S):
    bit = Bit(2*n+1)
    invs = 0
    for i in range(n):
        s = S[i]+n #BITで扱うため
        invs += bit.sum(s) # #i<j
        bit.add(s, 1)
    return invs

n = int(input())
a = list(map(int, input().split()))
r = max(a)+1
l = 0
c = (n*(n+1)//2+1)//2
while r-l > 1:
    m = (l+r)//2
    S = [0]*(n+1)
    for i in range(1, n+1):
        if a[i-1] >= m:
            S[i] = S[i-1] + 1
        else:
            S[i] = S[i-1] - 1
    if invnumber(n+1, S) >= c:
        l = m
    else:
        r = m
print(l)


### FIXED CODE ###

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            #i & -iでLSB(least significant bit/最下位 bit)が求まる
            #区間和はLSBだけ引いていく
            i -= i & -i
        return s

    #a_i(1<=i<=n)にxを加算
    #点に対する更新
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

def invnumber(n, S):
    bit = Bit(2*n+1)
    invs = 0
    for i in range(n):
        s = S[i]+n #BITで扱うため
        invs += bit.sum(s) # #i<j
        bit.add(s, 1)
    return invs

n = int(input())
a = list(map(int, input().split()))
r = max(a)+1
l = 0
c = (n*(n+1)//2+1)//2
while r-l > 1:
    m = (l+r)//2
    S = [0]*(n+1)
    for i in range(1, n+1):
        if a[i-1] >= m:
            S[i] = S[i-1] + 1
        else:
            S[i] = S[i-1] - 1
    if invnumber(n+1, S) >= c:
        l = m
    else:
        r = m
print(l)
### BUGGY CODE ###

l, r = list(map(int,input().split()))
mod = 2019
min = 2019
if 2019 in range(l, r + 1):
    print(0)
    exit()
for i in range(l, r + 1):
    for j in range(i + 1, r + 1):
        if min > (i * j) % mod:
            min = (i * j) % mod
print(min)

### FIXED CODE ###

l, r = list(map(int,input().split()))
mod = 2019
min = 2019
for i in range(l, r + 1):
    for j in range(i + 1, r + 1):
        if min > (i * j) % mod:
            min = (i * j) % mod
        if min == 0:
            print(0)
            exit()
print(min)
### BUGGY CODE ###

N = int(input())
S = input()
dict = {ch : S.count(ch) for ch in S}
ans = 1

for value in dict.values():
    ans *= (value+1)
print((ans-1)%(10**9+7))

### FIXED CODE ###

import collections
N = int(input())
S = input()
mod = 10**9+7

C = collections.Counter(S)
ans = 1

for value in C.values():
    ans *= (value + 1)
print((ans-1)%mod)
### BUGGY CODE ###

n, q = map(int , input().split())
queue = []
for _ in range(n):
    line = input().split()
    queue.append([line[0], int(line[1])])

class my_queue:
    def __init__(self, queue):
        self.queue = queue
    def enqueue(self, item):
        self.queue.append(item)
    def dequeue(self):
        if len(self.queue) != 0:
            item = self.queue[0]
            self.queue = self.queue[1:]
        else :
            item = None
        return item

queue = my_queue(queue)

time = 0
finish_task = []

while(True):
    item = queue.dequeue()
    if item == None:
        break
    elif item[1] <= q:
        time += item[1]
        finish_task.append([item[0], time])
    else :
        time += q
        queue.enqueue([item[0], item[1] - q])

for item in finish_task:
    print(item[0], item[1])

### FIXED CODE ###

n, q = map(int , input().split())
queue = []
for _ in range(n):
    line = input().split()
    queue.append([line[0], int(line[1])])

class my_queue:
    def __init__(self, queue):
        self.queue = queue
    def enqueue(self, item):
        self.queue = self.queue + [item]
        self.queue.append(item)
    def dequeue(self):
        if len(self.queue) != 0:
            item = self.queue[0]
            self.queue = self.queue[1:]
        else :
            item = None
        return item


time = 0
finish_task = []

while(len(queue) != 0):
    item = queue.pop(0)
    if item == None:
        break
    elif item[1] <= q:
        time += item[1]
        finish_task.append([item[0], time])
    else :
        time += q
        queue.append([item[0], item[1] - q])

for item in finish_task:
    print(item[0], item[1])
### BUGGY CODE ###

n=int(input())
l=[int(input()) for i in range(n)]
a=1
ans=0
while a!=2:
    a=l[a-1]
    ans+=1
    if a==1:
        ans=-1
        break
print(ans)
    

### FIXED CODE ###

n=int(input())
l=[int(input()) for i in range(n)]
a=1
ans=0
while a!=2:
    a=l[a-1]
    ans+=1
    if ans==n+1:
        ans=-1
        break
print(ans)
### BUGGY CODE ###

from fractions import gcd
import sys
input = sys.stdin.readline

N,M=map(int,input().split())
List=list(map(lambda x:int(x)/2,map(int, set(input().split()))))

def main():
    LCM=1

    for i in List:
        LCM*=i/gcd(LCM,i)

    for i in List:
        if LCM//i%2==0:
            print(0)
            exit()

    print(int(M//(LCM*2)+M%(LCM*2)//LCM))


if __name__ == '__main__':
    main()


### FIXED CODE ###

from fractions import gcd
import sys
input = sys.stdin.readline

N,M=map(int,input().split())
List=list(map(lambda x:int(x)//2,map(int, set(input().split()))))

def main():
    LCM=1

    for i in List:
        LCM*=i//gcd(LCM,i)

    for i in List:
        if LCM//i%2==0:
            print(0)
            exit()

    print(int(M//(LCM*2)+M%(LCM*2)//LCM))


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

iN,iM = [int(x) for x in input().split()]
iD = 10**9 +7 #法

def fPrimeCounter(iM):
    i = 2
    iS = int(iM ** 0.5) + 1
    aRet = []
    while i < iS or iM != 1:
        iCounter = 0
        while iM % i == 0:
            iM = iM // i
            iCounter += 1
        if 0 < iCounter : aRet.append(iCounter)
        i += 1

    return aRet

#二分累乗法 iDを法として
def fBiPow(iX,iN,iD):
    iY = 1
    while iN > 0:
        if iN % 2 == 0:
            iX = iX * iX % iD
            iN = iN // 2
        else:
            iY = iX * iY % iD
            iN = iN - 1
    return iY

aP = fPrimeCounter(iM)
if aP == [] :
    print (1)
else:
    iMax = max(aP) + iN - 1
    aM = [1] * (iMax + 1)
    #階乗 iD を法とした
    for i in range(1,iMax + 1):
        aM[i] = aM[i-1] * i  % iD
    aInvM = [1]* (iMax + 1)
    aInvM[iMax] = fBiPow(aM[iMax],iD-2,iD)
    #階乗の逆元 iD を法とした
    for i in range(iMax,0,-1):
        aInvM[i-1] = aInvM[i]*i % iD

    iRet = 1
    for i in aP:
        # i + iN -1  C  iN -1
        iRet *= aM[i+iN-1] * aInvM[iN-1] * aInvM[i] % iD
    iRet %= iD
    print(iRet)


### FIXED CODE ###

iN,iM = [int(x) for x in input().split()]
iD = 10**9 +7 #法

def fPrimeCounter(iM):
    i = 2
    iS = int(iM ** 0.5) + 1
    aRet = []
    while i < iS or iM != 1:
        iCounter = 0
        while iM % i == 0:
            iM = iM // i
            iCounter += 1
        if 0 < iCounter : aRet.append(iCounter)
        i += 1

    return aRet

#二分累乗法 iDを法として
def fBiPow(iX,iN,iD):
    iY = 1
    while iN > 0:
        if iN % 2 == 0:
            iX = iX * iX % iD
            iN = iN // 2
        else:
            iY = iX * iY % iD
            iN = iN - 1
    return iY

aP = fPrimeCounter(iM)
if aP == [] :
    print (1)
else:
    iMax = max(aP) + iN - 1
    aM = [1] * (iMax + 1)
    #階乗 iD を法とした
    for i in range(1,iMax + 1):
        aM[i] = aM[i-1] * i  % iD
    aInvM = [1]* (iMax + 1)
    aInvM[iMax] = fBiPow(aM[iMax],iD-2,iD)
    #階乗の逆元 iD を法とした
    for i in range(iMax,0,-1):
        aInvM[i-1] = aInvM[i]*i % iD

    iRet = 1
    for i in aP:
        # i + iN -1  C  iN -1
        iRet *= aM[i+iN-1] * aInvM[iN-1] * aInvM[i] % iD
    iRet %= iD
    print(iRet)
### BUGGY CODE ###

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

ans = 0
for i in range(n):
    tp = p[0:i+1]
    if (min(tp) >= p[i]):
        ans += 1
print(ans)


### FIXED CODE ###

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

ans = 0
pmax = p[0]
for i in range(n):
    if (p[i] <= pmax):
        ans += 1
        pmax = p[i]

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

#入力取得
from fractions import Fraction
import sys
sys.setrecursionlimit(15000)

def fibMul(fn1, fn2):
  a = fn1[0]
  b = fn1[1]
  c = fn2[0]
  d = fn2[1]
  return (a*c + 5*b*d, a*d + b*c)

def fibExp(fn, n):
  if (n == 0):
    return (Fraction(1), Fraction(1));
  if (n % 2 == 0):
    return fibExp(fibMul(fn, fn), n / 2);
  return fibMul(fn, fibExp(fn, n - 1));

def fibMin(fn1, fn2):
  a = fn1[0]
  b = fn1[1]
  c = fn2[0]
  d = fn2[1]
  return (a - c, b - d)

def fibMain(n):
  fibNum1 = (Fraction(1, 2), Fraction( 1, 2))
  fibNum2 = (Fraction(1, 2), Fraction(-1, 2))

  fibNum3 = fibMin(fibExp(fibNum1, n), fibExp(fibNum2, n))
  fibNum4 = (Fraction(0, 1), Fraction(1, 5))
  return fibMul(fibNum3, fibNum4)

def fib(n):
  return fibMain(n)[0].numerator




N, M = map(int, input().split())

a= []

for i in range(M):
    a.append(int(input()))

l = ["1"] * (N + 1)

for a_ele in a:
    l[a_ele] = "0"

l = ''.join(l)

# print(l)

if '00' in l:
    print(0)

else:
    l_arr = l.split('0')
    result = 1
    for l_ele in l_arr:
        result *= fib(len(l_ele))

    result = result % 1000000007
    print(result)


### FIXED CODE ###

def fib(n):
    if n <= 1:
        return n
    result = [1, 0, 0, 1]
    matrix = [1, 1, 1, 0]
    while n > 0:
        if n % 2:
            result = mul(matrix, result)
        matrix = mul(matrix, matrix)
        n //= 2
    return result[2]

def mul(a, b):
    return [a[0]*b[0] + a[1]*b[2],
            a[0]*b[1] + a[1]*b[3],
            a[2]*b[0] + a[3]*b[2],
            a[2]*b[1] + a[3]*b[3]]





N, M = map(int, input().split())

a= []

for i in range(M):
    a.append(int(input()))

l = ["1"] * (N + 1)

for a_ele in a:
    l[a_ele] = "0"

l = ''.join(l)

# print(l)

if '00' in l:
    print(0)

else:
    l_arr = l.split('0')
    result = 1
    for l_ele in l_arr:
        result *= fib(len(l_ele))

        if result > 1000000007:
            result = result % 1000000007

    result = result % 1000000007

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

# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np

# なんこか入力
n,q = map(int, input().split())

# 文字列を一文字ずつのリストに代入 test は['t', 'e', 's', 't']
s = list(input())

# n行の複数列ある数値を二次元配列へ。x[n][?]
x = [[int(i) for i in input().split()] for i in range(q)] 

for i in range(q):
    count = 0
    for j in range(x[i][0]-1,x[i][1]-1):
        if s[j] == "A" and s[j+1] == "C":
            count += 1
#            print(x[i][0],x[i][1],j)
    print(count)




### FIXED CODE ###

# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np

# なんこか入力
n,q = map(int, input().split())

# 文字列を一文字ずつのリストに代入 test は['t', 'e', 's', 't']
s = list(input())

# n行の複数列ある数値を二次元配列へ。x[n][?]
x = [[int(i) for i in input().split()] for i in range(q)] 
c = [0]
# n番目までに何個ACがあるか


count = 0
for i in range(1,n):
    if s[i-1] == "A" and s[i] == "C":
        count += 1
    c.append(count)
    
#print(c)

for i in range(q):
    if x[i][0] == 1:
        print(c[x[i][1]-1])
    else:
        print(c[x[i][1]-1]-c[x[i][0]-1])
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = [0 for j in range(n)]

for i in range(n):
    b[i] = a.index(i+1) + 1

print(*b)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = [0 for j in range(n)]

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

print(*b)
### BUGGY CODE ###

from collections import Counter
import itertools

n = int(input())
x = []
for i in range(n):
  x.append(sorted(input()))
  
x_sort = sorted(x)
ans = 0

counter = Counter(map(tuple, x_sort))
for word, cnt in counter.most_common():
  ans += len(list(itertools.combinations(list(range(cnt)), 2)))
  
print(ans)

### FIXED CODE ###

from collections import Counter
import itertools

n = int(input())
x = []
for i in range(n):
  x.append(sorted(input()))
  
x_sort = sorted(x)
ans = 0

counter = Counter(map(tuple, x_sort))
for word, cnt in counter.most_common():
  ans += (cnt*(cnt-1))//2
  
print(ans)
### BUGGY CODE ###

from itertools import product

N = int(input())
added = set()
ans = []
a = [[i for i in range(j)] for j in range(1,N+1)]
for x in product(*a):
    count = 0
    appeared = set()
    temp = []
    order = [float('inf')] * N
    for y in x:
        if y not in appeared:
            order[y] = 97 + count
            count += 1
            appeared.add(y)
            temp.append(chr(order[y]))
        else:
            temp.append(chr(order[y]))
    s = ''.join(temp)
    if s not in added:
        ans.append(s)
        added.add(s)
for x in sorted(ans):
    print(x)

### FIXED CODE ###

def dfs(s,n):
    if len(s) == n:
        print(s)
    else:
        for i in range(len(set(s))+1):
            dfs(''.join([s,chr(97+i)]),n)

N = int(input())
dfs('a',N)
### BUGGY CODE ###

n = int(input())
h = list(map(int, input().split()))
ans = 0
for i in range(n-1):
    num = min(n, i + h[i] + 1)
    height_1 = h[i]
    for j in range(num, n):
        height_2 = h[j]
        if height_1 + height_2 == (j - i):
            ans += 1

print(ans)

### FIXED CODE ###

from collections import Counter

n = int(input())
h = list(map(int, input().split()))
a = []
b = []
for i in range(n):
    a.append(i + h[i])
    b.append(i - h[i])

x = Counter(a)
y = Counter(b)

z = set(a)
ans = 0
for i in z:
    ans += x[i] * y[i]

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

from fractions import *
n = int(input())
a = list(map(int, input().split()))

mod = 1000000007

l = 1

for i in range(n):
    l = l * a[i] // gcd(l, a[i])

ans = 0
for i in range(n):
    ans += l // a[i]
    ans %= mod

print(ans)

### FIXED CODE ###

from fractions import gcd
n = int(input())
a = list(map(int, input().split()))

mod = 1000000007

l = 1

for i in range(n):
    l = l * a[i] // gcd(l, a[i])

ans = 0
for i in range(n):
    ans += l // a[i]

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

N = int(input())
S = input()
import itertools
print(len(set(itertools.combinations(S,3))))

### FIXED CODE ###

N = int(input())
S = input()
kouho = [str(i).zfill(3) for i in range(0,1000)]
cnt =0
for k in kouho:
    ok = True
    S_temp = S
    for l in k:
        if l in S_temp:
            basho = S_temp.index(l)
            S_temp = S_temp[basho+1:]
        else:
            ok = False
            break
    if ok == True:
        cnt += 1
print(cnt)
### BUGGY CODE ###

N=int(input())
S=[]
count=[]
ans=0
for i in range(N):
  s=sorted(input())
  if s in S:
    ans+=count[S.index(s)]
    count[S.index(s)]+=1
  else:
    S.append(s)
    count.append(1)
print(ans)

### FIXED CODE ###

N=int(input())
l=[]

for i in range(N):
  l.append(str(sorted(input())))

d={}
for i in l:
  d.setdefault(i,0)
  d[i]+=1

ans=0
for i in d.values():
  ans+=i*(i-1)//2
print(ans)
### BUGGY CODE ###

N = int(input())
L = input().split()
L = [int(L[i]) for i in range(len(L))]

tri = 0
for i in range(N):
  for j in range(i+1,N):
    for k in range(j+1,N):
      if L[i] < L[j] + L[k]:
        if L[j] < L[i] + L[k]:
          if L[k] < L[i] + L[j]:
            tri += 1
print(tri)

### FIXED CODE ###

N = int(input())
L = list(map(int,input().split()))
L.sort()
cnt = 0

import bisect
for i in range(N):
  for j in range(i+1,N-1):
    insert = bisect.bisect_left(L,L[i]+L[j]) -j -1
    cnt += insert
        
print(cnt)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
h, w = map(int, input().split())
s = [input() for _ in range(h)]

hdots = [[0]*(w+1) for _ in range(h)]
for j in range(h):
    ndots = 0
    for i in range(1, w+1):
        if s[j][i-1] == '.':
            ndots += 1
        else:
            hdots[j][i-1] = ndots
            ndots = 0
    hdots[j][-1] = ndots if s[j][-1] == '.' else 0
    for i in range(w, 0, -1):
        if s[j][i-1] == '.':
            hdots[j][i] = ndots
        else:
            ndots = hdots[j][i-1]
vdots = [[0]*w for _ in range(h+1)]
for i in range(w):
    ndots = 0
    for j in range(1, h+1):
        if s[j-1][i] == '.':
            ndots += 1
        else:
            vdots[j-1][i] = ndots
            ndots = 0
    vdots[-1][i] = ndots if s[-1][i] == '.' else 0
    for j in range(h, 0, -1):
        if s[j-1][i] == '.':
            vdots[j][i] = ndots
        else:
            ndots = vdots[j-1][i]

ans = 0
for j in range(h):
    for i in range(w):
        nh, nv = hdots[j][i+1], vdots[j+1][i]
        if nh == 0 or nv == 0:
            continue
        ans = max(ans, nh+nv-1)
print(ans)


### FIXED CODE ###

# Refered #5850116 submit
import numpy as np

h, w = map(int, input().split())
s = np.array([list(input()) for _ in range(h)]) == '.'

ups = np.zeros((h, w), dtype = int)
downs = np.zeros((h, w), dtype = int)
lefts = np.zeros((h, w), dtype = int)
rights = np.zeros((h, w), dtype = int)

for i in range(1, h):
    ups[i] = (ups[i-1]+1)*s[i-1]
for i in range(h-2, -1, -1):
    downs[i] = (downs[i+1]+1)*s[i+1]
for j in range(1, w):
    lefts[:, j] = (lefts[:, j-1]+1)*s[:, j-1]
for j in range(w-2, -1, -1):
    rights[:, j] = (rights[:, j+1]+1)*s[:, j+1]
counts = ups+downs+lefts+rights
ans = np.max(counts*s)+1
print(ans)
### BUGGY CODE ###

# 問題文の意味がわからんコンテスト
# 0の場合も自分自身を照らす、っての気づくところからやっと読解
# Kを5000兆回やったあとはすべての要素がNになっとる この収束はわりと早いらしい
n, k = map(int, input().split())
a = list(map(int, input().split()))

for _ in range(k):
    b = [0] * (n + 1)
    for i in range(n):
        b[max(0, i - a[i])] += 1
        b[min(n, i + a[i] + 1)] -= 1
    for i in range(n):
        b[i + 1] += b[i]
    a = b[:n]
    if b[-1] == n:
        break
print(" ".join(list(map(str, a))))


### FIXED CODE ###

# 問題文の意味がわからんコンテスト
# 0の場合も自分自身を照らす、っての気づくところからやっと読解
# Kを5000兆回やったあとはすべての要素がNになっとる この収束はわりと早いらしい
n, k = map(int, input().split())
a = list(map(int, input().split()))

for _ in range(min(k, 100)):
    b = [0] * (n + 1)
    for i in range(n):
        b[max(0, i - a[i])] += 1
        b[min(n, i + a[i] + 1)] -= 1
    for i in range(n):
        b[i + 1] += b[i]
    a = b[:n]
print(" ".join(list(map(str, a))))