Harryxun/stf_run huggingface dataset:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

# 遅延評価で加えてあげるだけ

N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

value = [0] * (N+1)
for p,x in PX:
    value[p] += x

def dfs(v,parent,add):
    value[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,value[v])

dfs(1,0,0)

answer = ' '.join(map(str,value[1:]))
print(answer)
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

value = [0] * (N+1)
for p,x in PX:
    value[p] += x

def dfs(v,parent,add):
    value[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,value[v])

dfs(1,0,0)

answer = ' '.join(map(str,value[1:]))
print(answer)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
 
# 遅延評価で加えてあげるだけ
 
N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]
 
graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)
 
value = [0] * (N+1)
for p,x in PX:
    value[p] += x
 
def dfs(v,parent,add):
    value[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,value[v])
 
dfs(1,0,0)
 
answer = ' '.join(map(str,value[1:]))
print(answer)
s = input()
s = s[:4] + '  ' s[4:]
print(s)

### FIXED CODE ###

s = input()
s = s[:4] + ' ' + s[4:]
print(s)
a,b=input().split()
if a='H' and b='H':
    print('H')
elif a='H' and b='D':
    print('D')
elif a='D' and b='H':
    print('D')
else:
    print('H')

### FIXED CODE ###

a,b=input().split()
if a=='H' and b=='H':
    print('H')
elif a=='H' and b=='D':
    print('D')
elif a=='D' and b=='H':
    print('D')
else:
    print('H')
from scipy.special import comb

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


k_max = int(comb(N - 1, 2))

if k_max < K:
    print(-1)
else:
    E = [[v, N] for v in range(1, N)]

    add_need = k_max - K

    count = 0
    for i in range(1, N):
        for k in range(i + 1, N):
            E.append([i, k])
            count += 1
    #         print(count)
            if count == add_need:
                break
        if count == add_need:
            break

    print(len(E))
    for e in E:
        print(e[0], e[1])



### FIXED CODE ###

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 = list(map(int, input().split()))
k_max = int(cmb(N - 1, 2))

if N == 2:
    if K == 0:
        print(1)
        print(1, 2)
    else:
        print(-1)
elif k_max < K:
    print(-1)
else:
    E = [[v, N] for v in range(1, N)]

    add_need = k_max - K
    if add_need >= 1:
        count = 0
        for i in range(1, N):
            for k in range(i + 1, N):
                E.append([i, k])
                count += 1
        #         print(count)
                if count == add_need:
                    break
            if count == add_need:
                break

    print(len(E))
    for e in E:
        print(e[0], e[1])
import numpy as np
def main():
    ttt = []
    n = int(input())
    e = [list(map(int, input().split())) for _ in range(n)]
    #e = [[int(i) for i in input().split()] for i in range(int(input()))]
    #n = 3
    #e = [[21,-11],[81234,94124,52141]]
    for i in range(n):
        t = e[0][0] - e[1][i]*0.006
        tt = abs(e[0][1] - t)
        ttt.append(tt)
    ttt = np.array(ttt)
    print(np.argmin(ttt)+1)
main()

### FIXED CODE ###

import numpy as np
def main():
    ttt = []
    n = int(input())
    N, M = map(int, input().split())
    e = list(map(int, input().split()))
    #e = [[int(i) for i in input().split()] for i in range(int(input()))]
    #n = 3
    #e = [[21,-11],[81234,94124,52141
    for j in range(n):
        t = N - e[j]*0.006
        tt = abs(M - t)
        ttt.append(tt)
    ttt = np.array(ttt)
    print(np.argmin(ttt)+1)
main()
INF = 100000000000
import math
N = int(input())
lists = list(map(int, input().split()))

min_gcd = INF

for a in range(len(lists) - 1):
  min_gcd = min(min_gcd, math.gcd(lists[a], lists[a+1]))

print(min_gcd)

### FIXED CODE ###

import fractions
INF = 100000000000

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

min_gcd = INF

for a in range(len(lists) - 1):
  min_gcd = min(min_gcd, fractions.gcd(lists[a], lists[a+1]))

print(min_gcd)
import sys
lines = sys.stdin.readlines()

S = str(input())

#10**nのmod計算
A = []
p =1
for i in range(len(S)):
  A.append(p)
  p = p*10%2019

