Harryxun/stf_run huggingface dataset:
from heapq import nlargest

n = int(input())
aaa = list(map(int, input().split()))
n2 = 1 << n
dp = [[0, a] for a in aaa]

for j in range(n):
    b = 1 << j
    for i in range(n2):
        if not i & b:
            dp[i | b] = nlargest(2, dp[i] + dp[i | b])

ans = []
tmp = 0
for a in dp[1:]:
    tmp = max(tmp, a)
    ans.append(tmp)
print(*ans)


### FIXED CODE ###

n = int(input())
aaa = list(map(int, input().split()))
n2 = 1 << n
dp = [[a, 0] for a in aaa]

for j in range(n):
    b = 1 << j
    for i in range(n2):
        if not i & b:
            dpi, dpk = dp[i], dp[i | b]
            if dpk[0] < dpi[0]:
                dpk[1] = max(dpk[0], dpi[1])
                dpk[0] = dpi[0]
            elif dpk[1] < dpi[0]:
                dpk[1] = dpi[0]

ans = []
tmp = 0
for a in dp[1:]:
    tmp = max(tmp, a[0] + a[1])
    ans.append(tmp)
print(*ans)
a = input()
b = input()
c = input()
r = 0
     
if a + b >= c:
  r = b + c
else:
  r = a + b

print(r)

### FIXED CODE ###

a, b, c = map(int,input().split())
r = 0
if c <= a + b + 1:
  r = b + c
else:
  r = a + 2 * b + 1
print(r)
import numpy as np
import math
[A,B] = input().split()
c = 0
if '.' in B:
    c = int(B.find('.'))
c = len(B)-c-1
B = B.replace(".","")
A = np.int64(A)
B = np.int64(B)
C = A*B
if c == 0 or C <=100:
    print(math.floor(C/int(10**c)))
else c == 1:
    print(str(C)[:-c])

### FIXED CODE ###

import numpy as np
import math
[A,B] = input().split()
# A = "1000000000000001"
# B = "9.09"
c = 0
if '.' in B:
    c = int(B.find('.'))
c = len(B)-c-1
B = B.replace(".","")
A = np.int64(A)
B = np.int64(B)
C = A*B
if c == 0 or C <=100:
    print(math.floor(C/int(10**c)))
elif c == 1:
    print(str(C)[:-1])
elif c == 2:
    print(str(C)[:-2])
# C = C/int(10**c)
# print(C)
# print(math.floor(C))
# print(9990000000000000)
x = int(raw_input())
y = int(raw_input())
print x*y

### FIXED CODE ###

l = map(int, raw_input().split())
print l[0] * l[1],
print l[0] *2 + l[1] * 2
import fractions

N=int(input())

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

M=[2]
while M[-1]<N:
    M.append(M[-1]*2)

tgt=sum(M)-M[0]
A=A+[A[-1]]*(M[-1]-len(A))
A=A[::-1]

for i in range(tgt-1):
    A.append(fractions.gcd(A[2*i],A[2*i+1]))

A=A[::-1]

print(A)
    

### FIXED CODE ###

# coding: utf-8
# Your code here!
def euclid(a,b):
    a,b=max(a,b),min(a,b)
    if a%b==0:
        return b
    else:
        a,b=b,a%b
        return euclid(a,b)

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

org_A=A[:]
#左から最大公約数作る右もね
A=A[::-1]
l=[A.pop(-1)]
while A:
    l.append(euclid(l[-1],A.pop(-1)))

A=org_A
r=[A.pop(-1)]
while A:
    r.append(euclid(r[-1],A.pop(-1)))
r=r[::-1]

ans=0
#print(l,r)
for i in range(N):
    temp=euclid(l[i-1] if i!=0 else r[i+1],r[i+1] if i!=N-1 else l[i-1])
    #print(l[i-1] if i!=0 else r[i+1],r[i+1] if i!=N-1 else l[i-1])
    ans=max(ans,temp)

print(ans)
num1=input().split()
num2=input().split()

num2.sort(reverse=True)
N=int(num1[0])
M==int(num1[1])
A=int(num2[int(num1[1])-1])

if A<N/M/4:
    print('Yes')
    else:
    print('No')

### FIXED CODE ###

n,m = map(int,input().split())
li = list(map(int,input().split()))
  
li.sort(reverse=True)
  
a=li[m-1]
b=sum(li)

