Harryxun/stf_run huggingface dataset:
import math
import string
import collections
from collections import Counter


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
h, w = map(int, input().split())
tmp = [None]*h
for i in range(w):
    tmp[i] = input()
# print(tmp)
for i in range(h-1):
    for j in range(w-1):

        if tmp[i][j] == '#':
            if (tmp[i-1][j] == '#' and i-1 >= 0)or(tmp[i+1][j] == '#' and i+1 <= h-1) or(tmp[i][j-1] == '#' and j-1 >= 0)or(tmp[i][j+1] == '#' and j+i <= w-1):
                continue
            else:
                print('No')
                exit()
print('Yes')


### FIXED CODE ###

import math
import string
import collections
from collections import Counter
from collections import deque


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

H, W = map(int, input().split())
s = [None]*H
for i in range(H):
    s[i] = input()
    # print(s[i])
for i in range(H):
    for j in range(W):
        if s[i][j] == '#':
            #print(i, j)
            if (i != 0 and s[i-1][j] == '#') or(i != H-1 and s[i+1][j] == '#')or(j != 0 and s[i][j-1] == '#') or(j != W-1 and s[i][j+1] == '#'):
                continue
            else:
                print('No')
                exit()
print('Yes')
W, H, N = map(int, input().split())

right = W
left = 0
top = H
bottom = 0

for i in range(N):
    x, y, a = map(int, input().split())
    if a == 1 and left <= x:
        left = x
    elif a == 2 and right >= x:
        right = x
    elif a == 3 and bottom <= y:
        bottom = y
    elif a == 4 and top >= y:
        top = y

if (top-bottom)*(right-left) > 0 and (top-bottom)>0 and (rightt-left)>0:
    print((top-bottom)*(right-left))
else:
    print(0)


### FIXED CODE ###

W, H, N = map(int, input().split())

right = W
left = 0
top = H
bottom = 0

for i in range(N):
    x, y, a = map(int, input().split())
    if a == 1 and left <= x:
        left = x
    elif a == 2 and right >= x:
        right = x
    elif a == 3 and bottom <= y:
        bottom = y
    elif a == 4 and top >= y:
        top = y

if (top-bottom)*(right-left) > 0 and (top-bottom)>0 and (right-left)>0:
    print((top-bottom)*(right-left))
else:
    print(0)
import math
import itertools
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

n, k = map(int, input().split())
d = [0]*k
d[0] = n-k+1
for i in range(1, k):
    a = cmb(k-1, i)/i
    div = math.ceil(a)
    if k % (i+1) == 0:
        d[i] = cmb(n-k+1, i+1)
    elif (i+1) % k == 0:
        d[i] = cmb(n-k+1, i+1)*(div-1) + 1
    else:
        d[i] = cmb(n-k+1, i+1)*div


    #     s = math.factorial(n-k+1)//math.factorial(i+1)
for i in d:
    print(i % (10 ** 9 + 7))


### FIXED CODE ###

import math


def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


n, k = map(int, input().split())
mod = 10**9+7
for i in range(1, k+1):
    if n-k+1 >= i:
        print(comb(n-k+1, i)*comb(k-1, i-1) % mod)
    else:
        print(0)
N, K = map(int, input().split())
S = input()
S[K-1] = S[K-1].lower()
print(S)

### FIXED CODE ###

N, K = map(int, input().split())
S = input()
S = S[0:K-1] + S[K-1].lower() + S[K:]
print(S)
a, b, c = map(int,input().split())
if c-b <=0:
 print("delicious")
elif a+b=>c:
 print("safe")
else:
 print("dangerous")

### FIXED CODE ###

a, b, c = map(int,input().split())
if c-b <= 0:
 print("delicious")
elif a+b >= c:
 print("safe")
else:
 print("dangerous")
n, t = map(int, input().split())
l = [input().split() for i in range(n)]
l.sort()
exist = False

for i in l:
  if int(i[1]) < t:
    print(i[0])
    exist = True
    break
if !(exist):
  print("TLE")

### FIXED CODE ###

n, t = map(int, input().split())
l = [list(map(int, input().split())) for i in range(n)]
l.sort()
exist = False

