Harryxun/stf_run huggingface dataset:
h, w = map(int,input().split())
grids = []
for i in range(h):
    grids.append(input())
    
start = []
for i in range(len(grids)):
    if "#" in grids[i]:
        start = [i, grids[i].index("#")]
        break

if len(start) == 0:
    quit

queue = [start]
check = [start]
ans = "No"
while len(queue) != 0:
    x, y = queue[0][0], queue[0][1]
    queue.pop(0)

    if x > 0:
        if grids[x-1][y] == "#" and [x-1, y] not in check:
            queue.append([x-1, y])
            check.append([x-1, y])
    if x < h-1:
        if grids[x+1][y] == "#" and [x+1, y] not in check:
            queue.append([x+1, y])
            check.append([x+1, y])
    if y > 0:
        if grids[x][y-1] == "#" and [x, y-1] not in check:
            queue.append([x, y-1])
            check.append([x, y-1])
    if y < w-1:
        if grids[x][y+1] == "#" and [x, y+1] not in check:
            queue.append([x, y+1])
            check.append([x, y+1])

cnt = 0
for grid in grids:
    cnt += grid.count("#")
    
if cnt == len(check):
    ans = "Yes"
print(ans)

### FIXED CODE ###

H,W = map(int, input().split())
s = []
answer = "Yes"

for i in range(H):
    s.append(str(input()))

for i in range(H):
    for j in range(W):
        if s[i][j] == "#":
            if j != 0 and s[i][j-1] == ".":
                if j+1 != W and s[i][j+1] == ".":
                    if i != 0 and s[i-1][j] == ".":
                        if i+1 != H and s[i+1][j] == ".":
                            answer ="No"

print(answer)
n,*a=open(0).read().split();f=float;;print(sum([f(a[s])*380000,f(a[s])][a[s+1]=="JPY"]for s in range(0,int(n)*2,2)))

### FIXED CODE ###

n=int(input())
ans=0
for i in range(n):
  a,b=input().split()
  if b=="JPY":
    ans+=int(a)
  else:
    ans+=float(a)*380000.0
print(ans)
import sys
input = sys.stdin.readline
import math
 
def INT(): return int(input())
def MAPINT(): return map(int, input().split())
def LMAPINT(): return list(map(int, input().split()))
def STR(): return input()
def MAPSTR(): return map(str, input().split())
def LMAPSTR(): return list(map(str, input().split()))
 
f_inf = float('inf')
 
n = INT()
a = sorted(LMAPINT())

ans = [True] * n
for i in range(n)):
  if ans[i] is False:
    continue
  for j in range(i+1, n):
    if a[j] % a[i] == 0:
      ans[j] = False
    if a[j] == a[i]:
      ans[i], ans[j] = False, False
 
print(ans.count(True))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
 
xs = [0] * (max(a) + 1)
 
for v in a:
    if xs[v] == 0:
        for j in range(v, len(xs), v):
            xs[j] += 1
    else:
        xs[v] += 1
print(len(list(filter(lambda v: xs[v] == 1, a))))
n = int(input())
count = 0
for i in range(n):
    x = int(input())
    if (x == 2):
        count += 1
    else if (x % 2 == 0):
        continue
    else:
        if (pow(2, x - 1, 1) == 0):
            count += 1
print(count)
 

### FIXED CODE ###

n = int(input())
count = 0
for i in range(n):
    x = int(input())
    if (x == 2):
        count += 1
    elif (x % 2 == 0):
        continue
    else:
        if (pow(2, x - 1, x) == 1):
            count += 1
print(count)
a, b = map(int(e) for e in input().split)

print(a*b - (a+b) + 1)

### FIXED CODE ###

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

print(a*b - a - b + 1)
S = list(input())
if len(list(set(S))) != 0:
    i =0
    count = 0
    while True:
        if S[i] != S[i+1]:
            count += 1
            S[i] = S[i + 1]
        i += 1
        if i == (len(S)-1):
            break
else:
    count = 0
print(count)
            

### FIXED CODE ###

S = list(input())
if len(list(set(S))) != 1:
    i =0
    count = 0
    while True:
        if S[i] != S[i+1]:
            count += 1
            S[i] = S[i + 1]
        i += 1
        if i == (len(S)-1):
            break
else:
    count = 0
print(count)
# 2019/05/22
# AtCoder Beginner Contest 093 - B

# Input
a, b, k = map(int, input().split())

vals = list()
for i in range(a, b+1):
    vals.append(i)