if a>=b/4/m:
  print('Yes')
else:
  print('No')
from fractions import gcd
from functools import reduce
input()
def gcd(*numbers):
    return reduce(math.gcd, numbers)
print(gcd(*[int(i) for i in input().split()]))

### FIXED CODE ###

# import math
from functools import reduce
input()
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

def gcds(*numbers):
    return reduce(gcd, numbers)
print(gcds(*[int(i) for i in input().split()]))
print(input().replace("1", "")[0])

### FIXED CODE ###

s = input()
k = int(input())
rep = s.replace("1", "")
if len(rep) == 0:
  print("1")
else:
  if s.index(rep[0]) < k:
    print(rep[0])
  else:
    print("1")
N, K = map(int, input().split())
A = list(map(int, input().split()))
s = [0] * 200000
for i in range(N):
    s[i+1] = s[i] +A[i]

max_s = 0
for i in range(K):
    if max_s < s[i+K] - s[i]:
        max_s = s[i+K] - s[i]


print((max_s+K) / 2)

### FIXED CODE ###

N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
s = [0] * 1000000
for i in range(N):
    s[i+1] = s[i] + A[i]

max_s = 0
for i in range(N):
    if max_s < s[i+K] - s[i]:
        max_s = s[i+K] - s[i]


print((max_s+K) / 2)
X,Y=list(map(int,input().split()))

import sys
if (2*Y-X)%3!=0 or (2*X-Y)%3!=0:
  print(0)
  sys.exit()
  