for i in l:
  if int(i[1]) <= t:
    print(i[0])
    exist = True
    break
if not exist:
  print("TLE")
def m():
    n, x = map(int, input().split())
    a = list(map(int, input().split()))
    ans = 0
    for i in range(1, n-1, 2):
        if a[i+1] > a[i-1]:
            if a[i+1] + a[i] < x:
                continue
            ans += (a[i+1] + a[i]) -x
            if a[i+1] > x:
                a[i+1] = x
        else:
            if a[i-1] + a[i] < x:
                continue
            ans += (a[i-1] + a[i]) -x
    if len(a) % 2 == 0:
        if a[-1] + a[-2] < x:
            return ans
        ans += (a[-1] + a[-2]) -x
        return ans
    else:
        return ans

print(m())

### FIXED CODE ###

def m():
    s = str(input())
    cnt = 0
    tmp = s[0]
    for i in s:
        if tmp != i:
            tmp = i
            cnt += 1
    return cnt
    pass

print(m())
from collections import deque

d = deque()
N=int(input())
A=[]
for i in range(N):
    a=int(input())
    A.append(a)
A=sorted(A)
A2=A.copy()
#61823
#351914
#419153
B=deque()
#最初に大きい方
B.append(A.pop(-1))
while len(A)>0:
    if len(A)>0:
        B.appendleft(A.pop(0))
    if len(A)>0:
        B.append(A.pop(0))
    if len(A)>0:
        B.appendleft(A.pop(-1))
    if len(A)>0:
        B.append(A.pop(-1))
B=list(B)
C=deque()
#最初に小さい方
C.append(A2.pop(0))
while len(A2)>0:
    if len(A2)>0:
        C.appendleft(A2.pop(-1))
    if len(A2)>0:
        C.append(A2.pop(-1))
    if len(A2)>0:
        C.appendleft(A2.pop(0))
    if len(A2)>0:
        C.append(A2.pop(0))
C=list(C)
countb=0
countc=0
for i in range(1,N):
    countb+=abs(B[i]-B[i-1])
    countc+=abs(C[i]-C[i-1])
print(max(countb, countc))


### FIXED CODE ###

from collections import deque

d = deque()
N=int(input())
A=[]
for i in range(N):
    a=int(input())
    A.append(a)
A=sorted(A)
A2=A.copy()
#61823
#351914
#419153
B=deque()
#最初に大きい方
B.append(A.pop(-1))
while len(A)>0:
    if len(A)>0:
        B.appendleft(A.pop(0))
    if len(A)>0:
        B.append(A.pop(0))
    if len(A)>0:
        B.appendleft(A.pop(-1))
    if len(A)>0:
        B.append(A.pop(-1))
B=list(B)
C=deque()
#最初に小さい方
C.append(A2.pop(0))
while len(A2)>0:
    if len(A2)>0:
        C.appendleft(A2.pop(-1))
    if len(A2)>0:
        C.append(A2.pop(-1))
    if len(A2)>0:
        C.appendleft(A2.pop(0))
    if len(A2)>0:
        C.append(A2.pop(0))
C=list(C)
countb=0
countc=0
for i in range(1,N):
    countb+=abs(B[i]-B[i-1])
    countc+=abs(C[i]-C[i-1])
print(max(countb, countc))
n,k=map(int,input().split())
x=list(map(int,input().split()))
x.append(0)
x.sort()
x_0=x.index(0)

if x_0 == 0:
    print(x[k])
elif x_0==n:
    print(x[-k])
else:
    r = min(n-x_0-1, k)
    l = min(x_0, k)
    ans1=float("inf")
    ans2=float("inf")
    #スタートで正に移動
    for i in range(1,r):
        s = 2*x[x_0 + i] - x[x_0 - (k-i)]
        ans1=min(ans1, s)
    for i in range(1,l):
        s = -2*x[x_0 - i] + x[x_0 + (k-i)]
        ans2=min(ans2, s)
    print(min(ans1, ans2))

### FIXED CODE ###

n,k=map(int,input().split())
x=list(map(int,input().split()))
x.append(0)
x.sort()
x_0=x.index(0)