vals.sort()
# small
for i in range(k):
    print(vals[i])

# large
for i in range(len(vals)-k, len(vals)):
    print(vals[i])


### FIXED CODE ###

# 2019/05/22
# AtCoder Beginner Contest 093 - B

# Input
a, b, k = map(int, input().split())
cnt = b - a + 1

vals = list()
if cnt < k:
    wk = cnt
else:
    wk = k

# small
for i in range(a, a + wk):
    print(i)

if k * 2 > cnt:
    wk = cnt - wk

# large
for i in range(b - wk + 1, b+1):
    print(i)
S = list(input())
if S[0]==S[1] and S[0]==S[3]:
    print('No')
else:
    print('Yes')

### FIXED CODE ###

S = list(input())
if S[0]==S[1] and S[0]==S[2]:
    print('No')
else:
    print('Yes')
a,b = int(input().split())
list = [a+b,a-b,a*b]
print(max(list))


### FIXED CODE ###

a,b = map(int,input().split())
list = [a+b,a-b,a*b]
print(max(list))
x = int(input())
temp = int(x ** 0.25)
for i in range(-temp, temp + 1):
    temp2 = int((i ** 5 + x) ** 0.2)
    if temp2 ** 5 - i ** 5 == x:
        print(temp2, i)
        break

### FIXED CODE ###

x = int(input())
temp = int(x ** 0.25)
flag = True
for i in range(-temp, temp + 1):
    for j in range(-temp, temp + 1):
        if i ** 5 - j ** 5 == x:
            print(i, j)
            flag = False
            break
    if flag == False:
        break
N, Y = map(int, input().split())

flag = True
def f(x_1,x_2):
    global flag
    x_3 = int((Y - 10000*x_1 - 5000*x_2) / 1000)
    if x_1 + x_2 + x_3 == N:
        print(str(x_1) + " " + str(x_2) + " " + str(x_3))
        flag = False