x=(2*Y-X)//3
y=(2*X-Y)//3
#(x+y)Cxを求める
fac=[0 for i in range(x+y+1)]
inv=[0 for i in range(x+y+1)]
finv=[0 for i in range(x+y+1)]
#初期条件
p=1000000007
fac[0]=fac[1]=1
inv[1]=1
finv[1]=1
#テーブルの作成
for i in range(2,x+y+1):
  fac[i]=fac[i-1]*i%p
  #p=(p//a)*a+(p%a) a^(-1)=-(p//a)*(p%a)^(-1)
  inv[i]=(p-(p//i)*inv[p%i])%p
  finv[i]=finv[i-1]*inv[i]%p
#求める
print((fac[x+y]*finv[x]%p)*finv[y]%p)




### FIXED CODE ###

X,Y=list(map(int,input().split()))

import sys
if (2*Y-X)%3!=0 or (2*X-Y)%3!=0:
  print(0)
  sys.exit()
if (2*Y-X)<0 or (2*X-Y)<0:
  print(0)
  sys.exit()
x=(2*Y-X)//3
y=(2*X-Y)//3
#(x+y)Cxを求める
fac=[0 for i in range(x+y+1)]
inv=[0 for i in range(x+y+1)]
finv=[0 for i in range(x+y+1)]
#初期条件
p=1000000007
fac[0]=fac[1]=1
inv[1]=1
finv[0]=finv[1]=1
#テーブルの作成
for i in range(2,x+y+1):
  fac[i]=fac[i-1]*i%p
  #p=(p//a)*a+(p%a) a^(-1)=-(p//a)*(p%a)^(-1)
  inv[i]=(-(p//i)*inv[p%i])%p
  finv[i]=finv[i-1]*inv[i]%p
#求める

print((fac[x+y]*finv[x]%p)*finv[y]%p)
N = int(input())
K = (((8 * N + 1) ** (1/2) - 1) / 2)

def recursive(k):
    if k == 2:
        return [[1, 2], [1, 3], [2, 3]]
    else:
        before = recursive(k - 1)
        r = [_ for _ in range(1 + k * (k - 1) // 2, 1 + k * (k + 1) // 2)]
        return ([before[_] + [r[_]] for _  in range(len(r))] + [r])
if K.is_integer():
    print('Yes')
    K = int(K)
    [print(K, ' '.join(map(str, ary))) for ary in recursive(K)]
else:
    print('No')

### FIXED CODE ###

N = int(input())
K = (((8 * N + 1) ** (1/2) + 1) / 2)

def recursive(k):
    if k == 2:
        return [[1], [1]]
    else:
        before = recursive(k - 1)
        r = [_ for _ in range(1 + (k - 2) * (k - 1) // 2, 1 + k * (k - 1) // 2)]
        return ([before[_] + [r[_]] for _  in range(len(r))] + [r])

if K.is_integer():
    K = int(K)
    print('Yes')
    print(K)
    [print(K - 1, ' '.join(map(str, ary))) for ary in recursive(K)]
else:
    print('No')
from collectins import deque

### FIXED CODE ###

from collections import deque

def isPa(w,k,p):
    tr = 0
    c = 0
    d = deque(w)
    while(d):
        tmp = d.popleft()
        if(tmp > p):
            return False
        
        if( tr + tmp > p):
            tr = tmp
            c += 1
        else:
            tr += tmp
        if c+1>k:
            return False
    return True

def MaxInP(w,k,p):
    maxinp = 0
    tmp = 0
    d = deque(w)
    while(d):
        tmp += d.popleft();
        if(tmp > p):
            if(tmp > maxinp):
                maxinp = tmp
            tmp = 0
    return maxinp

n,k = [int(x) for x in input().split()]
w = deque()
for i in range(n):
    w.append(int(input()))
    
mean = int(sum(w)/k)
maxinp = MaxInP(w,k,mean)

if k == 1:
    print(mean)
else:
    minP = mean
    maxP = maxinp
    while(True):
        m = int ((minP + maxP)/2)
        if ( isPa(w,k,m) ):
            maxP = m
        else:
            minP = m
        if (minP+1 == maxP or minP == maxP):
            print(maxP)
            break
from math import pi

r = floot(input())
print("{:.6f} {:.6f}".format(r * r * pi, 2 * r * pi))

### FIXED CODE ###

from math import pi

r = float(input())
area = r**2 * pi
length = 2 * r * pi
print("{:.6f} {:.6f}".format(area, length))
import sys
n, m = map(int, input().split())
sc = [list(map(int, input().split())) for _ in range(m)]

ans = [-1] * n
for i in sc:
    s,c=sc[i]
    if (ans[s-1] == c) | (ans[s-1] == -1):
        ans[s-1] = c
    else:
        print(-1)
        sys.exit()

for i in range(n):
    if ans[i] == -1:
        if i == 0:
            ans[i] = 1
        else:
            ans[i] = 0

if n != 1:
    if ans[0] == 0:
        print(-1)
        sys.exit()

print(*ans, sep='')


### FIXED CODE ###

import sys
n, m = map(int, input().split())
sc = [list(map(int, input().split())) for _ in range(m)]

ans = [-1] * n
for i in sc:
    s, c = i
    if (ans[s-1] == c) | (ans[s-1] == -1):
        ans[s-1] = c
    else:
        print(-1)
        sys.exit()

for i in range(n):
    if ans[i] == -1:
        if (i == 0) & (n != 1):
            ans[i] = 1
        else:
            ans[i] = 0

if n != 1:
    if ans[0] == 0:
        print(-1)
        sys.exit()

print(*ans, sep='')
from collections import deque

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


def teleport(now_index):
    next_machi_index = portals[now_index] - 1
    return next_machi_index


current = first_count = 0
keiro = list()
for _ in range(K):
    if current in keiro:
        loop_index = keiro.index(current)
        loop_keiro = keiro[loop_index:]
        break
    keiro.append(current)
    current = teleport(current)

print(keiro[(K - first_count) % len(loop_keiro)] + 1)


### FIXED CODE ###

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

visitTowns = list()
visitTimes = [0 for _ in range(N + 1)]

curTown = 1
timeBackTo = 0

curTime = 0
while True:
    if visitTimes[curTown] > 0:
        timeBackTo = visitTimes[curTown]
        break

    visitTowns.append(curTown)
    visitTimes[curTown] = curTime

    # teleport
    curTown = portals[curTown]

    curTime += 1

nonLoopCount = timeBackTo
loopSpan = len(visitTowns) - nonLoopCount

if K <= nonLoopCount:
    print(visitTowns[K])
    exit()

rem = (K - nonLoopCount) % loopSpan
print(visitTowns[nonLoopCount + rem])
n = int(input())
an = list(map(int,input().split()))

anset = list(set(an))

andict = {}

for i in range(len(an)):
    if an[i] in andict:
        andict[an[i]] = andict[an[i]] + 1
    else:
        andict.update({an[i]:1})

counter = 0

for i ,j in andict.keys(), andict.values():
    if i == j :
        None
    elif i > j:
        counter = counter + j
    elif i < j:
        counter = counter + j - i
    
        
print(counter)

### FIXED CODE ###

n = int(input())
an = list(map(int,input().split()))

anset = list(set(an))

andict = {}

for i in range(len(an)):
    if an[i] in andict:
        andict[an[i]] = andict[an[i]] + 1
    else:
        andict.update({an[i]:1})

counter = 0

for i ,j in andict.items():
    if i == j :
        None
    elif i > j:
        counter = counter + j
    elif i < j:
        counter = counter + j - i
    
        
print(counter)
a = int(input())
b, c = map(int, input().split())
s = input()
print("{} {}".format(a+b+c, s))

### FIXED CODE ###

s=list(input())
print(s.count("1"))
x,y=map(int,input().split())
r=4*x
if r>=y y>=2*x and (r-y)%2==0:
  print('Yes')
else:
  print('No')


### FIXED CODE ###

x,y=map(int,input().split())
r=4*x
if r>=y and y>=2*x and (r-y)%2==0:
  print('Yes')
else:
  print('No')
i = 0
     
while 1:
   i += 1
   x = input()
   if x == 0:
      k = 1
   else:
      print "Case %d: %d" %(i, x)

### FIXED CODE ###

i = 0
     
while 1:
   i += 1
   x = input()
   if x == 0:
      break
   else:
      print "Case %d: %d" %(i, x)
n=int(input())
ans=1
for i in range(n):
  x=int(input())
  ans*=x

if ans<=10**18:
  print(ans)
else:
  print(-1)

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
x=1
A.sort()
if 0 in A:
  print(0)
  exit()

for i in range(n):
  x*=A[n-i-1]
  if x>10**18:
    print(-1)
    exit()
  else:
    continue

print(x)
n = int(input())
student = list(map(int,input().split()))
 
ans = [0] * n   #登校した順番を記録するためのリスト
 
for i in range(n):
    s = student[i]   #出席番号がiの人が来た時に、既にs人いました。
    ans[s-1] = i+1 　#なのでansリスト(来た順に対応させる)のs-1番目(リストの仕様)に出席番号iの人が配属されます。

print(*ans)

### FIXED CODE ###

n = int(input())
student = list(map(int,input().split()))
 
ans = [0] * n   #登校した順番を記録するためのリスト
 
for i in range(n):
    s = student[i]   #出席番号iの生徒が登校した順番をメモ
    ans[s-1] = i+1    #ansに出席番号を書き込む
 
print(*ans)
a,b = map(int, raw_input().split())
d = a / b
r = a % b
f = float(a) / float(b)
print " ".join(d, r, f)

### FIXED CODE ###

a,b = map(int, raw_input().split())
d = a / b
r = a % b
f = float(a) / float(b)
print " ".join([str(d), str(r), str('%.5f' % f)])
import sys

l = [map(int,l.split()) for line in sys.stdin]
n = l[0]
l = l[1]

print "%s %s %s" %(min(l),max(l),sum(l))

### FIXED CODE ###

import sys
 
l = [map(int,line.split()) for line in sys.stdin]
n = l[0]
l = l[1]
 
print "%s %s %s" %(min(l),max(l),sum(l))
an=int(input())
a=sorted(list(map(int,input().split())))
if n%3==0:
  d={}
  for ai in a:
    if ai not in d:
      d[ai]=a.count(ai)
  sa=list(set(a))
  if sa[0]^sa[1]==sa[2] and d[sa[0]]==d[sa[1]] and d[sa[0]]==d[sa[2]]:
    print('Yes')
    exit()
print('No')

### FIXED CODE ###

n=int(input())
a=sorted(list(map(int,input().split())))
if n%3==0:
  d={}
  for ai in a:
    if ai not in d:
      d[ai]=a.count(ai)
      if len(d)==4:
        break
  sa=list(set(a))
  if len(sa)==3 and sa[0]^sa[1]==sa[2] and d[sa[0]]==d[sa[1]] and d[sa[0]]==d[sa[2]]:
    print('Yes')
    exit()
  if len(sa)==2 and 0 in d and 2*d[0]==max(d[sa[0]],d[sa[1]]):
    print('Yes')
    exit()

if n == a.count(0):
  print('Yes')
  exit()

print('No')
a,b,c=input().split()
print(eval(abc))

### FIXED CODE ###

a,b,c=input().split()
print(eval(a+b+c))
from collections import deque, defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)

n = int(input())
edges = defaultdict(lambda : defaultdict(lambda: False))
for i in range(n-1):
    a, b = map(int, input().split())
    edges[a][b] = True
    edges[b][a] = True

nums = [deque() for _ in range(3)]
for i in range(1, n+1):
    nums[i%3].append(i)

color = [-1 for _ in range(n)]
cnts = [0 for _ in range(2)]
def coloring(num, pre_color):
    if pre_color:
        col = 0
    else:
        col = 1
    color[num-1] = col
    cnts[col] += 1
    for k in edges[num].keys():
        if color[k-1] == -1:
            coloring(k, col)

coloring(1, 1)

ans = [0 for _ in range(n)]
def solve(v):
    for i in range(n):
        if color[i] == v:
            ans[i] = nums[0].pop()
        else:
            for i in [1, 2, 0]:
                if len(nums[i]) > 0:
                    ans[i] = nums[i].pop()


if cnts[0] <= n // 3:
    solve(0)
elif cnts[1] <= n // 3:
    solve(1)
elif cnts[0] > n // 3 and cnts[1] > n // 3:
    for i in range(n):
        if color[i]:
            if len(nums[1]) > 0:
                ans[i] = nums[1].pop()
            else:
                ans[i] = nums[0].pop()
        else:
            if len(nums[2]) > 0:
                ans[i] = nums[2].pop()
            else:
                ans[i] = nums[0].pop()
else:
    print(-1)
    exit()

print(" ".join(list(map(str, ans))))

### FIXED CODE ###

from collections import deque, defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)

n = int(input())
edges = defaultdict(lambda : defaultdict(lambda: False))
for i in range(n-1):
    a, b = map(int, input().split())
    edges[a][b] = True
    edges[b][a] = True

nums = [deque() for _ in range(3)]
for i in range(1, n+1):
    nums[i%3].append(i)

color = [-1 for _ in range(n)]
cnts = [0 for _ in range(2)]
def coloring(num, pre_color):
    if pre_color:
        col = 0
    else:
        col = 1
    color[num-1] = col
    cnts[col] += 1
    for k in edges[num].keys():
        if color[k-1] == -1:
            coloring(k, col)

coloring(1, 1)

ans = [0 for _ in range(n)]
def solve(v):
    for i in range(n):
        if color[i] == v:
            ans[i] = nums[0].pop()
        else:
            for j in [1, 2, 0]:
                if len(nums[j]) > 0:
                    ans[i] = nums[j].pop()
                    break

if cnts[0] <= n // 3:
    # print("A")
    solve(0)
elif cnts[1] <= n // 3:
    # print("B")
    solve(1)
else:
    # print("C")
    for i in range(n):
        if color[i]:
            if len(nums[1]) > 0:
                ans[i] = nums[1].pop()
            else:
                ans[i] = nums[0].pop()
        else:
            if len(nums[2]) > 0:
                ans[i] = nums[2].pop()
            else:
                ans[i] = nums[0].pop()

print(" ".join(list(map(str, ans))))
x, n = map(int, input().split())
if n == 0:
    print(x)
else:
    p = list(map(int, input().split()))

    p.sort()
    y = 0

    for i in range(n):
        if p[i] <= x:
            y = i
            if i != n-1 and x < p[i+1]:
                break 

    i = 0
    while 1 == 1:
        if x - i != p[y - i]:
            print(x - i)
            break
        if x + i != p[y + i]:
            print(x + i)
            break
        i =+ 1

### FIXED CODE ###

x, n = map(int, input().split())
if n == 0:
    print(x)
else:
    p = list(map(int, input().split()))

    p.sort()
    y = 0

    for i in range(n):
        if p[i] <= x:
            y = i
            if i != n-1 and x < p[i+1]:
                break 

    i = 0
    while 1 == 1:
        if y - i < 0:
            print(p[0] - 1)
            break
        elif x - i != p[y - i]:
            print(x - i)
            break
        if n <= y + i:
            print(p[n - 1] + 1)
            break
        elif x + i != p[y + i]:
            print(x + i)
            break
        i = i + 1
N=int(input())
S=input()
X=int(S,2)

#Sのビット数
bitcount=0
for i in range(N):
  if S[i]=='1':
    bitcount+=1
bp=bitcount+1
bm=bitcount-1
    

fXp=X%bp
fXm=X%bm
    

def f(n):
  c=0
  x=1
  while x<=n:
    if n&x>0:
      c+=1
    x*=2
  return n%c

ls=[0 for i in range(bitcount+2)]  
ls2=[0 for i in range(bitcount+2)]
for i in range(1,bitcount+2):
  ls[i]=f(i)
  ls2[i]=ls2[ls[i]]+1

for i in range(N):
  if S[i]=='0':
    print(ls2[(fXp+2**(N-1-i))%bp]+1)
  else:
    if (X^(2**(N-1-i)))==0:
      print(0)
    else:
      print(ls2[(fXm-2**(N-1-i))%bm]+1)
  
      #print(ls2[(fXm-ls_bitm[N-1-i])%bm]+1)
  


### FIXED CODE ###

N=int(input())
S=input()

#Sのビット数
bitcount=0
for i in range(N):
  if S[i]=='1':
    bitcount+=1
bp=bitcount+1
bm=bitcount-1

lsp=[1 for i in range(N)]
for i in range(1,N):
  lsp[i]=(lsp[i-1]*2)%bp
lsp.reverse()
fXp=0
for i in range(N):
  if S[i]=='1':
    fXp=(fXp+lsp[i])%bp
    
if bm!=0:
  lsm=[1 for i in range(N)]
  for i in range(1,N):
    lsm[i]=(lsm[i-1]*2)%bm
  lsm.reverse()
  fXm=0
  for i in range(N):
    if S[i]=='1':
      fXm=(fXm+lsm[i])%bm


def f(n):
  c=0
  x=1
  while x<=n:
    if n&x>0:
      c+=1
    x*=2
  return n%c

ls=[0 for i in range(bitcount+2)]  
for i in range(1,bitcount+2):
  ls[i]=ls[f(i)]+1

for i in range(N):
  if S[i]=='0':
    print(ls[(fXp+lsp[i])%bp]+1)
  else:
    if bm==0:
      print(0)
    else:
      print(ls[(fXm-lsm[i])%bm]+1)
N, K = map(int, input().split())
*h, = map(int, input().split())
dp = [float("inf") for _ in range(N + 1)]
dp[0] = 0
for i in range(N):
	for j in range(1, min(K + 1, N - i + 1)):
		dp[i + j] = min(dp[i + j], dp[i] + abs(h[j] - h[i]))
print(dp[N])


### FIXED CODE ###

N, K = map(int, input().split())
*h, = map(int, input().split())
dp = [float("inf") for _ in range(N)]
dp[0] = 0
for i in range(N - 1):
	for j in range(1, min(K + 1, N - i)):
		dp[i + j] = min(dp[i + j], dp[i] + abs(h[i + j] - h[i]))
print(dp[N - 1])
# -*- coding: utf-8 -*-
S = str(input())
T,U = S[0],S[-1]
print(S[0]+len(S[1:-2])+S[-1])

### FIXED CODE ###

# -*- coding: utf-8 -*-
S = str(input())
T,U = S[0],S[-1]
print(S[0]+str(len(S[1:len(S)-1]))+S[-1])
from decimal import *
import re
def solve2(m, n):
    maxlen = 85
    #maxlen = 160
    PREC=200
    #PREC=300
    getcontext().prec = PREC
    x = Decimal(m) / Decimal(n)
    s = x.to_eng_string()
    if len(s) < PREC:
        return(s[2:],'')
    rep = 1
    while True:
        clip = min(int(PREC/rep),20)
        #r = r'(.{%d})\1{%d,}' % (rep, int(PREC/rep)-1)
        r = r'(.{%d})\1{%d,}' % (rep, clip)
                                         #ex. '(.{6})\\1{12,}'
        a=re.search(r, s)
        if a:
            break
        rep += 1
        if rep > maxlen:
            raise ValueError('This cannot happen.')

    u = s[2:a.start()+len(a.group(1))]
    v = (' '*PREC + '^'*len(a.group(1)))[-len(u):]
    return(u,v)

while True:
    try:
        m,n = map(int, input().strip().split())
        s,t = solve2(m, n)
        print(s)
        if t!='':
            print(t)
    except EOFError:
        break

### FIXED CODE ###

from decimal import *
import re
def solve2(m, n):
    maxlen = 80
    PREC=180
    getcontext().prec = PREC
    x = Decimal(m) / Decimal(n)
    s = x.to_eng_string()
    if len(s) < PREC:
        return(s[2:],'')
    rep = 1
    while True:
        r = r'(.{%d})\1{%d,}' % (rep, int(maxlen/rep))  #ex. '(.{6})\\1{13,}'
        a=re.search(r, s)
        if a:
            break
        rep += 1
        if rep > maxlen:
            raise ValueError('This cannot happen.rep=%d' % rep)

    u = s[2:a.start()+len(a.group(1))]
    v = (' '*PREC + '^'*len(a.group(1)))[-len(u):]
    return(u,v)

while True:
    try:
        m,n = map(int, input().strip().split())
        s,t = solve2(m, n)
        print(s)
        if t!='':
            print(t)
    except EOFError:
        break
N = int(input())
S = input()

d = 0
for k in range(2,N):
    sk = S[k]
    for j in range(k):
        sj = S[j]
        if sk != sj:
            for i in range(j):
                si = S[i]
                if (si != sj) & (si != sk):
                    if j-i != k-j:
                   
                        d += 1

print(d)




### FIXED CODE ###

a = str(input())

if "7" in a:
  print("Yes")
else:
  print("No")
costs = [2,5,5,4,5,6,3,7,6]

N, M = map(int, input().split())
A = list(map(int, input().split()))
neginf = -1 * 1e10
D = [neginf]*(N+1)

def dp(n_match):
    D[0] = 0
    for n in range(1,n_match+1):
        arr = [D[n-costs[a-1]] if n-costs[a-1]>=0 else neginf for a in A]
        D[n] = max(arr)+1

def main():
    dp(N)
    n = N
    ans = ''
    while n>0:
        for a in A:
            arr = [a for a in A if D[n-costs[a-1]]==D[n]-1]
        a = max(arr)
        ans += str(a)
        n -= costs[a-1]
    print(ans)

main()

### FIXED CODE ###

costs = [2,5,5,4,5,6,3,7,6]

N, M = map(int, input().split())
A = list(map(int, input().split()))
neginf = -1 * 1e20
D = [neginf]*(N+1)

def dp(n_match):
    D[0] = 0
    for n in range(1,n_match+1):
        arr = [D[n-costs[a-1]] if n-costs[a-1]>=0 else neginf for a in A]
        D[n] = max(arr)+1

def main():
    dp(N)
    n = N
    ans = ''
    while n>1:
        arr = [ a for a in A if  n-costs[a-1]>=0 and D[n-costs[a-1]]==D[n]-1 ]
        if len(arr)>0:
            a = max(arr)
            ans += str(a)
            n -= costs[a-1]
        else:
            break
    print(ans)

main()
S = input()
K = int(input())
d=[[0 for _ in range(100)] for _ in range(4)]
ans = [0,0,0,0]
l = len(S)
odd_diff = 0
even_diff = 0
if l == 1:
    ans = K // 2
    print(ans)
if l > 1:
    for i in range(4):
        s = S * (i + 1)
        l = len(s)
        for j in range(l-1):
            
            if j == 0 and s[j] == s[j+1]:
                ans[i] += 1
                d[i][0] = 1
            if j > 0 and s[j] == s[j+1] and d[i][j-1] == 0:
                ans[i] += 1
                d[i][j] = 1
    if K <= 4:
        print(ans[K-1])
    elif K > 4 and K % 2 == 0:
        even_diff = ans[3] - ans[1]
        print(ans[1]+(K/2)*even_diff)
    elif K > 4 and K % 2 == 1:
        odd_diff = ans[2] - ans[0]
        print(ans[0]+(K//2)*odd_diff)

### FIXED CODE ###

S = input()
K = int(input())
d=[[0 for _ in range(400)] for _ in range(4)]
ans = [0,0,0,0]
l = len(S)
odd_diff = 0
even_diff = 0
if l == 1:
    print(int(K//2))
if l > 1:
    for i in range(4):
        s = S * (i + 1)
        l = len(s)
        for j in range(l-1):
            
            if j == 0 and s[j] == s[j+1]:
                ans[i] += 1
                d[i][0] = 1
            if j > 0 and s[j] == s[j+1] and d[i][j-1] == 0:
                ans[i] += 1
                d[i][j] = 1
    if K <= 4:
        print(int(ans[K-1]))
    elif K > 4 and K % 2 == 0:
        even_diff = ans[3] - ans[1]
        print(int(ans[1]+(K/2-1)*even_diff))
    elif K > 4 and K % 2 == 1:
        odd_diff = ans[2] - ans[0]
        print(int(ans[0]+(K//2)*odd_diff))