if x_0 == 0:
    print(x[k])
elif x_0==n:
    print(-x[-k-1])
else:
    r = min(n-x_0, k)
    l = min(x_0, k)
    ans1=float("inf")
    ans2=float("inf")
    #スタートで正に移動
    for i in range(1,r+1):
        if  k-i <= l:
            s = 2*x[x_0 + i] - x[x_0 - (k-i)]
            ans1=min(ans1, s)
    #スタートで負に移動
    for i in range(1,l+1):
        if k-i <= r:
            s = -2*x[x_0 - i] + x[x_0 + (k-i)]
            ans2=min(ans2, s)
    print(min(ans1, ans2))
a = int(input())
x = list(map(int,input().split()))
t = [range(1,a+1)]
A = []
B = []
for i in range(1,a+1):
    A.append(30000*i)
    B.append(30000*(a-i+1)+tpx[i-1]])
print(*A)
print(*B)

### FIXED CODE ###

a = int(input())
x = list(map(int,input().split()))
t = range(1,a+1)
A = []
B = []
for i in range(1,a+1):
    A.append(30000*i)
    B.append(30000*(a-i+1))
for i ,d in enumerate(x):
    A[d-1] -= a-i
print(*A)
print(*B)
#%%
import bisect

#%%
a,b,q = map(int, input().split())
INF = 10**18
shrines = [-INF] + [int(input() for _ in range(a))] + [INF]
temples = [-INF] + [int(input() for _ in range(b))] + [INF]

for _ in range(q):

    start = int(input())

    # スタート位置より右にある神社のうち、もっともスタート位置に近いもの
    shrine_east = shrines[bisect.bisect_right(shrines, start)]
    # スタート位置より右にある寺のうち、もっともスタート位置に近いもの
    temple_east = temples[bisect.bisect_right(temples, start)]

    # スタート位置より左にある神社のうち、もっともスタート位置に近いもの
    shrine_west = shrines[bisect.bisect_right(shrines, start) - 1]
    # スタート位置より左にある寺のうち、もっともスタート位置に近いもの
    temple_west = temples[bisect.bisect_right(temples, start) - 1]

    ans = INF

    for shrine in [shrine_east, shrine_west]:
        for temple in [temple_east,temple_west]:
            cur = min(abs(shrine-start), abs(temple-start)) + abs(shrine-temple)
            ans = min(ans,cur)

    print(ans)



#%%
arr = [4,8,12,16,20]

#%%
bisect.bisect_left(arr,12)

#%%
bisect.bisect_right(arr,12)

#%%


### FIXED CODE ###

#%%
import bisect

#%%
a,b,q = map(int, input().split())
INF = 10**18
shrines = [-INF] + [int(input()) for _ in range(a)] + [INF]
temples = [-INF] + [int(input()) for _ in range(b)] + [INF]

for _ in range(q):

    start = int(input())

    # スタート位置より右にある神社のうち、もっともスタート位置に近いもの
    shrine_east = shrines[bisect.bisect_right(shrines, start)]
    # スタート位置より右にある寺のうち、もっともスタート位置に近いもの
    temple_east = temples[bisect.bisect_right(temples, start)]

    # スタート位置より左にある神社のうち、もっともスタート位置に近いもの
    shrine_west = shrines[bisect.bisect_right(shrines, start) - 1]
    # スタート位置より左にある寺のうち、もっともスタート位置に近いもの
    temple_west = temples[bisect.bisect_right(temples, start) - 1]

    ans = INF

    for shrine in [shrine_east, shrine_west]:
        for temple in [temple_east,temple_west]:
            cur = min(abs(shrine-start), abs(temple-start)) + abs(shrine-temple)
            ans = min(ans,cur)

    print(ans)
import sys
input_number = int(raw_input())

if __name__ == '__main__':
    print(str(input_number ** 3))



### FIXED CODE ###

import sys
input_number = int(input())
if __name__ == '__main__':
    print(str(input_number ** 3))
n,q = map(int,input().spliot())
ki = [0]*(n+1)
for i in range(n-1):
    a,b = map(int,input().split())
    ki[b] = a

