Harryxun/stf_run huggingface dataset:
N,A,B,C=map(int,input().split())
S = [input() for _ in range(N)]
table = [A,B,C]
ans = []

def ci(s):
    if s == 'AB':
        return 0,1
    elif s == 'BC':
        return 1,2
    else:
        return 0,2

if A+B+C == 0:
    print('No')
    exit()
elif A+B+C == 1:
    for s in S:
        i,j = ci(s)
        if table[i] == 0 and table[j] == 0:
            print('No')
            exit()
        else:
            if table[i] == 0:
                table[i] = 1
                table[j] = 0
                ans.append(i)
            else:
                table[j] = 1
                table[i] = 0
                ans.append(j)

else:
    for k in range(N):
        i,j= ci(S[k])
        if table[i] > table[j]:
            i,j = j,i
        # print(table,i,j)
        if k + 1 < N:
            i2,j2 = ci(S[k+1])
        if table[i] == 0 and table[j] == 0:
            print('No')
            exit()
        elif table[i] == 0 and table[j] > 0:
            table[i] += 1
            table[j] -= 1
            ans.append(i)
        else:
            table[i] += 1
            table[j] -= 1
            if table[i2] == 0 and table[j2] == 0:
                table[i] -= 2
                table[j] += 2
                ans.append(j)
            else:
                ans.append(i)

print('Yes')
L = ['A','B','C']
for a in ans:
    print(L[a])

### FIXED CODE ###

N,A,B,C=map(int,input().split())
S = [input() for _ in range(N)]
table = [A,B,C]
ans = []

def ci(s):
    if s == 'AB':
        return 0,1
    elif s == 'BC':
        return 1,2
    else:
        return 0,2

if A+B+C == 0:
    print('No')
    exit()
elif A+B+C == 1:
    for s in S:
        i,j = ci(s)
        if table[i] == 0 and table[j] == 0:
            print('No')
            exit()
        else:
            if table[i] == 0:
                table[i] = 1
                table[j] = 0
                ans.append(i)
            else:
                table[j] = 1
                table[i] = 0
                ans.append(j)

else:
    for k in range(N):
        i,j= ci(S[k])
        if table[i] > table[j]:
            i,j = j,i
        # print(table,i,j)
        if k + 1 < N:
            i2,j2 = ci(S[k+1])
        if table[i] == 0 and table[j] == 0:
            print('No')
            exit()
        elif table[i] == 0 and table[j] > 0:
            table[i] += 1
            table[j] -= 1
            ans.append(i)
        else:
            table[i] += 1
            table[j] -= 1
            if k + 1 < N:
                if table[i2] == 0 and table[j2] == 0:
                    table[i] -= 2
                    table[j] += 2
                    ans.append(j)
                else:
                    ans.append(i)
            else:
                ans.append(i)

print('Yes')
L = ['A','B','C']
for a in ans:
    print(L[a])
T1,T2 = map(int,input().split())
A1,A2 = map(int,input().split())
B1,B2 = map(int,input().split())

dis1 = (A1 - B1) * T1
dis2 = (A2 - B2) * T2

if dis1 == -dis2:
    print("infinity")

elif (dis1<0 and dis2<0) or (dis1>0 and dis2>0):
    print("0")