#左からi文字以降の数字列のmod計算
X = []
a = 0
for i in range(len(S)):
  a = (a + int(S[len(S)-i-1])*A[i]) %2019
  X.append(a)
X.sort()
flag =1
n = 0

#modが同じになる組み合わせ、またはもともとmodが0になる数字列の個数の総和計算
for i in range(len(X)-1):
  if X[i]==0:
    n +=1
  if X[i]==X[i+1]:
    flag += 1
  else:
    n += flag*(flag-1)//2
    flag = 1
print(n)

### FIXED CODE ###

import sys

lines = sys.stdin.readlines()

x = lines[0].split(' ')
S =int(x[0])
W =int(x[1])

if S > W:
    ans = 'safe'
else:
    ans = 'unsafe'

print(ans)
import operator
import functools
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = [0]*(k+2)
seki = functools.partial(functools.reduce, operator.mul)
ans[0] = seki(a[:k])
for i in range(n-k):
    #print(i,ans)
    ans[i+1] = ans[i] * a[i+k]
    ans[i+1] //= a[i]
for i in range(n-k):
    if ans[i+1] > ans[i]:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
for i in range(n-k):
    if a[i+k] > a[i]:
        print("Yes")
    else:
        print("No")
S = input()
N = len(S)

def isp(s):
  n = len(s)
  for i in range(n // 2 - 1):
    if s[i] != s[n - 1 - i]:
      return False
  return True

if isp(S) and isp(S[0:(N - 1) / 3]):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

S = input()
N = len(S)
 
def isp(s):
  n = len(s)
  for i in range(n // 2):
    if s[i] != s[n - 1 - i]:
      return False
  return True
 
if isp(S) and isp(S[0:(N - 1) // 2]):
  print("Yes")
else:
  print("No")
import numpy as np
n,d=map(int, input().split())
x = [np.array(list(map(int, input().split()))) for i in range(n)]
a=0
for i in range(len(x)):
    for j in range(i+1, len(x)):
        if float.is_integer(np.linalg.norm(x[i] - x[j])):
            a += 1
print(a)

### FIXED CODE ###

n, d = map(int, input().split())
x = [list(map(int, input().split())) for i in range(n)]
a = 0
for i in range(len(x)):
    for j in range(i+1, len(x)):
        t = 0
        for k in range(d):
            t += (x[i][k]-x[j][k])**2
        if float.is_integer(t**0.5):
            a += 1
print(a)
from scipy.sparse.csgraph import csgraph_from_dense, bellman_ford
from scipy.sparse.csgraph._shortest_path import NegativeCycleError

n, m = map(int, input().split())
GRAPH = [[0]*n for _ in range(n)]

for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    GRAPH[a][b] = -c

try:
    sp = bellman_ford(csgraph_from_dense(GRAPH), indices=0)
except NegativeCycleError:
    print('inf')
else:
    print(-int(sp[-1]))


### FIXED CODE ###

n, m = map(int, input().split())
edges = []
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    edges.append((a, b, -c))

init_v = 0
INF = float('inf')
dist = [INF]*n
dist[init_v] = 0
for i in range(n):
    for v, v2, c in edges:
        if dist[v2] <= dist[v]+c:
            continue
        dist[v2] = dist[v]+c

negative = [0]*n
for i in range(n):
    for v, v2, c in edges:
        if dist[v2] <= dist[v]+c:
            continue
        dist[v2] = dist[v]+c
        negative[v2] = 1

if negative[-1]:
    print('inf')
else:
    print(-dist[-1])
import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write('\n'.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
from decimal import Decimal
from fractions import Fraction
#sys.setrecursionlimit(100000)
INF = float('inf')
mod = int(1e9)+7


n,k=mdata()
p=mdata()
c=mdata()
ans=-INF
for i in range(n):
    c1=[]
    a=i
    while True:
        a=p[a]-1
        c1.append(c[a])
        if a==i:
            break
    m=-INF
    m1=0
    for j in range(min(k,len(c1))):
        m1+=c1[j]
        ans=max(m1,ans)
    if m1>0:
        t=k//len(c1)
        m1=max(0,m1*(t-1))
        ind=max(0,len(c)*(t-1))
        ans=max(ans,m1)
        for i in range(ind,k):
            m1+=c1[i]
            ans=max(ans,m1)
out(ans)



### FIXED CODE ###

import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write('\n'.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
from decimal import Decimal
from fractions import Fraction
#sys.setrecursionlimit(100000)
INF = float('inf')
mod = int(1e9)+7


n,k=mdata()
p=mdata()
c=mdata()
ans=-INF
for i in range(n):
    c1=[]
    a=i
    while True:
        a=p[a]-1
        c1.append(c[a])
        if a==i:
            break
    m1=0
    for j in range(min(k,len(c1))):
        m1+=c1[j]
        ans=max(m1,ans)
    if m1>0:
        t=k//len(c1)
        m1=max(0,m1*(t-1))
        ind=max(0,len(c1)*(t-1))
        ans=max(ans,m1)
        for i in range(ind,k):
            m1+=c1[i%len(c1)]
            ans=max(ans,m1)
out(ans)
n,x=map(int,input().split())
m=2*n-1
if x==1 or x==m:
    print("No")
    exit()
ll=list(range(1,2*n))
if x!=2:
    l=[x-1,x,x+1,x-2]
    ll.remove(x-1)
    ll.remove(x)
    ll.remove(x+1)
    ll.remove(x-2)
else:
    l=[x+1,x,x-1,x+2]
    ll.remove(x-1)
    ll.remove(x)
    ll.remove(x+1)
    ll.remove(x+2)

ans=[]
k=0
for i in range(len(ll)+1):
    if i==n-2:
        ans+=l
        k=-1
    else:
        ans.append(ll[i+k])

print("Yes")
for i in ans:
    print(i)



### FIXED CODE ###

n,x=map(int,input().split())
m=2*n-1
if x==1 or x==m:
    print("No")
    exit()
if n==2:
    print("Yes")
    for i in [1,2,3]:
        print(i)
    exit()
ll=list(range(1,2*n))
if x!=2:
    l=[x-1,x,x+1,x-2]
    ll.remove(x-1)
    ll.remove(x)
    ll.remove(x+1)
    ll.remove(x-2)
else:
    l=[x+1,x,x-1,x+2]
    ll.remove(x-1)
    ll.remove(x)
    ll.remove(x+1)
    ll.remove(x+2)

ans=[]
for i in range(len(ll)):
    if i==n-2:
        ans+=l
    ans.append(ll[i])
if len(ll)==n-2:
    ans+=l
print("Yes")
for i in ans:
    print(i)
s = int(input(""))

if s >= 0 and s < 86400:
    h = s / 3600
    m = (s % 3600) / 60
    s = ((s % 3600) % 60) % 60

print("{0:d}:{1:d}:{2:d}".format(h, m, s))

### FIXED CODE ###

second = int(input(""))

if second >= 0 and second < 86400:
    h = int(second / 3600)
    m = int((second % 3600) / 60)
    s = int(((second % 3600) % 60) % 60)

print("{0}:{1}:{2}".format(h, m, s))
print([1, 3, 3, 8, 3, 6, 9, 17, 4, 20, 7, 15, 10, 10, 18, 18, 5, 13, 21, 21, 8, 8, 16, 16, 11, 24, 11, 112, 19, 19, 19, 107, 6, 27, 14, 14, 22, 22, 22, 35, 9, 110, 9, 30, 17, 17, 17, 105, 12, 25, 25, 25, 12, 12, 113, 113, 20, 33, 20, 33, 20, 20, 108, 108, 7, 28, 28, 28, 15, 15, 15, 103, 23, 116, 23, 15, 23, 23, 36, 36, 10, 23, 111, 111, 10, 10, 31, 31, 18, 31, 18, 93, 18, 18, 106, 106, 13, 119, 26, 26][int(input())]+1)

### FIXED CODE ###

from collections import Counter
def collatz(n):
    if n%2:
        return n*3 + 1
    else:
        return n//2
    
i = int(input())
dic = dict()
dic[i] = 1
cur = i
for n in range(1,10000):
    cur = collatz(cur)
    if cur in dic:
        print(n+1)
        break
    else:
        dic[cur] = 1
a,b,c,d=map(int,input().split())
if a==b:
  print("Bad")
  elif b==c:
    print("Bad")
    elif c==d:
      print("Bad")
      else:
        print("Good")

### FIXED CODE ###

s=input()
if s[0]==s[1] or s[1]==s[2] or s[2]==s[3]:
  print("Bad")
else:
  print("Good")
x = input().split()
pointdict = {}
y = []
for i in x[0]:
    pointdict[i] = x[1]

for i in x[2]:
    ans = input()
    y.append(ans)

for i in y:
    for e in x[0]:
        if e != i:
            pointdict[e] -= 1

for p in pointdict:
    if pointdict[p] is not 0:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

x = input().split()
plist = [int(x[1]) for i in range(int(x[0]))]
y = []
l = 0
while l < int(x[2]):
    ans = input()
    y.append(int(ans))
    l += 1

for i in y:
    plist[i-1] += 1

for p in plist:
    if p - int(x[2]) > 0:
        print("Yes")
    else:
        print("No")
X,t = map(int,input().split())

if X >= t:
    print(X-t)
elsel:
    print(0)

### FIXED CODE ###

X,t = map(int,input().split())

if X >= t:
    print(X-t)
else:
    print(0)
N = int(input())
if n%2 == 0:
  print(N)
else:
  print(N*2)

### FIXED CODE ###

N = int(input())

if N%2 == 0:
	print(N)
else:
	print(N*2)
return x*x*x

### FIXED CODE ###

x = input()
ans = x**3
print ans
H, W, K = map(int, input().split())

WW = [0]*(W+1)
WW[0] = 1
WW[1] = 1
for i in range(2, W+1):
    WW[i] = WW[i-1] + WW[i-2]
DP = [[0]*W for i in range(H+1)]
DP[0][0] = 1
mod = 10**9+7
for i in range(1, H+1):
    for j in range(W):
        if j == 0:
            DP[i][j] = DP[i-1][j]*WW[W-1] + DP[i-1][j+1]*WW[W-2]
        elif j == W-1:
            DP[i][j] = DP[i-1][j]*WW[W-1] + DP[i-1][j-1]*WW[W-2]
        else:
            DP[i][j] = DP[i-1][j]*WW[j]*WW[W-1-j]+DP[i-1][j-1] * \
                WW[j-1]*WW[W-1-j]+DP[i-1][j+1]*WW[j]*WW[W-2-j]

        DP[i][j] %= mod
# print(DP, WW)
print(DP[-1][K-1])


### FIXED CODE ###

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

WW = [0]*(W+1)
WW[0] = 1
WW[1] = 1
for i in range(2, W+1):
    WW[i] = WW[i-1] + WW[i-2]
DP = [[0]*W for i in range(H+1)]
DP[0][0] = 1
mod = 10**9+7
for i in range(1, H+1):
    for j in range(W):
        if j == 0:
            DP[i][j] = DP[i-1][j]*WW[W-1]
            if W > 1:
                DP[i][j] += DP[i-1][j+1]*WW[W-2]
        elif j == W-1:
            DP[i][j] = DP[i-1][j]*WW[W-1]
            if W > 1:
                DP[i][j] += DP[i-1][j-1]*WW[W-2]
        else:
            DP[i][j] = DP[i-1][j]*WW[j]*WW[W-1-j]+DP[i-1][j-1] * \
                WW[j-1]*WW[W-1-j]+DP[i-1][j+1]*WW[j]*WW[W-2-j]

        DP[i][j] %= mod
# print(DP, WW)
print(DP[-1][K-1])
import sys
sys.setrecursionlimit(2000000000)


N = int(input())
T = [0 for i in range(N)]
for t in range(N):
    T[t] = int(input())


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


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


def solve(listT):
    listlen = len(listT)
    ans = -1
    while True:
        ans = lcm(listT[listlen - 2], listT[listlen - 1])
        listT.pop(listlen - 1)
        listT.pop(listlen - 2)
        listT.append(ans)
        listlen = len(listT)
        if(listlen == 1):
            break
    return ans

ans = solve(T)
print(ans)


### FIXED CODE ###

N = int(input())
result = 1

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


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


for i in range(0, N):
    num = int(input())
    result = lcm(result, num)
print(int(result))
N, K = map(int, input().split())
h = [int(input()) for i in range(N)].sort()
print(min(h[i+K-1] - h[i] for i in range(N-K+1)))


### FIXED CODE ###

N, K = map(int, input().split())
h = sorted([int(input()) for i in range(N)])
print(min(h[i+K-1] - h[i] for i in range(N-K+1)))
import sys
while True:
    a,b=map(int,stdin.readline().split())
    if a==0 and b==0:
        break
    if a<b:print(a,b)
    else:print(b,a)

### FIXED CODE ###

import sys
while True:
    a,b=map(int,sys.stdin.readline().split())
    if a==0 and b==0:
        break
    if a<b:print(a,b)
    else:print(b,a)
N = int(input())
nums = input().split()
mul = int(nums[0])
for i in nums[1:]:
    if str(0) in mul:
        mul = 0
        break
    if len(str(mul)) > 19:
        mul = -1
        break
    mul *= int(i)
print(mul)

### FIXED CODE ###

N = int(input())
nums = input().split()
mul = int(nums[0])
if str(0) in nums:
    mul = 0
else:
    for i in nums[1:]:
        mul *= int(i)
        if len(str(mul)) >= 19 and str(mul) != "1000000000000000000":
            mul = -1
            break
print(mul)
def main():
    n = 10**18
    a = 10**18
    b = 10**18
    n, a, b = map(int, input().split())

    if (b-a) % 2 == 1:
        t = min(a-1, n-b)
        if a-1 == t:
            a = 1
            b = b-t
            print(t + 1 + ((b-1)-a)//2)
        else:
            a = a + t
            b = n
            print(t + 1 ((b-1)-a)//2)

    else:
        print((b-a)//2)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = 10**18
    a = 10**18
    b = 10**18
    n, a, b = map(int, input().split())

    if (b - a) % 2 == 1:
        print((b-a)//2 + (b-a) % 2 + min(a-1, n-b))
    else:
        print((b - a) // 2)


if __name__ == '__main__':
    main()
n = input()
print(' ',end='')
print(*[i for in range(1,1+n) if i%3==0 or'3' in str(i)])


### FIXED CODE ###

n = int(input())
print(" ",end="")
print(*[i for i in range(1,1+n) if i%3==0 or'3' in str(i)])
n, w = map(int, input().split())
l = [ list(map(int, input().split())) for _ in range(n) ]
dp = [ [0]*(w+1) for _ in range(n+1) ]
for i in range(1, n+1):
  for j in range(w+1):
    if j < l[i-1][0]:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = max(dp[i-1][j-l[i-1][0]] + l[i-1][1], dp[i-1][j])
print(dp[n][w])


### FIXED CODE ###

n, W = map(int, input().split())
wv = [ list(map(int, input().split())) for _ in range(n) ]
dp = [ [float("inf")]*(10**5+1) for _ in range(n+1) ]
dp[0][0] = 0
for i in range(n):
  w, v = wv[i]
  for j in range(10**5+1):
    if j < v:
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = min(dp[i][j], dp[i][j-v]+w)
ans = 0
for j in range(10**5+1):
  if dp[n][j] <= W:
    ans = j
print(ans)
import sys
from copy import deepcopy
from collections import defaultdict
readline=sys.stdin.readline
read=sys.stdin.read

def main():
    n=int(readline())
    a=[list(map(int,l.split())) for l in read().splitlines()]
    cost=deepcopy(a)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j])
    s=0
    for i in range(n):
        for j in range(i+1,n):
            if cost[i][j]<a[i][j]:
                print(-1)
                return None
            detour=min([cost[i][k]+cost[k][j] for k in range(n) if k!=i and k!=j])
            if detour>cost[i][j]:
                s+=a[i][j]
    print(s)

if __name__=='__main__':
    main()


### FIXED CODE ###

import sys
from copy import deepcopy
import numpy as np
readline=sys.stdin.readline
read=sys.stdin.read

def main():
    n=int(readline())
    a=np.array([list(map(int,l.split())) for l in read().splitlines()])
    cost=deepcopy(a)
    for k in range(n):
        arr=np.stack([cost,[cost[k]]+np.transpose([cost[k]])])
        cost=np.amin(arr,axis=0)
    cost2=deepcopy(a)
    f=np.sum(cost<a)
    if f:
        print(-1)
        return
    filt=np.sum([([cost[k]]+np.transpose([cost[k]]))==cost for k in range(n)],axis=0)==2
    print(np.sum(a[filt])//2)

if __name__=='__main__':
    main()
MOD=10**9+7
n,m=map(int,input().split())
A=[1 for i in range(n)]
A[1]=2
for i in range(m):
  A[int(input())-1]=0
if A[0]==0:
  A[1]=1


for i in range(2,n):
  if A[i]!=0:
    A[i]=(A[i-1]+A[i-2])
    A[i]%=MOD
    
    
print(A)

### FIXED CODE ###

MOD=10**9+7
n,m=map(int,input().split())
A=[1 for i in range(n)]
if n!=1:
  A[1]=2
  for i in range(m):
    A[int(input())-1]=0
  
  if A[0]==0 and A[1]!=0:
    A[1]=1



  for i in range(2,n):
    if A[i]!=0:
      A[i]=(A[i-1]+A[i-2])
      A[i]%=MOD

    
  print(A[n-1])
  
else:print(1)
N,X = map(int, input().split())
print(N)
print(X)

def para(a,b):
    if a > b:
        return 2*b + para(b,a-b)
    if a < b:
        return 2*a + para(b-a,a)
    if a == b:
        return a
print(N+para(X,N-X))

### FIXED CODE ###

N,X = map(int,input().split(" "))
 
Y,X = sorted([N - X,X])
 
s = 0
while Y:
    s += (X//Y)*Y*3
    Y,X = [X%Y,Y]
 
print(s)
n = int(input())
l = [*map(int, input().split())]
cnt = 0

for i in range(1, len(l)-1):
    sub = sorted([l[i-1], l[i], l[i+1]])
    
    if sub[1] == l[i]:
        cnt += 1

print(cnt)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
cnt = 0

for i in range(1, len(l)-1):
    sub = sorted([l[i-1], l[i], l[i+1]])
    
    if sub[1] == l[i]:
        cnt += 1

print(cnt)
import numpy as np

n = int(input())
L = [int(i) for i in input().split()]
LL = [0 for i in range(pow(10,5)+1)]
LLL = np.ones(pow(10,5)+1, dtype = "uint64")
 
for i in range(n):
  LL[L[i]] += 1
  
out = 1
for i in range(len(LL)-1):
  LLL[i+1] = pow(i+1, LL[i+1])

out = int(np.prod(LLL))
if L[0] != 0 or LL[0] != 1:
  out = 0
print(out % 998244353)

### FIXED CODE ###

n = int(input())
L = [int(i) for i in input().split()]
LL = [0 for i in range(pow(10,5)+1)]
 
for i in range(n):
  LL[L[i]] += 1
  
MOD = 998244353
out = 1
maximum = max(L)
for i in range(maximum):
  out = (out * pow(LL[i], LL[i+1], MOD)) % MOD
 
if L[0] != 0 or LL[0] != 1:
  out = 0

for i in range(maximum):
  if L[i+1] == 0:
    out = 0
  
print(out)
import sys
string = input()
K = int(input())

if len(set(string)) == 1:
    print((K * len(string)) // 2)
    sys.exit()


f = string[0]
l = string[-1]
if f == l:
    first = 1
    for i in range(1, len(string)):
        if string[i] == f:
            first += 1
        else:
            break
    last = 1
    for i in range(len(string) - 2, 0, -1):
        if string[i] == l:
            last += 1
        else:
            break
ans = 0
final = 0
if (first + last) % 2 == 0 and first % 2 and last % 2:
    final = K - 1

string = string + '_'

count = 1
for n in range(1, len(string)):
    if string[n - 1] == string[n]:
        count += 1
    elif string[n - 1] != string[n] or n == len(string) - 1:
        if count >= 2:
            ans += (count // 2)
            #print(f'n: {n}')
            #print(count)
            #print(ans)
        count = 1
print(ans * K + final)

### FIXED CODE ###

import sys
S = input()
K = int(input())

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

if S[-1] == S[0]:
    letter = S[0]
    i = 1
    left_count = 1
    while letter == S[i]:
        left_count += 1
        i += 1
    right_count = 1
    i = len(S) - 2
    while letter == S[i]:
        right_count += 1
        i -= 1

    if left_count % 2 == 1 and right_count % 2 == 1:
        ans = K - 1
    else:
        ans = 0

else:
    ans = 0
tmp_count = 1
tmp_ans = 0
for s in range(1, len(S)):
    tmp = S[s]
    if tmp == S[s - 1]:
        tmp_count += 1
        if s == len(S) - 1:
            tmp_ans += tmp_count // 2
    else:
        tmp_ans += tmp_count // 2
        tmp_count = 1
print(tmp_ans * K + ans)