c = [0]*(n+1)
for i in range(q):
    p,x = map(int,input().split())
    c[p] += x
for i in range(1,n+1):
    c[i] += c[ki[i]]
print("".join(map(str,c[1:])))

### FIXED CODE ###

n,q=list(map(int,input().split()))
GR=[[] for _ in range(n)]
for i in range(n-1):
  a,b=list(map(int,input().split()))
  GR[a-1].append(b)
  GR[b-1].append(a)
 
ans=[0 for _ in range(n)]
for i in range(q):
  p,x=list(map(int,input().split()))
  ans[p-1] += x
  
gr=[1]
parent=[0 for _ in range(n)]
while gr:
  po=gr.pop()
  for no in GR[po-1]:
    if no == parent[po-1]:
      continue
    gr.append(no)
    parent[no-1]=po
    ans[no-1] += ans[po-1]
      
print(' '.join(map(str,ans)))
n, c = list(map(int, input().split()))
x, v = [], []
for i in range(n):
    x_, v_ = list(map(int, input().split()))
    x.append(x_)
    v.append(v_)
sushi1 = list((sum(v[:i+1]) - x[i]) for i in range(n))
sushi2 = list((sum(v[n-i:]) - (c - x[n-i])) for i in range(1, n+1))
max1, max2 = [0], [0]
for i in range(n):
    max1.append(max(sushi1[i] - x[i], max1[i]))
    max2.append(max(sushi2[i] - (c - x[n-i-1]), max2[i]))
def ans1(i):
    if i < 0:
        return 0
    elif i == 0:
        return max2[n]
    ans = max2[n-i] + sushi1[i-1]
    return max(ans, ans1(i-1))
def ans2(i):
    if i < 0:
        return 0
    elif i == 0:
        return max1[n]
    ans = max1[n-i] + sushi2[i-1]
    return max(ans, ans2(i-1))
print(max(ans1(n), ans2(n)))

### FIXED CODE ###

import numpy as np
n, c = list(map(int, input().split()))
xv = list(list(map(int, input().split())) for i in range(n))
sushi1, max1, sushi2, max2 = [0], [0], [0], [0]
sum1, sum2 = 0, 0
for x, v in xv:
    sum1 += v
    sushi1.append(max(sum1 - x, sushi1[-1]))
    max1.append(max(sum1 - 2*x, max1[-1]))
for x, v in xv[::-1]:
    sum2 += v
    sushi2.append(max(sum2 - (c-x), sushi2[-1]))
    max2.append(max(sum2 - 2*(c-x), max2[-1]))
ans1 = max(np.array(sushi1) + np.array(max2[::-1]))
ans2 = max(np.array(sushi2) + np.array(max1[::-1]))
print(max(0, ans1, ans2))
N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[0]*(N-1)
d=[[] for _ in range(N)] # 隣接リスト
e=[ set() for _ in range(N)] #その頂点につながる辺に存在する色のリスト
maxi=0
for i in range(N-1):
    a[i],b[i] = map(int,input().split())
    d[a[i]-1].append(b[i]-1)
    d[b[i]-1].append(a[i]-1)
    
for j in d:
    maxi=max(maxi,len(j))  #最大の色数が確定する
pos=set([i+1 for i in range(maxi)])

for i in range(N-1):
    tmp= pos- e[a[i]-1] -e[b[i]-1]
    col=tmp.pop()
    c[i]=col
    e[a[i]-1].add(col)
    e[b[i]-1].add(col)
   
print(maxi)
for color in c:
    print(color)


### FIXED CODE ###

from collections import deque

N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[set() for _ in range(N)] # 使用している色
d=[set() for _ in range(N)] # 隣接リスト
e=[ False for _ in range(N)] #訪問ずみかどうか
f=[0]*N  #答え
for i in range(N-1):
    a[i],b[i] = map(int,input().split())
    d[a[i]-1].add(b[i]-1)
    d[b[i]-1].add(a[i]-1)

maxi=max([len(d[i]) for i in range(N-1)])
print(maxi)
#print("c:",c)
#print("d",d)
#print("e",e)