for i in range(Y // 10000 + 1):
    spliting = i + int((Y - 10000*i) / 2 // 5000)
    
    if spliting <= N:
        for k in range(spliting + 1):
            f(i,k)
            if flag == False:
                break
    else:
        for k in range(spliting , (Y - 10000*a) // 5000 + 1):
            f(i,k)
            if flag == False:
                break
    if flag == False:
        break
    
if flag:
    print("-1 -1 -1")

### FIXED CODE ###

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

flag = True

for i in range(Y // 10000 + 1):
    for k in range((Y - 10000*i) // 5000 + 1):
        l = int((Y - 10000*i - 5000*k) / 1000)
        if (i + k + l) == N:
            print(str(i) + " " + str(k) + " " + str(l))
            flag = False
            break
    if flag == False:
        break
if flag:
    print("-1 -1 -1")
import fractions

N = int(input())
inp_ints = list(map(int, input().split()))
ints = list(set(inp_ints)) * 2
""" uniq_ints = list(set(inp_ints))

ints = uniq_ints
for m in uniq_ints:
    if inp_ints.count(m) >= 2:
        ints.append(m) """

gcd = 0
result = 1
holed_ints = []
for i in range(N):
    holed_ints = ints[:i] + ints[i+1:]
    gcd = 0
    for j in range(N-1):
        gcd = fractions.gcd(gcd, holed_ints[j])
    if gcd > result:
        result = gcd

print(result)

### FIXED CODE ###

import fractions

integral_count = int(input())
blackboard_integers = list(map(int, input().split()))

gcd_integers = list(set(blackboard_integers))

gcd = 0
result = 1
for i in range(len(gcd_integers)):
    gcd = 0
    if blackboard_integers.count(gcd_integers[i]) >= 2:
        for n in gcd_integers:
            gcd = fractions.gcd(gcd, n)
    else:
        for n in gcd_integers[:i]:
            gcd = fractions.gcd(gcd, n)
        for n in gcd_integers[i+1:]:
            gcd = fractions.gcd(gcd, n)
    if gcd > result:
        result = gcd

print(result)
def makerectangle(n , a):

    listmax = []
    a.sort(reverse=True)
    for i in range(n):
        if a[i] == a[i + 1] and listmax.count(a[i]) == 0:
            if a[i] == a[i + 3] and len(listmax) == 0:
                return a[i] * a[i]
            else:
                listmax.append(a[i])
        if len(listmax) > 1:
            return listmax[0] * listmax[1]
    return 0


def main():
    n = int(input())
    a = list(map(int,input().split()))
    print(makerectangle(n , a))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def makerectangle(n , a):

    listmax = []
    a.sort(reverse=True)
    for i in range(n):
        if len(a) > i + 1 and a[i] == a[i + 1] and listmax.count(a[i]) == 0:
            if len(a) > i + 3 and a[i] == a[i + 3] and len(listmax) == 0:
                return a[i] * a[i]
            else:
                listmax.append(a[i])
        if len(listmax) > 1:
            return listmax[0] * listmax[1]
    return 0


def main():
    n = int(input())
    a = list(map(int,input().split()))
    print(makerectangle(n , a))

if __name__ == '__main__':
    main()
while 1:
	try:
		r={}
		n=input()
		l=m=0
		for i in [1]*n:
			p,d1,d2=map(int,raw_input().split())
			d=d1+d2
			if d>m:l,m=p,d
		print l,m
	except syntaxError:
		pass

### FIXED CODE ###

while 1:
    try:
        n=input()
        if n==0:break
        l=m=0
        for i in [1]*n:
            p,d1,d2=map(int,raw_input().split())
            d=d1+d2
            if d>m:l,m=p,d
        print l,m
    except SyntaxError:
        pass
input()
print(" ".join.(input().split()[::-1])

### FIXED CODE ###

input()
print(" ".join(input().split()[::-1]))
s = input()
for i in range(len(s)):
  if s[i] == 'A':
    left = i
    break
    
for i in range(len(s)):
  if s[N-1-i] == 'Z':
    right = N-1-i
    break
    
print(right - left + 1)


### FIXED CODE ###

s = input()
N = len(s)
for i in range(N):
  if s[i] == 'A':
    left = i
    break
    
for i in range(N):
  if s[N-1-i] == 'Z':
    right = N-1-i
    break
    
print(right - left + 1)
N, Q = map(int, input().split())

if N > 1000:
    import sys
    sys.setrecursionlimit(N)

Edges = list([] for _ in range(N))
for i in range(N-1):
    a, b = map(int, input().split())
    Edges[a-1].append(b-1)
    Edges[b-1].append(a-1)
P = [0 for _ in range(N)]
for i in range(Q):
    p, x = map(int, input().split())
    P[p-1] += x

gone = [False for _ in range(N)]

def dfs(counter, count, cur_node):
    count += P[cur_node]
    gone[cur_node] = True
    counter[cur_node] += count
    for next_node in Edges[cur_node]:
        if gone[next_node]:
            continue
        dfs(counter, count, next_node)

counter = [0 for _ in range(N)]
dfs(counter, 0, 0)

for c in counter:
    print(c)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

N, Q = map(int, input().split())
Edges = list([] for _ in range(N))
for i in range(N-1):
    a, b = map(int, input().split())
    Edges[a-1].append(b-1)
    Edges[b-1].append(a-1)
P = [0 for _ in range(N)]
for i in range(Q):
    p, x = map(int, input().split())
    P[p-1] += x

gone = [False for _ in range(N)]

def dfs(counter, count, cur_node):
    count += P[cur_node]
    gone[cur_node] = True
    counter[cur_node] += count
    for next_node in Edges[cur_node]:
        if gone[next_node]:
            continue
        dfs(counter, count, next_node)

counter = [0 for _ in range(N)]
dfs(counter, 0, 0)

for c in counter:
    print(c)
import math
X=int(input())
u=100
y=0
while u>=0:
  u=math.floor(u*1.01)
  y+=1
print(y)


### FIXED CODE ###

import math
X=int(input())
u=100
y=0
while u<X:
  u=math.floor(u*1.01)
  y+=1
print(y)
n , a = map(int,input().split())
if 500%n <= a:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

n = int(input())
a = int(input())

if n%500 <= a:
  print("Yes")
else:
  print("No")
N = int(input())
A = [int(n) for n in input().split()]

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

temp_gcm = gcm(A[0],A[1])
for i in range(2,N):
  temp_gcm = gcm(A[i],temp_gcm)
print(temp_gcm)


### FIXED CODE ###

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

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

temp_gcd = gcd(A[0],A[1])
for i in range(2,N):
     temp_gcd = gcd(A[i],temp_gcd)
print(temp_gcd)
# 大きさnの順列をすべて生成する
from itertools import permutations
def generate_permutations(n):
    perms = permutations(range(1, n+1), n)
    return [perm for perm in perms]

n = int(input())
ptuple = tuple(map(int, input().split()))
qtuple = tuple(map(int, input().split()))
 
perms = generate_permutations(n)
a = perms.index(ptuple)
b = perms.index(qtuple)
print(int(math.fabs(a - b)))

### FIXED CODE ###

import math

def number(plist):
    a = 1
    memo = []
    while len(plist) > 0:
        p = plist.pop(0)
        memo.append(p)
        num = len(set(range(1, p)) - set(memo))
        a += math.factorial(len(plist)) * num
    return a

n = int(input())
plist = list(map(int, input().split()))
qlist = list(map(int, input().split()))

a = number(plist)
b = number(qlist)
print(int(math.fabs(a - b)))
# -*- coding: utf-8 -*-

import math
import sys

A, B, K = (int(i) for i in input().split())

gcd_num = math.gcd(A, B)

if K==1:
    print(gcd_num)
    sys.exit()

yakusuu_array = []
for i in range(1,gcd_num):
    if gcd_num % i == 0:
        yakusuu_array.append(i)
        yakusuu_array.sort(reverse=True)

print(yakusuu_array[K-2])

### FIXED CODE ###

# -*- coding: utf-8 -*-

import fractions

A, B, K = (int(i) for i in input().split())

gcd_num = fractions.gcd(A, B)

if K==1:
    print(gcd_num)
    exit()

yakusuu_array = []
for i in range(1,gcd_num):
    if gcd_num % i == 0:
        yakusuu_array.append(i)
        yakusuu_array.sort(reverse=True)

print(yakusuu_array[K-2])
string = str(input())
  n = 0
  limit = len(string)-4
  secondLimit = len(string)
  size = len(string)-1
  potencys = [0] * 1500 
  potencys.append(1)
  thirdLimit = size
  for i in range(size, 2, -1):
    intValue = int(string[i])
    potencyIndex = 0
    thirdLimit = i - 1
    for j in range(thirdLimit, -1, -1):
      potencyIndex += 1
      if potencyIndex >= len(potencys):
        potencys.append(potencys[-1]*10)
      intValue += int(string[j])* potencys[potencyIndex]
      if i-j > 2 and intValue % 673 == 0:
        n += 1
  print(n)

### FIXED CODE ###

number = str(input())[::-1]
remainderDictionary = {0: 1}
    
sum = 0
x = 1
for i in number:
  x = (x * 10) % 2019
  sum += int(i) * x
  sum %= 2019
  remainderValue = remainderDictionary.get(sum,0) + 1
  remainderDictionary[sum] = remainderValue
     
ans = 0
for i in remainderDictionary:
  value = remainderDictionary[i]
  ans += value * (value - 1) // 2 # N C 2
print(ans)
a, b = map(int,input().split())
v = ""
if a = b:
    v = "Draw"
elif a == 1 or a > b:
    v = "Alice"
elif b == 1 or a < b:
    v = "Bob"
print(v)


### FIXED CODE ###

a, b = map(int,input().split())
v = ""
if a == b:
    v = "Draw"
elif a == 1:
    v = "Alice"
elif b == 1:
    v = "Bob"
elif a > b:
    v = "Alice"
else:
    v = "Bob"

print(v)
def tri(a,b,c):
	return a^2 == b^2 + c^2
for time in range(int(input())):
	x,y,z = [int(i) for i in input().split()]
	if tri(x,y,z):
		print(???YES???)
	else:
		print(???NO???)

### FIXED CODE ###

def tri(a,b,c):
	return a**2 == b**2 + c**2
for time in range(int(input())):
	x,y,z = [int(i) for i in input().split()]
	if tri(x,y,z) or tri(y,z,x) or tri(z,x,y):
		print("YES")
	else:
		print("NO")
n = int(input())
a = list(map(int, input().split()))
a.sort()
maxa = max(a)

dp = {i: 0 for i in range(1, dp+1)}

ans = 0
for i in range(n):
    if dp[a[i]] == 1:
        continue

    if i == n - 1 or a[i] != a[i+1]:
        ans += 1

    prime += a[i]
    while prime <= maxa:
        dp[prime] = 1
        prime += a[i]
    
print(ans)

### FIXED CODE ###

n = int(input())
*A, = map(int, input().split())
maxA = max(A)
# C[a] = A内のaの個数
C = {a: 0 for a in A}
for a in A:
    C[a] += 1
# D[a]=1: Aにaより小さいaの約数が存在する
D = {a: 0 for a in A}
for a in A:
    if C[a] > 0:
        t = 2
        while a * t <= maxA:
            D[a * t] = 1
            t += 1
ans = 0
for a in A:
    if C[a] == 1 and D[a] == 0:
        ans += 1
print(ans)
densya = N * A
if densya >= B:
	print(B)
else:
	print(A)

### FIXED CODE ###

a,b,c = map(int,input().split())
print(min(a*b , c))
length = raw_input()
count = length
answer = raw_input()


def compare(current, i):
  if current[i] < answer[i]:
    answer = current
  elif current[i] == answer[i]:
    compare(current, i+1)

while count > 0:
  if count == length:
    current_word = answer
  if count < length:
    current_word = raw_input()
    compare(current_word, 0)
  count -= 1

print answer
  

### FIXED CODE ###

s = []
n = input()
 
for i in range(n):
    x = raw_input()
    s.append(x)
 
s.sort()
 
print s[0]
A, B, H, M = map(int,input().split())

theta_M = M*6
theta_H = H*30 + M*0.5

theta = abs(theta_M - theta_H)
if theta > 180:
  theta = 360 - theta
  
import math
x = A**2 + B**2 - 2 * 3 * 4 * math.cos(math.radians(theta))
x = math.sqrt(x)
print(x)

### FIXED CODE ###

A, B, H, M = map(int,input().split())

theta_M = M*6
theta_H = H*30 + M*0.5

theta = abs(theta_M - theta_H)
if theta > 180:
  theta = 360 - theta
  
import math
x = A**2 + B**2 - 2 * A * B * math.cos(math.radians(theta))
x = math.sqrt(x)
print(x)
D = 60
U = 2 * 10 ** 5 + 10
to = [[0] * D for _ in range(U)]

N, K = map(int, input().split())
for i, a in enumerate(map(int, input().split())):
    to[0][i] = a - 1
# 表の構築
for i in range(D - 1):
    for j in range(N):
        to[i + 1][j] = to[i][to[i][j]]

v = 0
for i in reversed(range(D)):
    x = 1 << i
    if x <= K:
        v = to[i][v]
        K -= x

print(v + 1)

### FIXED CODE ###

N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))

first = [0] * (N + 1)
second = [0] * (N + 1)
roop1 = []
roop2 = []

now = 1
while True:
    if not first[now]:
        first[now] = 1
        roop1.append(now)
        now = A[now]
    elif not second[now]:
        second[now] = 1
        roop2.append(now)
        now = A[now]
    else:
        break


if K < len(roop1):
    print(roop1[K])
else:
    K -= len(roop1)
    m = K % len(roop2)
    print(roop2[m])
x,a = map(int,input().split())
pritn(0 if x < a else 10)

### FIXED CODE ###

x,a = map(int,input().split())
print(0 if x < a else 10)
import sys
N, M = map(int, input().split())
xrd = [[] for i in range(N)]
x = [None]*N


def check(s, visited=None):
    if visited is None:
        visited = []
    visited.append(s)
    for t, d in xrd[s]:
        if t in visited:
            continue
        if x[t] is None:
            x[t] = x[s] + d
            check(t)
        else:
            if x[t] != x[s] + d:
                print("No")
                sys.exit()


for i in range(M):
    L, R, D = map(int, input().split())
    xrd[L-1].append([R-1, D])
    xrd[R-1].append([L-1, -D])

for i in range(N):
    if x[i] is None:
        x[i] = 0
        check(i)


print("Yes")


### FIXED CODE ###

import sys
sys.setrecursionlimit(200002)

N, M = map(int, input().split())
G = [[] for _ in range(N)]
x = [None] * N

def fail():
    print("No")
    exit()

def dfs(s):
    global x, G
    for t, d in G[s]:
        if x[t] is None:
            x[t] = x[s] + d
            dfs(t)
        else:
            if x[t] != x[s] + d:
                fail()

for _ in range(M):
    L, R, D = map(int, input().split())
    G[L-1].append([R-1,  D])
    G[R-1].append([L-1, -D])

for i in range(N):
    if x[i] is None:
        x[i] = 0
        dfs(i)

print("Yes")
N, K = [int(i) for i in input().split()]
print(int(math.floor(math.log(float(N)/math.pow(K,2), K))) + 1 + 2)

### FIXED CODE ###

import math

N, K = [int(i) for i in input().split()]
print(int(math.floor(math.log(float(N)/math.pow(K,2), K))) + 1 + 2)
import numpy
def main():
  n,m=map(int,input().split())
  a=sorted(list(map(int,input().split())))
  for i in range(m):
    a[-1]=a[-1]//2
    a.sort()
  print(sum(a))
main()


### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
a=[-_ for _ in a]
import heapq
heapq.heapify(a)
for i in range(m):
  temp=-heapq.heappop(a)
  heapq.heappush(a,-(temp//2))
  
print(-sum(a))
print((N=int(input()) * (N+1) /2)

### FIXED CODE ###

N=int(input())
print(int(N * (N+1) /2))
def cmin(a,b):
    if a>b:
        return b
    else:
        return a

N = int(input())
h = list(map(int,input().split()))

dp[] = [0] + [float("inf")]*(N-1)
for i in range(N-2):
    dp[i] = cmin(dp[i],dp[i-1]+abs(h[i-1]-h[i]))
print(dp[-1])

### FIXED CODE ###

N = int(input())
h = list(map(int,input().split()))

cost = [0,abs(h[1]-h[0])]
for i in range(1,N-1):
    cost.append( min(cost[i]+abs(h[i+1]-h[i]), cost[i-1]+abs(h[i+1]-h[i-1])) )
print(cost[-1])
n=int(input());s=input();print(max(len(set(s[:i])&set(s[i:]))for i in range(n))

### FIXED CODE ###

n = int(input())
s = list(input())
a = 0
for i in range(n):
    x = list(set(s[:i]))
    y = list(set(s[i:]))
    t = 0
    for j in x:
        if j in y:
            t += 1
    a = max(a, t)
print(a)
A,B,K = map(int, input().split())
L = list(range(A,B+1))
l = L[:K]
r = L[-K:]
N = sorted(set(l + r))
for i in range(len(N)):
  print(N[i])

### FIXED CODE ###

a,b,k = map(int,input().split())
if (b-a+1) >= (2*k):
  for i in range(k):
    print(a+i)
  for i in reversed(range(0,k)):
    print(b-i)
else:
  for i in range(a,b+1):
    print(i)
#A
s = input()
k = int(input())
s_sum = 0

if s[0] == s[-1]:
    s_f = 1
    for i in range(len(s)):
        if i != 0:
            if s[i] == s[i-1]:
                s_f += 1
            else:
                break
    s_l = 1
    for i in range(len(s)-1 , -1, -1):
        if i != len(s)-1:
            if s[i] == s[i+1]:
                s_l += 1
            else:
                break
                
if s_f + s_l % 2 == 0:
    s_sum += 1

n = 1
for i in range(len(s)):
    if i != 0:
        if s[i] == s[i-1]:
            n += 1
        else:
            if n != 1:
                if n % 2 == 0:
                    s_sum += (n / 2)
                else:
                    s_sum += ((n - 1)/ 2)
                n = 1
                
    if i == (len(s) - 1):
        if n != 1:
            if n % 2 == 0:
                s_sum += (n / 2)
            else:
                s_sum += ((n - 1)/ 2)

print(int(s_sum * k))

### FIXED CODE ###

#A
s = input()
k = int(input())
s_sum = 0

s_f = 1
s_l = 1


if s[0] == s[-1]:
    for i in range(len(s)):
        if i != 0:
            if s[i] == s[i-1]:
                s_f += 1
            else:
                break
                
    
    for i in range(len(s)-1 , -1, -1):
        if i != len(s)-1:
            if s[i] == s[i+1]:
                s_l += 1
            else:
                break
                
    
                
                
    if s_f == len(s):
        print((k * len(s)) // 2)
        
    else:
        n = 1
        is_not_first = False
        for i in range(len(s)):
            if i != 0:
                if s[i] == s[i-1]:
                    n += 1
                else:
                    if not is_not_first:
                        is_not_first = True
                        n = 1
                    else:
                        if n != 1:
                            if n % 2 == 0:
                                s_sum += (n / 2)
                            else:
                                s_sum += ((n - 1)/ 2)
                            n = 1

        x1 = (s_f // 2 + s_l // 2) + s_sum * k
        x2 = ((s_f + s_l)//2) * (k-1)
        print(int(x1 + x2))
        
else:   
    n = 1
    for i in range(len(s)):
        if i != 0:
            if s[i] == s[i-1]:
                n += 1
            else:
                if n != 1:
                    if n % 2 == 0:
                        s_sum += (n / 2)
                    else:
                        s_sum += ((n - 1)/ 2)
                    n = 1
                    

        if i == (len(s) - 1):
            if n != 1:
                if n % 2 == 0:
                    s_sum += (n / 2)
                else:
                    s_sum += ((n - 1)/ 2)
                    

    print(int(s_sum * k))