else:
    S = abs(dis1//(dis1+dis2))
    R = abs(dis1%(dis1+dis2)) 
    if rem == 0:
        ans = S*2 
    else:
        ans = S*2 + 1
    
    print(ans)
 

### FIXED CODE ###

T1,T2 = map(int,input().split())
A1,A2 = map(int,input().split())
B1,B2 = map(int,input().split())

dis1 = (A1 - B1) * T1
dis2 = (A2 - B2) * T2

if dis1 > 0:
    dis1 = -dis1
    dis2 = -dis2

if dis1 + dis2 <0:
    print(0)

elif dis1 == -dis2:
    print("infinity")
    
else:
    S = dis1//(dis1+dis2)
    R = dis1%(dis1+dis2) 
    if R == 0:
        ans = S*2 
    else:
        ans = S*2 + 1
    
    print(abs(ans))
(n, l) = map(int, input().split())
d = [l + i for i in range(n)]
c = [abs(i) for i in d.copy()]
nearest0 = c.index(min(c))
d.remove(d[nearest0])
ans = sum(d)
print(ans)

### FIXED CODE ###

(n, l) = map(int, input().split())
d = [l + i for i in range(n)]
c = [abs(i) for i in d.copy()]
nearest0 = c.index(min(c))
d.remove(d[nearest0])
ans = sum(d)
print(ans)
n, k = map(int, input().split())
nums = list(map(int, input().split()))
p = []
m = []

for i in nums:
    if i >= 0:
        p.append(i)
    else:
        m.append(i)

p.sort()
m.sort(reverse = True)

ans = 1
MOD = 1e9 + 7

if n == k:
    for i in nums:
        ans = ans * i % MOD
    print(ans)
    exit()

if not p and k % 2 == 1:
    for i in range(k):
        ans = ans * m[i] % MOD
    print(ans)
    exit()

ps = []
ms = []
cnt = 0
for i in range (k):
    if not p:
        ms.append(m.pop())
        continue
    if not m:
        ps.append(p.pop())
        cnt += 1
        continue
    
    if p[-1] >= abs(m[-1]):
        ps.append(p.pop())
    else:
        ms.append(m.pop())
        cnt += 1

if cnt % 2 == 1:
    if not p or m[-1] / ps[-1] >= p[-1] / ms[-1]:
        ps.pop()
        ms.append(m.pop())
    if not m or m[-1] / ps[-1] < p[-1] / ms[-1]:
        ms.pop()
        ps.append(p.pop())

for i in ps:
    ans = ans * i % MOD
for i in ms:
    ans = ans * i % MOD

print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
A = list(map(int,input().split()))
mod = 10**9+7
plus = []
minus=[]
for i in A:
    if i>=0:
        plus.append(i)
    else:
        minus.append(i)
ok = False
if len(plus)>0:
    if n==k:
        ok = (len(minus)%2==0)
    else:
        ok = True
else:
    ok = (k%2==0)
ans = 1
if not ok:
    A.sort(key=abs)
    for i in range(k):
        ans *= A[i]
        ans %= mod
else:
    plus.sort()
    minus.sort(reverse=True)
    if k%2 == 1:
        ans *= plus.pop()
    P = []
    while len(plus) >= 2:
        P.append((plus.pop())*(plus.pop()))
    while len(minus) >= 2:
        P.append((minus.pop())*(minus.pop()))
    P.sort(reverse=True)
    for i in range(k//2):
        ans *= P[i]
        ans %= mod
print(ans)
import collections
N=int(input())
L=list(map(int,input().split()))
E=[i for i in L[::2]]
O=[i for i in L[1::2]]
e = collections.Counter(E).most_common()
o = collections.Counter(O).most_common()
if e[0][0] != o[0][0]:
    print(N - e[0][1] - o[0][1])
else:
    if len(e) == 1 or len(o) == 1:
        print(N // 2)
    else:
        a = N - e[1][1] - o[0][1]
        b = N - e[0][1] - o[1][1]
        print(min(a, b))

### FIXED CODE ###

print(1110-int(input()))
n,m=map(int,input().split())
c=set(list(range(1,m+1)))#from 1 to m+1 set {}
#print(c)
for i in range(n):
    l=list(map(int,input().split()))
    a=l[1:]
    #l[0] no mean
    c=c & se t(a) # and > & 
    #print(c)
print(len(c))

### FIXED CODE ###

n,m=map(int,input().split())
c=set(list(range(1,m+1)))#from 1 to m+1 set {}
#print(c)
for i in range(n):
    l=list(map(int,input().split()))
    a=l[1:]
    #l[0] no mean
    c=c & set(a) # and > & 
    #print(c)
print(len(c))
a, b, x = map( int, input())

print(b//x - a//x + 1)

### FIXED CODE ###

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

print( b//x - (a-1)//x)
S = str(input())
count = 0
X =[]
for s in S:
    if s == 'A' or s == 'T' or s == 'C' or s == 'G':
        count += 1
    else:
        X.append(count)
        count = 0
print(int(max(X)))

### FIXED CODE ###

S = str(input())

count = 0
X =[]
for n in range(len(S)):
    if n != len(S) -1:
        if S[n] == 'A' or S[n] == 'T' or S[n] == 'C' or S[n] == 'G':
            count += 1
        else:
            X.append(count)
            count = 0
    else:
        if S[n] == 'A' or S[n] == 'T' or S[n] == 'C' or S[n] == 'G':
            count += 1
            X.append(count)
        else:
            X.append(count)
print(int(max(X)))
S = input()

N = len(S)
# Sの各文字は'L', 'R', 'U', 'D'のいずれかであることに注意する
# 1,3,...文字目が'L'でなく、偶数文字目が'R'でないとき 'Yes'とする
for i in range(N):
  if (i % 2 == 0 and S[i] == 'L') or (i % 2 == 1 and S[i] == 'R'):
    ans = 'No'
    break
    
print(ans)

### FIXED CODE ###

S = input()
N = len(S)

# 1,3,...文字目が'R'でも'U'でも'D'でもない、または、2,4,...文字目が'L'でも'U'でも'D'でもないとき、'No'を出力する
ans = 'Yes'
for i in range(N):
  if (i % 2 == 0 and S[i] != 'R' and S[i] != 'U' and S[i] != 'D') or (i % 2 == 1 and S[i] != 'L' and S[i] != 'U' and S[i] != 'D'):
    ans = 'No'
    break
    
print(ans)
def insertionSort( nums, n, g ):
	cnt = 0
	i = g
	n = len( nums )
	while i < n:
		v = nums[i]
		j = i - g
		while 0 <= j and v < nums[j]:
			nums[ j+g ] = nums[j]
			j -= g
			cnt += 1
		nums[ j+g ] = v
		i += 1
	
	return cnt


def shellSort( nums, n ):
	cnt = 0
	g = []
	val =0
	for i in range( 0, n ):
		val = 3*val+1
		if  n < val:
			break
		g.append( val )

	g.reverse( )
	m = len( g )
	print( m )
	print( " ".join( map( str, g ) ) )
	for i in range( 0, m ):
		cnt += insertionSort( nums, n, g[i] )
	print( cnt )


n = int( input( ) )
nums = []
for i in range( 0, n ):
	nums.append( int( input( ) ) )

shellSort( nums, n )
for val in nums:
	print( val )

### FIXED CODE ###

import sys
 
def insertionSort( nums, n, g ):
    cnt = 0
    i = g
    while i < n:
        v = nums[i]
        j = i - g
        while 0 <= j and v < nums[j]:
            nums[ j+g ] = nums[j]
            j -= g
            cnt += 1
        nums[ j+g ] = v
        i += 1
    return cnt
         
def shellSort( nums, n ):
    g = []
    val = 1
    while val <= n:
        g.append( val )
        val = 3*val+1
     
    g.reverse( )
    m = len( g )
    print( m )
    print( " ".join( map( str, g ) ) )
    cnt = 0
    for i in range( m ):
        cnt += insertionSort( nums, n, g[i] )
    print( cnt )
     
n = int( sys.stdin.readline( ) )
nums = []
for i in range( n ):
    nums.append( int( sys.stdin.readline( ) ) )
 
shellSort( nums, n )
print( "\n".join( map( str, nums ) ) )
# DDCC C
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
h,w,k = nm()
C = []
itigo = []
itigo_sum = []
ans = [[] for i in range(h)]
for i in range(h):
    C.append(si())
s = 0
for c in C:
    ii = c.count('#')
    s += ii
    itigo.append(ii)
    itigo_sum.append(s)

itigo_cnt = 0
cnt = 1

for i in range(h):
    itigo_cnt = 1
    if i>=1:
        itigo_cnt += itigo_sum[i-1]
    if itigo[i]==0:
        for j in range(w):
            ans[i].append(ans[i-1][j])
    else:
        cnt = itigo_cnt
        for j in range(w):
            ans[i].append(cnt)
            if C[i][j:j+1]=='#':
                if itigo_sum[i]>cnt:
                    cnt += 1

for aa in ans:
    print(*aa)


### FIXED CODE ###

# DDCC C
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
h,w,k = nm()
C = []
itigo = []
itigo_sum = []
is_copy = []
ans = [[] for i in range(h)]
for i in range(h):
    C.append(si())
s = 0
for c in C:
    ii = c.count('#')
    s += ii
    itigo.append(ii)
    itigo_sum.append(s)

itigo_cnt = 0
cnt = 1

for i in range(h):
    itigo_cnt = 1
    if i>=1:
        itigo_cnt += itigo_sum[i-1]
    if itigo[i]==0:
        continue
    else:
        cnt = itigo_cnt
        for j in range(w):
            ans[i].append(cnt)
            if C[i][j:j+1]=='#':
                if itigo_sum[i]>cnt:
                    cnt += 1
idx = 0
for i,aa in enumerate(ans):
    if aa:
        idx = i
        if is_copy:
            for j in range(len(is_copy)):
                t = is_copy.pop()
                for k in range(w):
                    ans[t].append(ans[i][k])
    else:
        is_copy.append(i)
    
    if i==len(ans)-1:
        for j in range(len(is_copy)):
            t = is_copy.pop()
            for k in range(w):
                ans[t].append(ans[idx][k])

for aa in ans:
    print(*aa)
n=int(input())

ans=[]
while(n!=0):
    m=n%p
    n=n//p
    ans.append(m)

res=list(map(lambda x: chr(ord("a")-1+x),ans))

print("".join(res))

### FIXED CODE ###

n=int(input())

basis=[26**i for i in range(12)]
l=[]
s=0
for b in basis:
    s+=b
    l.append(s)    

i=0
f=12
while(f-i>1):
#     print(f-i)
    x=(i+f)//2
    if l[x]>n:
        f=x
    else:
        i=x

k=n-l[i]
length=i+1

res=[]
for i in range(length):
    q=k//26
    r=k%26
    k=q
    res.append(r)

ans=list(map(lambda x: chr(ord("a")+x),list(reversed(res))))
print("".join(ans))
import numpy as np

h,w = map(int,(input().split()))
s = [list(map(str,input())) for i in range(h)]
l = [[0]*(w+2) for i in range(h+2)]


def addFlag(i,j):
    for x in range(3):
        for y in range(3):
            if l[i+x][j+y] != '#':
                l[i+x][j+y] += 1
                
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            l[i+1][j+1] = '#'
            addFlag(i,j)

l = np.delete(l,[0,h+1],0)
l = np.delete(l,[0,w+1],1)

for i in l:
    if len(i)>1:
        ans = ''.join(i)
    else:
        ans = int(i)
    print(ans)


### FIXED CODE ###

import numpy as np

h,w = map(int,(input().split()))
s = [list(map(str,input())) for i in range(h)]
l = [[0]*(w+2) for i in range(h+2)]


def addFlag(i,j):
    for x in range(3):
        for y in range(3):
            if l[i+x][j+y] != '#':
                l[i+x][j+y] += 1
                
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            l[i+1][j+1] = '#'
            addFlag(i,j)

l = np.delete(l,[0,h+1],0)
l = np.delete(l,[0,w+1],1)


for i in l:
    ans = ''.join(map(str,i))
    print(ans)
import math

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

if a*a*b <= 2*x:
    print(90-math.degrees(math.atan(a**3/(2*(a*a*b-x)))))
else:
    print(90-math.degrees(math.atan(2*x/(a*b*b))))



### FIXED CODE ###

import math
a,b,x=map(int,input().split())
if a*a*b<=2*x:
    c=(b-x/(a**2))*2/a
    ans=math.degrees(math.atan(c))
else:
    c=a*b*b/(2*x)
    ans=math.degrees(math.atan(c))
print(ans)
N,A,B = map(int,input().split())

T = int(N/(A+B))
S = N%(A+B)


if S<A:
	print(T*A+S)
else:
	print(T*A+A)



### FIXED CODE ###

N = list(input())
if N[0] == N[1] == N[2]:
	print("No")
else :
	print("Yes")
#!/usr/bin/env python3.4
# -*- coding: utf-8 -*-

# abc126_d

from collections import namedtuple

DistFrom = namedtuple('DistFrom', ['f', 'dist'])

def main():
    # input
    n, = [int(s) for s in input().split()]
    #if n==1: return
    fs = [[int(s) for s in input().split()] for _ in range(n-1)]
    # getans
    gs = [None] * n
    for i in range(n):
        gs[i] = list()
    for x, y, d in fs:
        x -= 1
        y -= 1
        gs[x].append(DistFrom(y, d))
        gs[y].append(DistFrom(x, d))
    distlist = [None] * n
    def search(cur, prev, dist):
        #distlist[cur] != None: return
        distlist[cur] = dist
        for i, d in gs[cur]:
            if i != prev:
                search(i, cur, dist+d)
    distlist[0] = 0
    for i, d in gs[0]:
        search(i, 0, d)
    ans = [d%2 for d in distlist]
    # output
    for a in ans:
        print(a)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
 
sys.setrecursionlimit(10**5)

n = int(input())
p = [list() for _ in range(n)]
for i in range(n-1):
    u, v, w = [int(s) for s in input().split()]
    u -= 1
    v -= 1
    w %= 2
    p[u].append((v, w))
    p[v].append((u, w))

costs = [-1 for _ in range(n)]

def dfs(cur, dist):
    if costs[cur] != -1:
        return
    costs[cur] = dist
    for v, d in p[cur]:
        dfs(v, dist^d)
dfs(0, 0)

for i in range(n):
    print(costs[i])
mod = 10**9+7
n,m = map(int,input().split())
a = set([int(input()) for _ in range(M)])
dp = [0]*(n+1)
dp[0] = 1
for i in range(1,n+1) :
    dp[i] = (dp[i-1] + dp[i-2]) % mod
    if i in a :
        dp[i] = 0

print(dp[n])

### FIXED CODE ###

mod = 10**9+7
n,m = map(int,input().split())
a = set()
for i in range(m):
  a.add(int(input()))
dp = [0]*(n+1)
dp[0] = 1
for i in range(1,n+1) :
    dp[i] = (dp[i-1] + dp[i-2]) % mod
    if i in a :
        dp[i] = 0
print(dp[n])
h,w = map(int,input().split())
matrix = [["a" for _ in range(w+2)]] + [list("a" + input() + "a") for _ in range(h)] + [["a" for _ in range(w+2)]]

matrix_list1 = []
matrix_list2 = []
cnt = 0

for i in range(1,w+1):
    for j in range(1,h+1):
        if matrix[i][j] == "#":
            tap = [i,j]
            matrix_list1.append(tap)

while len(matrix_list1) != 0:     
    for x,y in matrix_list1:
        if matrix[x+1][y] == ".":
            matrix[x+1][y] = "#"
            tap = [x+1,y]
            matrix_list2.append(tap)
        if matrix[x-1][y] == ".":
            matrix[x-1][y] = "#"
            tap = [x-1,y]
            matrix_list2.append(tap)
        if matrix[x][y+1] == ".":
            matrix[x][y+1] = "#"
            tap = [x,y+1]
            matrix_list2.append(tap)
        if matrix[x][y-1] == ".":
            matrix[x][y-1] = "#"
            tap = [x,y-1]
            matrix_list2.append(tap)
    else:
        matrix_list1 = matrix_list2.copy()
        matrix_list2 = []
        if len(matrix_list1) > 0:
            cnt += 1
    
print(cnt)

### FIXED CODE ###

from collections import deque

h,w = map(int,input().split())
matrix = [["a" for _ in range(w+2)]] + [list("a" + input() + "a") for _ in range(h)] + [["a" for _ in range(w+2)]]

matrix_list1 = deque()
cnt = 0

for i in range(1,h+1):
    for j in range(1,w+1):
        if matrix[i][j] == "#":
            matrix_list1.append([i,j])

while len(matrix_list1) != 0:     
    for _ in range(len(matrix_list1)):
        x,y = matrix_list1.popleft()
        if matrix[x+1][y] == ".":
            matrix[x+1][y] = "#"
            matrix_list1.append([x+1,y])
        if matrix[x-1][y] == ".":
            matrix[x-1][y] = "#"
            matrix_list1.append([x-1,y])
        if matrix[x][y+1] == ".":
            matrix[x][y+1] = "#"
            matrix_list1.append([x,y+1])
        if matrix[x][y-1] == ".":
            matrix[x][y-1] = "#"
            matrix_list1.append([x,y-1])
    else:
        if len(matrix_list1) > 0:
            cnt += 1
    
print(cnt)
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    def ans(self):
        print(len(set(self.par))-1)

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

for i in range(m):
    a,b,c=map(int,input().split())
    uf.union(a,b)
a=1
b=1
c=0
for i in range(3,n+1):
    if uf.same_check(1,i):
        a+=1
    elif uf.same_check(2,i):
        b+=1
    else:
        c+=1
if a>b:
    a+=c
else:
    b+=c
print(a*(a-1)//2+b*(b-1)//2-m)


### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    def ans(self):
        print(len(set(self.par))-1)

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

for i in range(m):
    a,b=map(int,input().split())
    uf.union(a,b)
a=1
b=1
c=0
for i in range(3,n+1):
    if uf.same_check(1,i):
        a+=1
    elif uf.same_check(2,i):
        b+=1
    else:
        c+=1
if a>b:
    a+=c
else:
    b+=c
print(a*(a-1)//2+b*(b-1)//2-m)
n,k=map(int,input().split())
ans=k
for i in range(n-1):
    ans=ans*(k-1)
print(ans)

### FIXED CODE ###

a,b,x=map(int,input().split())
if a%x==0:
    print(b//x-(a-1)//x)
else:
    print(b//x-a//x)
x,y = map (raw_input().split())
print x*y, 2*x+2*y

### FIXED CODE ###

a,b = map(int,raw_input().split())
print ("{0} {1}").format(a*b,2*a+2*b)
a=int(input())
b=int(input())

print(a*b/2)

### FIXED CODE ###

a,b,c=map(int,input().split())
print(int((a*b)/2))
import sys

for line in sys.stdin:
    A=line.split()
    B=map(int,A)

D=B.sort()
e=1

while e != 0:
    e=B[1]%B[0]
    C=[0]
    B[0]=e
    B[1]=C

print B[0]

### FIXED CODE ###

A=map(int,raw_input().split())
A.sort()

while A[1]%A[0]!=0:
    temp=A[0]
    A[0]=A[1]%A[0]
    A[1]=temp

print A[0]
import numpy as np
from itertools import groupby

h,w=map(int,input().split())
M=np.array([list(input()) for i in range(h)])
C=np.array([[0]*w for i in range(h)])
R=np.array([[0]*w for i in range(h)])
L=np.array([[0]*w for i in range(h)])

for i in range(w):
	c=0
	for k,g in groupby(M[:,i]):
		l=len(list(g))
		if k=='#':
			C[c:c+l,i]=0
		else:
			C[c:c+l,i]=l
		c+=l

for i in range(h):
	c=0
	for k,g in groupby(M[i,:]):
		l=len(list(g))
		if k=='#':
			R[i,c:c+l]=0
		else:
			R[i,c:c+l]=l
		c+=l

r=0
for i in range(h):
	for j in range(w):
		r=max(r,C[i][j]+R[i][j]-1)
print(r)


### FIXED CODE ###

h,w=map(int,input().split())
M=[list(input()) for i in range(h)]
D=[[0]*w for i in range(h)]
U=[[0]*w for i in range(h)]
R=[[0]*w for i in range(h)]
L=[[0]*w for i in range(h)]

for i in range(h):
    c=0
    for j in range(w):
        if M[i][j]=='.':
            c+=1
            R[i][j]=c
        else:
            c=0
for i in range(h):
    c=0
    for j in range(w):
        if M[i][w-1-j]=='.':
            c+=1
            L[i][w-1-j]=c
        else:
            c=0
for j in range(w):
    c=0
    for i in range(h):
        if M[i][j]=='.':
            c+=1
            D[i][j]=c
        else:
            c=0
for j in range(w):
    c=0
    for i in range(h):
        if M[h-1-i][j]=='.':
            c+=1
            U[h-1-i][j]=c
        else:
            c=0
r=0
for i in range(h):
    for j in range(w):
        r=max(r,R[i][j]+L[i][j]+D[i][j]+U[i][j]-3)
print(r)
n, l = map(int, input().split())
s = soated([input() for i in range(n)])
print(*s, sep = "")

### FIXED CODE ###

n, l = map(int, input().split())
s = sorted([input() for i in range(n)])
print(*s, sep = "")
if n != 0:
    p = list(map(int, input().split()))
 
result = x
if n != 0:
    for i in range(0, 1000):
        if not (x - i) in p:
            print(x - i)
            break
        if not (x + i) in p:
            print(x + i)
            break
else:
    print(x)
    

### FIXED CODE ###

X,N= map(int,input().split())
p = list(map(int,input().split()))
for i in range(100):
  if X-i not in p:
    print(X-i)
    exit()
  if X+i not in p:
    print(X+i)
    exit()
S = list(input())
K = int(input())

if(len(set(S)) == 1):
    print(len(S) // 2 * K)
else:
    m = 0
    ans = 0
    if(S[0] == S[-1]):
        l = 0
        r = len(S) - 1
        while(S[l] == S[l+1]):
            l += 1
        while(S[-r] == S[-r]):
            r += 1
        m = l//2 + r//2 - (l+r)//2
        m *= K - 1
    
    for i in range(len(S)-1):
        if(S[i] == S[i+1]):
            ans += 1
            S[i+1] = "3"
    ans *= K
    ans -= m
    print(ans)





### FIXED CODE ###

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

if(len(set(S)) == 1):
    print(len(S) * K//2)
else:
    ans = 0
    cnt = 1
    a = []
    for i in range(len(S)-1):
        if(S[i] == S[i+1]):
            cnt += 1
        else:
            a.append(cnt)
            cnt = 1
    a.append(cnt)

    for i in a:
        ans += (i//2)*K

    if (S[0] == S[-1]):
        ans -= (a[0]//2 + a[-1]//2  - (a[0] + a[-1])//2)*(K-1)

    print(ans)