#x=0としてBFSする

v=deque([0])
e[0]=True
color=1

while v:
  p = v.popleft()
  for q in d[p]:
    if e[q]==False:
      while color in c[p]:
        color +=1
        if color>maxi:
          color=1
      c[p].add(color)
      c[q].add(color)
      f[q]=color
      e[q]=True
      v.append(q)
      
for i in range(N-1):
  print( f[b[i]-1])
n,k=map(int,input().split())
A=sorted(list(map(int,input().split())) , key=abs , reverse=1)
import bisect as bi
# print(A)
# import numpy as np
# G=np.prod(A[:k])
def seki(A,mod=10**9+7):
    now=1
    for i in A:
        i=abs(i)
        if i>0 : now*=i
        # if i<0 : now*=i
        if i==0 :return 0
        if now>0 : now%=mod
    return now

CH=A[:k]
NO=A[k:]
# G=seki(A[:k])

mod=10**9+7
# if G>=0 : print(G%mod) ; exit()
if sum([A[i]>0 for i in range(n)])==0 and k%2==1:
  print((-seki(A[n-k:]))%mod) ;exit()
if n==k and len(A[bi.bisect_left(A,-1):])%2==1 :
    print((-seki(A))%mod) ;exit()
if sum([i<0 for i in A[:k]])%2==0 :
    print(seki(A[:k])%mod) ; exit()
if 0 in CH:
    print(0);exit()
  
# done=0 ; done2=0
# # ch=-73267983297 ; ch2=-9263498381621
# 
# for i in range(k-1,-1,-1):
#     if A[i]<0 and done==0:
#         for j in range(i+1,n):
#             if A[j]>=0: 
#                 # ch=G*A[j]//A[i]
#                 x1=A[j] ; y1=A[i]
#                 done=1
#                 break
#     if A[i]>0 and done2==0:
#         for j in range(i+1,n):
#             if A[j]<=0: 
#                 # ch2=G*A[j]//A[i]
#                 x2=A[j] ; y2=A[i]
#                 done2=1
#                 break
# #     if done==1 and done2==1 : break
# 
# G=seki(A[:k])
# G=-G
# if done and done2 :
#     if x1 * y2 > x2 * y1 :
#         print((G*x1//y1)%mod)
#     else:
#         print((G*x2//y2)%mod)
# elif done==1:
#     print((G*x1//y1)%mod)
# elif done2==1:
#     print((G*x2//y2)%mod)
        

done=0 ; done2=0
muri,muri2=0,0

# x1,x2,y1,y2=0,0,0,0
if sum([i<0 for i in NO])==n-k : #NO全部-
    muri=1
if sum([i<0 for i in CH])==k : #CH全部-
    if sum([i<0 for i in NO])==0: #-を入れられない
        muri2=1
if muri==0:
    y1= [i for i in CH if i<0][-1]
    x1= [i for i in NO if i>0][0]
    done=1
if muri2==0:
    y2= [i for i in CH if i>0][-1]
    x2= [i for i in NO if i<0][0]
    done2=1

