Harryxun/stf_run huggingface dataset:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  N,K=LI()
  P=LI()
  P=[0]+P
  C=LI()
  C=[0]+C

  l=[[0] for _ in range(N)]
  check=[[False]*(N+1) for _ in range(N)]
  roop=[]
  for i in range(N):
    zahyo=i+1
    check[i][zahyo]=True
    f=False
    for j in range(N+1):
      zahyo=P[zahyo]
      if check[i][zahyo] and not f:
        roop.append(j+1)
        f=True
      score=C[zahyo]
      l[i].append(l[i][-1]+score)
  # print(l)
  # print(roop)

  ans=-inf
  for i in range(N):
    roop_count=roop[i]
    if K<=roop_count:
      ans=max(ans,max(l[i][1:K+1]))
    else:
      ans=max(ans,max(l[i][1:K+1]))
      if l[i][roop_count]>0:
        c=K//roop_count
        _ans=c*l[i][roop_count]
        k=K%roop_count
        _ans+=max(l[i][1:k+1])
        ans=max(ans,_ans)

  return ans

# main()
print(main())


### FIXED CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  N,K=LI()
  P=LI()
  P=[0]+P
  C=LI()
  C=[0]+C

  l=[[0] for _ in range(N)]
  check=[[False]*(N+1) for _ in range(N)]
  roop=[]
  for i in range(N):
    zahyo=i+1
    check[i][zahyo]=True
    f=False
    for j in range(N+1):
      zahyo=P[zahyo]
      if check[i][zahyo] and not f:
        roop.append(j+1)
        f=True
      score=C[zahyo]
      l[i].append(l[i][-1]+score)
  # for i in range(N):
  #   print(l[i])
  # print(roop)

  ans=-inf
  for i in range(N):
    roop_count=roop[i]
    if K<=roop_count:
      ans=max(ans,max(l[i][1:K+1])) # 1巡以内
    else:
      ans=max(ans,max(l[i][1:K+1])) # 1巡以内

      # 2巡目以降（1巡で負になるなら回らない方がいい）
      if l[i][roop_count]>0:
        c=K//roop_count
        _ans1=c*l[i][roop_count]
        k=K%roop_count
        _ans1+=max(l[i][1:k+1]+[0])
        ans=max(ans,_ans1)

        # 可能な巡数まで行かない方がいい場合も
        _ans2=(c-1)*l[i][roop_count]
        _ans2+=max(l[i][:roop_count]+[0])
        ans=max(ans,_ans1,_ans2)

  return ans

# main()
print(main())
#include<iostream>
#include<vector>

using namespace std;