if done and done2:
    if x1 * y2 > x2 * y1 :
        print((-seki(CH)*x1//y1)%mod)
    else:
        print((-seki(CH)*x2//y2)%mod)
elif muri:
    print((-seki(CH)*x2//y2)%mod)
else:
    print((-seki(CH)*x1//y1)%mod)


### FIXED CODE ###

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

if K%2==1 and A[-1]<0:
    for i in range(K):
        ans=ans*A[N-(i+1)]%mod
    print(ans)
    exit()

l=0
r=N-1
if K%2==1:
    ans=ans*A[r]
    r-=1

for _ in range(K//2):
    ml=A[l]*A[l+1]
    mr=A[r]*A[r-1]
    if ml>mr:
        ans=ans*ml%mod
        l+=2
    else:
        ans=ans*mr%mod
        r-=2

print(ans)
K = int(input())
A = list(map(int,input().split()))[::-1] + [1]

# 切り上げ
def ceil(a, b):
    return -(-a//b)

# [a, b) に含まれるcの倍数のうち最小,最大のものを返す
def query(a, b, c):
    l = c * ceil(a, c)
    r = c * (ceil(b, c) - 1)
    if l <= r:
        return True, l, r
    else:
        return False, -1, -1

cand = [2,2]
for i in range(K):
    if len(cand) == 0:
        print(-1)
        exit()
    s, m = cand
    cand = []
    fs, ls, rs = query(s, s+A[i], A[i+1])
    fm, lm, rm = query(m, s+A[i], A[i+1])
    if fs:
        cand.append(ls)
    if fm:
        cand.append(rm)

if len(cand) == 0:
    print(-1)
else:
    print(cand[0], cand[-1])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

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

def ceil(a, b):
    return -(-a // b)

def floor(a, b):
    return a // b

def L(i):
    if i == K:
        return 2
    return ceil(L(i+1), A[i]) * A[i]

def R(i):
    if i == K:
        return 2
    return floor(R(i+1), A[i]) * A[i] + A[i] - 1

L0 = L(0); R0 = R(0)
if L0 <= R0:
    print(L0, R0)
else:
    print(-1)
import numpy as np

N=int(input())
A=np.array(list(map(int, input().split())))

sign = np.arange(1,N+1)
sign = sign + A
temp = np.arange(N)+1-A
count = 0
for i in range(1,N):
  count += (sign[:i]==temp[:i]).sum()

print(count)

### FIXED CODE ###

from collections import defaultdict

N = int(input())
*A,=map(int,input().split())

'''
方針:
- 各A_i,(i<h)ごとにf(h,j)=A_h+A_j-|h-j|の値がf(i,j)に比べてどれだけ変化するかを計算し、
リストに格納(①)
- 各要素A_k,(j<k)ごとにf(i,k)=A_i+A_k-|i-k|の値がf(i,j)に比べてどれだけ変化するかを
計算し、カウントをとる(②)
- 再度ループを回して①と②を照合し、値が一致する組数をansに加算
'''

ans=0
diff_list=[] #①照合用の差分リスト
count=defaultdict(int) #②各要素がどれだけはみ出ているかのカウント
#前処理として、最初のループで①と②を作成
for i in range(1,N):
  if i == A[0]+A[i]:
    ans += 1
  d1 = A[i]-A[0]
  d2 = i
  diff_list.append(d1+d2)
  
  count[A[0]+A[i]-i] += 1

for i in range(N-1):
  count[A[0]+A[i+1]-(i+1)] -= 1 #その要素自身を忘れずに引く
  d = diff_list[i]
  ans += count[-d]
  
print(ans)
# Author: cr4zjh0bp
# Created: Sat Mar 14 19:55:57 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni = lambda: int(ns())
nin = lambda y: [ni() for _ in range(y)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda y: [na() for _ in range(y)]
nf = lambda: float(ns())
nfn = lambda y: [nf() for _ in range(y)]
nfa = lambda: list(map(float, stdin.readline().split()))
nfan = lambda y: [nfa() for _ in range(y)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda y: [ns() for _ in range(y)]
ncl = lambda y: [list(ns()) for _ in range(y)]
nas = lambda: stdin.readline().split()

s = ns()
k = ni()

c = []
cnt = 1
for i in range(len(s) - 1):
    if s[i] == s[i + 1]:
        cnt += 1
    elif cnt > 1:
        c.append(cnt)
        cnt = 1
if cnt > 1:
    c.append(cnt)

itv = 0
if len(s) > 1 and len(c) > 0:
    if s[0] == s[1] and s[-1] == s[-2]:
        itv = sum([x // 2 for x in c[1:-1]])
    elif s[0] == s[1] and s[-1] != s[-2]:
        itv = sum([x // 2 for x in c[1:]])
    elif s[0] != s[1] and s[-1] == s[-2]:
        itv = sum([x // 2 for x in c[:-1]])
    else:
        itv = sum([x // 2 for x in c[:]])

if len(c) == 1 and c[0] == len(s):
    # 全ての要素が連続している
    print(len(s) * k // 2)
elif s[0] != s[-1]:
    # 両端が連続していない
    print(itv * k)
else:
    ans = 0
    # 左端を操作する必要がある
    if s[0] == s[1]:
        ans += c[0] // 2
    # 右端を操作する必要がある
    if s[-1] == s[-2]:
        ans += c[-1] // 2

    # 左端、右端以外
    ans += itv * k

    if len(c) == 0:
        # 左端と右端がどちらも連続していない
        ans += k - 1
    else:
        if s[0] == s[1] and s[-1] == s[-2]:
            # 両端に連続した要素がある
            ans += (c[-1] + c[0]) // 2 * (k - 1)
        elif s[0] == s[1] and s[-1] != s[-2]:
            # 右端に連続した要素がない
            ans += (c[1] + 1) // 2 * (k - 1)
        else:
            # 左端に連続した要素がない
            ans += (c[-1] + 1) // 2 * (k - 1)

    print(ans)

### FIXED CODE ###

# Author: cr4zjh0bp
# Created: Sat Mar 14 20:41:10 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni = lambda: int(ns())
nin = lambda y: [ni() for _ in range(y)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda y: [na() for _ in range(y)]
nf = lambda: float(ns())
nfn = lambda y: [nf() for _ in range(y)]
nfa = lambda: list(map(float, stdin.readline().split()))
nfan = lambda y: [nfa() for _ in range(y)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda y: [ns() for _ in range(y)]
ncl = lambda y: [list(ns()) for _ in range(y)]
nas = lambda: stdin.readline().split()

from collections import Counter

s = ns()
n = len(s)
s = s + "$"
k = ni()

c = []
cnt = 1
for i in range(len(s) - 1):
    if s[i] == s[i + 1]:
        cnt += 1
    elif cnt > 1:
        c.append(cnt)
        cnt = 1

if (len(c) == 1 and c[0] == n) or n == 1:
    print(n * k // 2)
elif s[0] != s[-2]:
    print(sum([x // 2 for x in c[:]]) * k)
else:
    a, b = 1, 1
    if s[0] == s[1]:
        a = c[0]
    if s[-2] == s[-3]:
        b = c[-1]
    print(sum([x // 2 for x in c[:]]) * k - (a // 2 + b // 2 - (a + b) // 2) * (k - 1))
N,T = map(int,input().split)
t = input().split()
int(amount) =0

if t[0] <= T:
    amount+=t[0]
else:
    amount+=T
    
for index in range(N-1):
    t_sub = int(t[index+1])-int(t[index])
    if t_sub <= T:
        amount+=t_sub
    else:
        amount+=T

        
amount +=T

print(amount)

### FIXED CODE ###

if __name__ == '__main__':
    N, T = map(int, input().split())
    ts = list(map(int, input().split()))
    
    
amount =0


    
for index in range(N-1):
    t_sub = ts[index+1]-ts[index]
    amount+=min(t_sub,T)

        
amount +=T

print(amount)
n=int(input())
s=list(input() for i in range(n))
m=int(input())
t=list(input() for j in range(m))
l=list(set(n))
ans=(max(0,s.count(l[k])-t.count(l[k])) for k in range(len(l)))

### FIXED CODE ###

n=int(input())
s=list(input() for i in range(n))
m=int(input())
t=list(input() for j in range(m))
l=list(set(s))
ans=max(0,max(s.count(l[k])-t.count(l[k]) for k in range(len(l))))
print(ans)
A,B = map(int,input().split())
if A-2B>=0:
  print(A-2B)
else:
  print(0)
  

### FIXED CODE ###

A,B = map(int,input().split())
if A-2*B>=0:
  print(A-2*B)
else:
  print(0)
def main():
  A,B = map(int,input.split())
  
  B*=100
  res = (A*B)//100
  print(res)
  return
 
main()

### FIXED CODE ###

A,B = input().split()
A = int(A)
B = round(float(B)*100)

res = (A*B)//100
print(res)
import sys

num = list(map(int, input().split()))
print(num)

if sum % 2 == 0:
    print("Even")
else:
    print("Odd")


### FIXED CODE ###

import sys
 
num = list(map(int, input().split()))

ans = num[0] * num[1]
 
if ans % 2 == 0:
    print("Even")
else:
    print("Odd")