int main(){
    int n,k;
    cin >> n >> k;
    std::vector<char> a(n);

    for (int i =0;i<n;i++)
        cin >> a[i];
    int ans =-(-n/(k-1));
    cout << ans<<endl;


}

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
n=n-k
print(-(-n//(k-1))+1)
def get_pattern(n, y):
    X = 10
    Y = 5
    Z = 1

    y //= 1000
    for nx in range(n+1):
        m = n - nx
        for ny in range(m+1):
            nz = m - ny
            sum = nx * X + ny * Y + nz * Z
            if y == sum:
                return f'{nx} {ny} {nz}'
    return '-1 -1 -1'


n, y = [int(x) for x in input().split()]
print(get_pattern(n, y))

### FIXED CODE ###

def get_pattern(n, y):
    X = 10
    Y = 5
    Z = 1

    y //= 1000
    for nx in range(n+1):
        m = n - nx
        for ny in range(m+1):
            nz = m - ny
            sum = nx * X + ny * Y + nz * Z
            if y == sum:
                return (nx, ny, nz)
    return (-1, -1, -1)


n, y = [int(x) for x in input().split()]
a, b, c = get_pattern(n, y)
print(a, b, c)
W, H, x, y, r=map(int, input().split())
if x>= r and x+r<=W and y>=r and y+r<=
print("Yes")
else:
print("No")


### FIXED CODE ###

W, H, x, y, r = map(int, input().split())
if x >= r and x + r <= W and y >= r and y + r <= H:
  print("Yes")
else:
  print("No")
moji = []
for i in range(3):
  moji[i] = input()[i]
print("".join(moji))

### FIXED CODE ###

moji = []
for i in range(3):
  moji.append(input()[i])
print("".join(moji))
num = int(input())
data = []
for _ in range(num):
    tmp = input()
    data.append(tmp.sort())
data = data.sort()
count = 0
for i in range(num):
    tmp = data[i]
    for j in range(i+1,num):
        if tmp == data[j]:
            count+=1
        else:
            break
print(count)

### FIXED CODE ###

"""
N = list(map(int,input().split()))
S = [str(input()) for _ in range(N)]
S = [list(map(int,list(input()))) for _ in range(h)] 
print(*S,sep="")
"""

import sys
sys.setrecursionlimit(10**6)
input = lambda: sys.stdin.readline().rstrip()
inf = float("inf") # 無限

n = int(input())

data = {}
for _ in range(n):
    temp = "".join(sorted(input()))
    # print(temp)
    if temp in data.keys():
        data[temp] += 1
    else:
        data[temp] = 1
# print(data)

answer = 0
for num in data.values():
    answer += (num*(num-1))//2
print(answer)
n = int(input()
s ={}
for i in range(n):
    string = input()
    s[string] = s[string] + 1 if string in s else 1 
m = int(input()
for i in range(m):
    string = input()
    s[string] = s[string] - 1 if string in s else -1
print(max(0,max(s.values())))

### FIXED CODE ###

n = int(input())
s ={}
for i in range(n):
    string = input()
    s[string] = s[string] + 1 if string in s else 1 
m = int(input())
for i in range(m):
    string = input()
    s[string] = s[string] - 1 if string in s else -1
print(max(0,max(s.values())))
S, T = [input() for i in range(2)]

s = list(S)
t = list(T)

n = len(s) - len(t) + 1
min = len(t)

for a in range(n):
  count = 0 
	for b in range(len(t)):
      if s[a+b] != t[b]:
        count += 1
  if count < min:
    min = count
      
print(min)

### FIXED CODE ###

x = [input() for i in range(2)]
S = x[0]
T = x[1]
moji = len(T)

for a in range(len(S) - len(T) + 1):
  count = 0
  for b in range(len(T)):
    
    if S[a+b] != T[b]:
      count += 1
  if count < moji:
    moji = count

print(moji)
# 文字列の読み込み
s = input()
a = list(s)
    if a[2] == a[3] and a[4] == a[5]:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

# 文字列の読み込み
s = input()
a = list(s)
if a[2] == a[3] and a[4] == a[5]:
    print('Yes')
else:
    print('No')
#E

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

N=int(input())
A=list(map(int,input().split()))
mod=10**9+7

Ainv=[]
for i in range(N):
    Ainv.append(pow(A[i],mod-2,mod))
SSS=0
for u in Ainv:
    SSS=(SSS+u)%mod
    
data=[0]*(max(A)+1)
for i in range(N):
    h=prime_factorize(A[i])
    cnt=1
    for i in range(1,len(h)):
        if h[i]==h[i-1]:
            cnt+=1
        else:
            data[h[i-1]]=max(data[h[i-1]],cnt)
            cnt=1
    data[h[-1]]=max(data[h[-1]],cnt)
ans=1
for i in range(1,len(data)):
    if data[i]==0:
        continue
    else:
        ans=ans*pow(i,data[i],mod)%mod
print(ans*SSS%mod)

### FIXED CODE ###

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

N=int(input())
A=list(map(int,input().split()))
Ainv=[]
for i in range(N):
    Ainv.append(pow(A[i],mod-2,mod))
SSS=0
for u in Ainv:
    SSS=(SSS+u)%mod
    
data=[0]*(max(A)+1)
for i in range(N):
    h=prime_factorize(A[i])
    cnt=1
    for i in range(1,len(h)):
        if h[i]==h[i-1]:
            cnt+=1
        else:
            data[h[i-1]]=max(data[h[i-1]],cnt)
            cnt=1
    if h:
        data[h[-1]]=max(data[h[-1]],cnt)
ans=1
for i in range(1,len(data)):
    if data[i]==0:
        continue
    else:
        ans=ans*pow(i,data[i],mod)%mod
print(ans*SSS%mod)
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n = input()
if n == "aaa" or  == "bbb":
    print("No")
else:
    print("Yes")




### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
n = input()
if n == "AAA" or n == "BBB":
    print("No")
else:
    print("Yes")
import networkx as nx
n,m=map(int,input().split())
a=[[tuple(i) for i in input().split()] for _ in range(m)]
g=nx.Graph()
g.add_edges_from(a)
print(sorted([len(i) for i in nx.connected_components(g)])[-1])

### FIXED CODE ###

import networkx as nx
n,m=map(int,input().split())
if m==0:print(1);exit()
a=[[i for i in input().split()] for _ in range(m)]
g=nx.Graph()
for x in a:
     g.add_edge(x[0],x[1])
print(len(sorted(nx.connected_components(g),key=len,reverse=True)[0]))
n = int(input().strip().split())
arr = [int(i) for i in input().strip().split()]
result = {i:0 for i in range(1, n + 1)}
for i, j in enumerate(arr, 2):
    result[j] += 1
    
for i in result.values():
    print(i)

### FIXED CODE ###

n = int(input().strip())
arr = [int(i) for i in input().strip().split()]
result = {i:0 for i in range(1, n + 1)}
for i, j in enumerate(arr, 2):
    result[j] += 1
    
for i in result.values():
    print(i)
s=input().split()
i=int(s[0])
j=int(s[1])
amari=[]
a=""
if i<j:
  p_1=j
  p_2=i
elif i==j:
  a=str(i)
elif i>j:
  p_1=i
  p_2=j
while a=="":
  am=p_1%p_2
  if am==0:
    break
  amari.append(am)
  p_1=p_2
  p_2=am
a=str(amari[-1])
print(a)

### FIXED CODE ###

i=int(input())
j=int(input())
a=6-(i+j)
print(str(a))
t, x = map(int, input())
print(t/x)

### FIXED CODE ###

a, b = map(int, input().split())
print(a/b)
n = int(input())
v = list(map(int,input().split()))
a = [v[i] for i in range(n) if i%2==0]
b = [v[i] for i in range(n) if i%2==1]

x = 0
y = 0
p=0
q=0

for i in range(10**5):
    if x<a.count(i):
        p=i
        x=a.count(i)
    if y<b.count(i):
        q=i
        y=b.count(i)

print(n-x-y)

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

input = raw_input()

result = " "
for i in range(0, 3):
    if input[i] == "1":
        result += "9"
    elif input[i] == "9":
        result += "1"
    else:
        result += input[i]

print int(result)
# abc123_a.py
a=int(input())
b=int(input())
c=int(input())
d=int(input())
e=int(input())
k=int(input())

l=[a,b,c,d,e]
size=len(l)
for i in range(size-1):
 if (l[i+1]-l[i]) > k:
  print(":(")
  exit(-1)

print("Yay!")


### FIXED CODE ###

# abc123_a.py
a=int(input())
b=int(input())
c=int(input())
d=int(input())
e=int(input())
k=int(input())

l=[]
# l=[a,b,c,d,e]
l.append(a)
l.append(b)
l.append(c)
l.append(d)
l.append(e)

size=len(l)
for i in range(size):
 for j in range(i,size):
  if i == j:
   continue
  if (l[j]-l[i]) > k:
   print(":(")
   exit()

print("Yay!")
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

count1 = 0
count2 = 0

AB = []
AB_new = []
A_new = sorted(A)
B_new = sorted(B)

for i in range(N):
    AB.append([A[i],B[i]])
    AB_new.append([A_new[i],B_new[i]])
    
aaa = sorted(AB, key=lambda x:(x[0],x[1]))

for i in range(N):
    if B_new[i] >= A_new[i]:
        count2 += 1

for i in range(N):
    for j in range(N):
        if aaa[i] == AB_new[j]:
            count1 = 1
            break
        if AB_new[j][0] > aaa[i][0]:
            break
    if count1 == 1:
        break

if count1 == 1 and count2 == N:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

N = int(input())

if N%2 == 0:
    print(int(N/2)-1)
else:
    print(int(N//2))
from fractions import gcd
from functools import reduce

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


if __name__ == '__main__':
    n, m = list(map(int, input().split(" ")))
    a = list(map(int, input().split(" ")))
    a = list(set(a))

    if j in a:
        if j % 2 != 0:
            print("0")

    l = lcm_list(a)

    i = l / 2

    if m < i:
        print("0")
    else:
        print(int(((m - i) // l) + 1))

### FIXED CODE ###

from fractions import gcd
from functools import reduce
import sys
sys.setrecursionlimit(10 ** 7)

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


if __name__ == '__main__':
    n, m = list(map(int, input().split(" ")))
    a = list(map(int, input().split(" ")))
    a = list(set(a))

    # for j in a:
    #     if j % 2 != 0:
    #         print("0")

    # a = [i/2 for i in a]
    l = lcm_list(a)

    # if l == 0:
    #     print(0)
    #     exit()

    if (2 * m) < l:
        print("0")
        exit()

    i = l / 2

    for j in a:
        if i // (j // 2) % 2 == 0:
            print(0)
            exit()

    # if m < i:
    #     print("0")
    else:
        # print("1")
        print(int(((m - i) // l) + 1))
        # print(int((m // i + 1) // 2))
n=int(input())
lst=[int(input()) for i in range(n)]
lst.sort()
i=0
while i<len(lst)-1:
    while lst[i]<lst[i+1]:
        del lst[i+1]
    i+=1
print(len(lst))

### FIXED CODE ###

n=int(input())
lst=[int(input()) for i in range(n)]
lst.sort()
ans=[lst[0]]
for i in range(1,n):
    if ans[-1]!=lst[i]: ans.append(lst[i])
print(len(ans))
A, B, C, D = [int(_) for _ in input().split()]

import math
def dvi_num(b, c):
    return math.floor(b / c)

def lcm(a, b):
    return a * b / math.gcd(a, b)

def dvi_num2(b, c, d):
    return b - dvi_num(b,c) - dvi_num(b,d) + dvi_num(b, lcm(c, d))

ans = dvi_num2(B, C, D) - dvi_num2(A - 1, C, D)

print(ans)

### FIXED CODE ###

A, B, C, D = [int(_) for _ in input().split()]

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

def lcm(a, b):
    return a * b // gcd(a, b)

def dvi_num2(b, c, d):
    return b - b // c - b //d + b // lcm(c, d)

ans = dvi_num2(B, C, D) - dvi_num2(A - 1, C, D)
print(int(ans))
n = str(input())
dai = [Q,W,E,R,T,Y,U,I,O,P,A,S,D,F,G,H,J,K,L,Z,X,C,V,B,N,M]
syou = [q,w,e,r,t,y,u,i,o,p,a,s,d,f,g,h,j,k,l,z,x,c,v,b,n,m]
if n in dai:
  print('A')
else:
  print('a')

### FIXED CODE ###

n = str(input())
dai = ["Q","W","E","R","T","Y","U","I","O","P","A","S","D","F","G","H","J","K","L","Z","X","C","V","B","N","M"]
syou = ["q","w","e","r","t","y","u","i","o","p","a","s","d","f","g","h","j","k","l","z","x","c","v","b","n","m"]
if n in dai:
  print('A')
else:
  print('a')
import copy
N,K = list(map(int, input().split()))
 
A = list(map(int, input().split()))
 
count = [0]
Check = [0] * N
for i in range(K):
    count.append(A[count[-1]]-1)
    if(Check[count[-1]] == 1):
        break
 
    Check[count[-1]] = 1
    i += 1
 
 
saisyo = count.index(count[-1]) + 1
 
loop_kazu = len(count) - saisyo
K_loop = K - saisyo
 
ans_index = K_loop % loop_kazu
ans = count[saisyo + ans_index] + 1
 
print(ans)
 

### FIXED CODE ###

import copy
N,K = list(map(int, input().split()))
 
A = list(map(int, input().split()))
 
count = [0]
Check = [0] * N
for i in range(K):
    count.append(A[count[-1]]-1)
#    print(count)
    if(Check[count[-1]-1] == 1):
        break
 
    Check[count[-1]-1] = 1
    i += 1
 
saisyo = count.index(count[-1]) + 1
#print(count,saisyo)
 
if(saisyo == len(count)):
    saisyo = 0
 
loop_kazu = len(count) - saisyo
 
if(K > loop_kazu):
    K_loop = K - saisyo
 
    ans_index = K_loop % loop_kazu
    ans = count[saisyo + ans_index] + 1
 
    print(ans)
 
else:
    print(count[K]+1)
import math
N = int(input())
fn = math.factorial(N)
ans = int(math.factorial(N)%(math.pow(10,9)+7))
print(ans)

### FIXED CODE ###

if __name__ == '__main__':
    N = int(input())
    ans = 1
    for i in range(1,N+1) :
        ans *= i
        # 剰余演算の分配則
        ans %= 1000000007
    ans %= 1000000007
    print(ans)
N=int(input())
a=[[0 for j in range(N-1)] for i in range(N)]
for i in range(N):
  line=list(map(int,input().split()))
  for j in range(N-1):
    a[i][j]=line[j]-1

id=[[0 for j in range(N+5)] for i in range(N+5)]
v=0
for i in range(N-1):
  for j in range(i+1,N):
    id[i][j]=v
    v+=1

def toId(i,j):
  if i>j:
    i,j=j,i
  return id[i][j]

to=[[] for i in range(N*(N+1)//2)]
for i in range(N):
  for j in range(N-1):
    a[i][j]=toId(i,a[i][j])
  for j in range(N-2):
    to[a[i][j+1]].append(a[i][j])
    
visited=[False for i in range(N*(N-1)//2)]
calculated=[False for i in range(N*(N-1)//2)]
dp=[0 for i in range(N*(N-1)//2)]

def dfs(v):
  if visited[v]:
    if not calculated[v]:
      return -1
    return dp[v]
  visited[v]=True
  for u in to[v]:
    val=dfs(u)
    if val==-1:
      return -1
    if val+1>dp[v]:
      dp[v]=val+1
  calculated[v]=True
  return dp[v]
    
ans=0
for i in range(N*(N-1)//2):
  res=dfs(i)
  if res==-1:
    print(-1)
    break
  if ans<res:
    ans=res
else:
  print(ans+1)

### FIXED CODE ###

N=int(input())
a=[[0 for j in range(N-1)] for i in range(N)]
for i in range(N):
  line=list(map(int,input().split()))
  for j in range(N-1):
    a[i][j]=line[j]-1
  a[i]=a[i][::-1]
    
q=[]

#seen=[[False for j in range(N)] for i in range(N)]

# 選手nが試合できるならqueに入れる
def check(i):
  if len(a[i])==0:
    return False
  j=a[i][-1]
  if a[j][-1]==i:
    q.append([i,j])
  
for i in range(N):
  check(i)
  
from collections import defaultdict

day=0
while q:
  day+=1
 # q=sorted(q)
  prevQ=q.copy()
  q=[]
  matched=defaultdict(list)
  for p in prevQ:
    i=p[0]
    j=p[1]
    if i>j:
      i,j=j,i
    if matched[i]:
      continue
    a[i].pop()
    a[j].pop()
    check(i)
    check(j)
    matched[i].append(j)
    
for i in range(N):
  if len(a[i])!=0:
    print(-1)
    break
else:
  print(day)
A1,A2,A3 = list(map(int, input().split()))

if A1+A2+A3 => 22:
    print('bust')
else:
    print('win')

### FIXED CODE ###

A1,A2,A3 = list(map(int, input().split()))

if A1+A2+A3 >= 22:
    print('bust')
else:
    print('win')
#二部グラフにできるのか
#ここからよ
#実は奇サイクルを含まない=二部グラフとなる
#それぞれのレベルで奇サイクルかどうか
#二部グラフを考えて残りでもどんどん二部グラフを考えるイメージ

#最終的には1or2の状態で残る
N=int(input())
ans=[[0]*N for j in range(N)]
#nはvecの長さ
#次の通路のレベル
def dfs(n,vec,level):
    global ans
    #print(vec)
    #print(n)
    l=vec[:n//2]
    r=vec[n//2:]
    for i in l:
        for j in r:
            ans[i][j]=level
    if len(l)>1:
        dfs(len(l),l,level+1)
    if len(r)>1:
        dfs(len(r),r,level+1)


dfs(N,[i for i in range(N)],1)
for i in range(N-1):
    a=[]
    for j in range(N):
        if i<j:
            a.append(str(ans[i][j]))
    print(" ".join(a))

### FIXED CODE ###

m,d=input().split()
m,d=int(m),int(d)

c=0
if d<22:
    print(0)
else:
    for j in range(m):
        for i in range(d-21):
            d1,d10=int(str(i+22)[1]),int(str(i+22)[0])
            #print(d1)
            #print(d10)
            if d1>1 and d10>1 and d1*d10==j+1:
                c+=1
                #print(j+1,i+22)
    print(c)
H, W = map(int, input().split())
lst = [['#'] * (W+2)]
lst += [['#'] + list(input()) + ['#'] for i in range(H)]
lst += [['#'] * (W+2)]


# print (lst)
lst_ue = [[-1] * (W+2) for i in range(H+2)]
lst_shita = [[-1] * (W+2) for i in range(H+2)]
lst_migi = [[-1] * (W+2) for i in range(H+2)]
lst_hidari = [[-1] * (W+2) for i in range(H+2)]

# print (lst_ue)
def ue(i, j):
    if lst_ue[i][j] != -1:
        return lst_ue[i][j]
    if lst[i][j] == '#':
        lst_ue[i][j] = 0
        return 0
    else:
        lst_ue[i][j] = ue(i-1, j) + 1
        return lst_ue[i][j]


def shita(i, j):
    if lst_shita[i][j] != -1:
        return lst_shita[i][j]
    if lst[i][j] == '#':
        lst_shita[i][j] = 0
        return 0
    else:
        lst_shita[i][j] = shita(i+1, j) + 1
        return lst_shita[i][j]        


def hidari(i, j):
    if lst_hidari[i][j] != -1:
        return lst_hidari[i][j]
    if lst[i][j] == '#':
        lst_hidari[i][j] = 0
        return 0
    else:
        lst_hidari[i][j] = hidari(i, j-1) + 1
        return lst_hidari[i][j]        

def migi(i, j):
    if lst_migi[i][j] != -1:
        return lst_migi[i][j]
    if lst[i][j] == '#':
        lst_migi[i][j] = 0
        return 0
    else:
        lst_migi[i][j] = migi(i, j+1) + 1
        return lst_migi[i][j]        

# def shita(i, j):
#     count = 0
#     for k in range(1, H+1):
#         if lst[i+k][j] == '#':
#             return count
#         else:
#             count += 1

# def hidari(i, j):
#     count = 0
#     for k in range(1,W+1):
#         if lst[i][j-k] == '#':
#             return count
#         else:
#             count += 1

# def migi(i, j):
#     count = 0
#     for k in range(1,W+1):
#         if lst[i][j+k] == '#':
#             return count
#         else:
#             count += 1

ans = 0
for i in range(1,H+1):
    for j in range(1, W+1):
        if lst[i][j] != '#':
            # print (i,j, 1 + ue(i,j)+shita(i,j)+hidari(i,j)+migi(i,j))
            ans = max(ans, ue(i,j)+shita(i,j)+hidari(i,j)+migi(i,j)-3)

print (ans)
# print (lst_ue)

### FIXED CODE ###

#上下方向の探索と左右方向の探索をまとめる
#まず表を完成させる-->全マスの探索
H, W = map(int, input().split())
lst = [['#'] * (W+2)]
lst += [['#'] + list(input()) + ['#'] for i in range(H)]
lst += [['#'] * (W+2)]


lst_ue = [[0] * (W+2) for i in range(H+2)]
lst_shita = [[0] * (W+2) for i in range(H+2)]
lst_migi = [[0] * (W+2) for i in range(H+2)]
lst_hidari = [[0] * (W+2) for i in range(H+2)]

for i in range(1, H+1):
    for j in range(1, W+1):
        lst_hidari[i][j] = 0 if lst[i][j] == '#' else 1 + lst_hidari[i][j-1]
    for j in range(W, 0, -1):
        lst_migi[i][j] = 0 if lst[i][j] == '#' else 1 + lst_migi[i][j+1]

for j in range(1, W+1):
    for i in range(1, H+1):
        lst_ue[i][j] = 0 if lst[i][j] == '#' else 1 + lst_ue[i-1][j]
    for i in range(H+1, 0, -1):
        lst_shita[i][j] = 0 if lst[i][j] == '#' else 1 + lst_shita[i+1][j]

ans = 0
for i in range(1,H+1):
    for j in range(1, W+1):
        ans = max(ans, lst_ue[i][j]+lst_shita[i][j]+lst_migi[i][j]+lst_hidari[i][j]-3)

print (ans)
nl=map((int,input().split()))
a=[i+nl[1] for i in range(nl[0])]

a_sum = sum(a)
abs_ = []
for i in range(nl[0]):
  abs_.append(abs(a_sum - a[i]))
idx=abs_.index(min(abs_))
print(a_sum-a[idx])
  

### FIXED CODE ###

N, L = map(int, input().split())
 
if L > 0: print(sum([i for i in range(L+1, L+N)]))
elif L+N-1 < 0: print(sum([i for i in range(L, L+N-1)]))
else: print(sum([i for i in range(L, L+N)]))
X,N = map(int, input().split())
P = list(map(int, input().split()))

table = [0] * 102
ans = X
dist = 102

for p in range(P):
  table[p] = 1

for i in range(102):
  if table[i] == 1:
    continue
  if abs(i - X) < dist:
    ans = i
    dist = abs(i - X)
  elif abs(i - X) == dist:
    ans = min(i, ans)

### FIXED CODE ###

X,N = map(int, input().split())
P = list(map(int, input().split()))

table = [0] * 102
ans = X
dist = 102

for p in P:
  table[p] = 1

for i in range(102):
  if table[i] != 0:
    continue
  if abs(i - X) < dist:
    ans = i
    dist = abs(i - X)
  elif abs(i - X) == dist:
    ans = min(i, ans)

print(str(ans))
s=input()
l=len(s)
ans=10**18
for i in range(l-1):
  if s[i]!=s[i+1]:
    tmp=max(i+1,n-i-1)
    ans=min(ans,tmp)
print(ans)

### FIXED CODE ###

s=input()
l=len(s)
ans=l
for i in range(l-1):
  if s[i]!=s[i+1]:
    tmp=max(i+1,l-i-1)
    ans=min(ans,tmp)
print(ans)
import sys

n = 0

S = sys.argv[1]

for i in range(len(S)):
    if S[i]=="+": n+=1
    else: n-=1

print(n)



### FIXED CODE ###

import sys
 
n = 0
 
S = input()

for i in range(0,4):
    if S[i]=="+": n+=1
    else: n-=1
 
print(n)
S = input()
K = int(input())

N = len(S)
p = S[0]
c = 0
for i in range(1,N):
    if S[i] == p:
        c += 1
        p = ''
    else:
        p = S[i]

ans = c*K
if S[0] == S[-1] and S[-2] != S[-1]:
    ans += K-1

print(ans)


### FIXED CODE ###

S = input()
K = int(input())

N = len(S)
p = S[0]
c = 0

if N == 1:
    print(K//2)
    exit()

if len(set(S)) == 1:
    print(N*K//2)
    exit()

for i in range(1,N):
    if S[i] == p:
        c += 1
        p = ''
    else:
        p = S[i]

ans = c*K
if S[0] == S[-1]:
    p = S[0]
    c = 1
    for i in range(1,N):
        if p == S[i]:
            c += 1
        else:
            break

    d = 1
    for i in range(2,N+1):
        if p == S[-i]:
            d += 1
        else:
            break

    if (c%2)*(d%2) == 1:
        ans += K-1

print(ans)