Harryxun/stf_run huggingface dataset:
def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a
def lcm(a,b):
    return a*b//gcd(a,b)
n,m=map(int,input().split())
s=list(input())
t=list(input())
L=lcm(n,m)
text=["0"]*L
judge=True
for i in range(n):
    text[i*(L//n)]=s[i]
for j in range(m):
    if text[j*(L//m)]!="0":
        if text[j*(L//m)]!=t[j]:
            judge=False
print(L) if judge else print(-1)
#print(len(text))


### FIXED CODE ###

def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a
n,m=map(int,input().split())
s=list(input())
t=list(input())
g=gcd(n,m)
a=n//g
b=m//g
judge=True
for i in range(g):
    if s[a*i]!=t[b*i]:
        judge=False
        break
print(g*a*b) if judge else print(-1)
#print(len(text))
ar = []
br = []
cr = []
mn = 10
for i in range(5):
    l = input()
    if int(l) % 10 == 0:
        ar.append(int(l))
    else:
        br.append(int(l))
        if mn > int(l) % 10:
            mn = int(l) % 10
for r in br:
    if str(r)[-1] == str(mn) and len(cr) == 0:
        cr.append(r)
    else:
        r += 10 - (r % 10)
        ar.append(r)
print(sum(ar) + cr[0])

### FIXED CODE ###

ar = []
br = []
cr = []
mn = 10
for i in range(5):
    l = input()
    if int(l) % 10 == 0:
        ar.append(int(l))
    else:
        br.append(int(l))
        if mn > int(l) % 10:
            mn = int(l) % 10
for r in br:
    if str(r)[-1] == str(mn) and len(cr) == 0:
        cr.append(r)
    else:
        r += 10 - (r % 10)
        ar.append(r)
if len(cr) == 1:
    print(sum(ar) + cr[0])
else:
    print(sum(ar))
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    s = input()
    ans = ""
    k = I()
    for i,si in enumerate(s):
        if si == "a":
            ans += si
            continue
        j = (ord("a")-ord(si))%26
        if j <= k:
            k -= j
            ans += "a"
        else:
            ans += si
    k %= 26
    print(ans[:-1]+chr(ord(ans[-1])+k))
    return

#Solve
if __name__ == "__main__":
    solve()


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    s = input()
    ans = []
    k = I()
    for i,si in enumerate(s):
        if si == "a":
            ans.append(si)
            continue
        j = (ord("a")-ord(si))%26
        if j <= k:
            k -= j
            ans.append("a")
        else:
            ans.append(si)
    k %= 26
    ans[-1] = chr(ord(ans[-1])+k)
    print(*ans,sep="")
    return

#Solve
if __name__ == "__main__":
    solve()
from itertools import permutations 
inf=10**9
n, m, r1 = map(int, input().split())
r=list(map(int, input().split()))
abc=[list(map(int, input().split())) for _ in range(m)]
d=[[inf]*n for i in range(n)]
for ai, bi, ci in abc:
    d[ai-1][bi-1]=ci
    d[bi-1][ai-1]=ci
for k in range(n):
    for i in range(n-1):
        for j in range(i, n):
            dk=d[i][k]+d[k][j]
            if d[i][j]>dk:
                d[j][i]=dk
                d[i][j]=dk
permutations(r)
ans=inf
for pi in permutations(r):
    res=0
    for i in range(r1-1):
        res+=d[pi[i]-1][pi[I+1]-1]
    if ans>res:
        ans=res
print(ans)

### FIXED CODE ###

from itertools import permutations
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
E = [list(map(int, input().split())) for _ in range(M)]
INF = 10 ** 9
d = [[INF for j in range(N)] for i in range(N)]
for i, j, c in E:
    d[i - 1][j - 1] = c
    d[j - 1][i - 1] = c
for k in range(N):
    for i in range(N - 1):
        for j in range(i, N):
            dk = d[i][k] + d[k][j]
            if d[i][j] > dk:
                d[i][j] = dk
                d[j][i] = dk
ans = 10 ** 9
for ri in permutations(r):
    x = 0
    for i in range(R - 1):
        x += d[ri[i] - 1][ri[i + 1] - 1]
    if ans > x:
        ans = x
print(ans)
import itertools

N = int(input())

number = [7, 5, 3]

ans = 0
for i in range(10):
    for conv in itertools.product(number, repeat=i+1):
        
        tmp = 0
        for j in range(len(conv)):
            tmp += conv[j] * 10 ** (len(conv) - j - 1)
            
        
        if ((3 in conv) and (5 in conv) and (7 in conv)) and tmp =< N:
            ans += 1
            
        
print(ans)

### FIXED CODE ###

import itertools

N = int(input())
nums = [3, 5, 7]
res = 0
for i in range(10):
  for balls in itertools.product(nums, repeat=i):
    num = ''
    if 3 in balls and 5 in balls and 7 in balls:
      for j in range(i):
        num += str(balls[j])
      if int(num) > N:
        break
      res += 1

print(res)
X, Y, Z, K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
AB = []
ans = []
for a in A:
    for b in B:
        AB.append(a + b)
AB.sort(reverse=True)
AB = AB[:min(3001,X*Y*Z+1)]
for c in C:
    for ab in AB:
        ans.append(c + ab)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])


### FIXED CODE ###

import sys
X, Y, Z, K = map(int, input().split())
A = list(map(int, sys.stdin.readline().split()))
B = list(map(int, sys.stdin.readline().split()))
C = list(map(int, sys.stdin.readline().split()))
A.sort(reverse = True)
B.sort(reverse = True)
C.sort(reverse = True)
AB = []
ans = []
for a in A:
    for b in B:
        AB.append(a + b)
AB.sort(reverse=True)
AB = AB[:min(3001, X*Y*Z+1)]
for c in C:
    for ab in AB:
        ans.append(c + ab)
ans.sort(reverse=True)
for i in range(K):
    print(ans[i])
def move_one_coine(target_i, target_j):
    while grids[target_j][target_i] < 2:
        for j in range(H):
            for i in range(W):
                if grids[j][i] >= 3:
                    grids[j][i] -= 1
                    grids[target_j][target_i] += 1
                    append_steps_to_answer(target_j, target_i, j, i)
        if j == H - 1 and i == W - 1:
            return


def append_steps_to_answer(j1, i1, j2, i2):
    prv_i = i1
    for i in range(i1 + 1, i2 + 1):
        ans.append([j1, prv_i, j2, i])
        prv_i = i

    prv_j = j1
    for j in range(j1 + 1, j2 + 1):
        ans.append([prv_j, i1, j2, i2])
        prv_j = j


H, W = map(int, input().split())
grids = [list(map(int, input().split())) for _ in range(H)]
ans = []
for j in range(H):
    for i in range(W):
        if grids[j][i] in [0, 1]:
            move_one_coine(i, j)

girds_to_move = None
for j in range(H):
    for i in range(W):
        if grids[j][i] % 2 == 1:
            if girds_to_move is None:
                girds_to_move = [j, i]
            else:
                grids[girds_to_move[0]][girds_to_move[1]] += 1
                grids[j][i] -= 1
                append_steps_to_answer(*girds_to_move, j, i)


print(len(ans))
[print(*map(lambda x: x + 1, process)) for process in ans]

### FIXED CODE ###

H,W = map(int,input().split())
A = [[0 for _ in range(W+1)]]
sumA = 0
for _ in range(H):
  row = [0] + list(map(int,input().split())) 
  A.append(row)
  sumA = sum(row)



c_num = 0
pros = []
for j in range(1,H+1):
  for i in range(1,W):
    if A[j][i]%2==1:
      pros.append([j,i, j,i+1])
      c_num += 1
      A[j][i] -= 1
      A[j][i+1] += 1
 
for j in range(H,1,-1):
  if A[j][W]%2==1:
    pros.append([j,W,j-1,W])
    c_num += 1
    A[j][W] -= 1
    A[j-1][W] += 1

print(c_num)
[print(*pro) for pro in pros]
p = "A"

while True:
    try:
        s, t = raw_input().split(",")
    except EOFError as e:
        break
    if s == p:
        p = t
    elif t == p:
        p = s

print("%s" % (chA, ))

### FIXED CODE ###

p = {"A":True, "B":False, "C": False}

while True:
    try:
        s, t = raw_input().split(",")
    except EOFError as e:
        break
    p[s], p[t] = p[t], p[s]

for i in p:
    if p[i]:
        print("%s" % (i, ))
N, Q = map(int, input().split())
nodes = {}
for _ in range(N-1):
    a, b = input().split()
    if nodes.get(a) is None:
        nodes[a] = [b]
    else:
        nodes[a] += [b]


ptree_map = {}


def gen_subtree_nodes(node):
    res = [int(node)]
    for n in nodes.get(node, []):
        subtree_nodes = gen_subtree_nodes(n)
        ptree_map[n] = subtree_nodes
        res += subtree_nodes

    return res


ptree_map['1'] = gen_subtree_nodes('1')

node_cnts = [0] * (N+1)
for _ in range(Q):
    p, x_str = input().split()
    x = int(x_str)
    for n in ptree_map[p]:
        node_cnts[n] += x

print(*node_cnts[1:])


### FIXED CODE ###

N, Q = map(int, input().split())
nodes = [[] for _ in range(2*(10**5)+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    nodes[a] += [b]

PX = [0 for _ in range(2*(10**5)+1)]
for _ in range(Q):
    p, x = map(int, input().split())
    PX[p] += x


node_cnts = [0] * (2*(10**5)+1)

q = [(1, PX[1])]
while q:
    node, count = q.pop()
    node_cnts[node] = count
    for n in nodes[node]:
        subtree_nodes = q.append((n, count + PX[n]))


print(*node_cnts[1:N+1], sep=' ')
N=int(input())
a=N%10
if a==2,4,5,7,9:
  print('hon')
elif a==0,1,6,8:
  print('pon')
else:
  print('bon')

### FIXED CODE ###

N=int(input())
a=N%10
if a==3:
  print('bon')
elif a==0 or a==1 or a==6 or a==8:
  print('pon')
else:
  print('hon')
import math
 
N = int(input())
list = []
min = 0
for i in range(5):
	list.append(int(input()))
	if min > list[i] or i == 0:
      min = list[i]

print(math.ceil(N/min) + 4)

### FIXED CODE ###

import math

N = int(input())
list = []
min = 0
for i in range(5):
  list.append(int(input()))
  if min > list[i] or i == 0:
    min = list[i]

print(math.ceil(N/min) + 4)
n = int(input())
L = list(map(int, input().split()))


count = 0
for i in range(n):
        if min(L[i],L[i+2]) < L[i+1] < max(L[i], L[i+2]):
            count += 1
            if i+2 == n - 1:
                break
print(count)

### FIXED CODE ###

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


count = 0
for i in range(1,n-1):
    if min(L[i-1],L[i+1]) < L[i] < max(L[i-1], L[i+1]):
        count += 1
            
print(count)
def cost(list, t):
    if t <= 0:
        return 0
    elif t == 1:
        return abs(list[1] - list[0])
    else:
        return min(cost(list, t - 1) + abs(list[t] - list[t - 1]), cost(list, t - 2) + abs(list[t] - list[t - 2]))

n = int(input())
h = input().split(" ")
h = list(map(int, h))
print(cost(h, n - 1))

### FIXED CODE ###

def expand_result(result, h, t):
    if t <= 0:
        result.append(0)
    elif t == 1:
        result.append(abs(h[1] - h[0]))
    else:
        result.append(min(result[t - 1] + abs(h[t] - h[t - 1]), result[t - 2] + abs(h[t] - h[t - 2])))
    return result

n = int(input())
h = input().split(" ")
h = list(map(int, h))
result = []
for i in range(n):
    result = expand_result(result, h, i)
print(result[n - 1])
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, x: "List[int]", y: "List[int]"):
    acc = []
    for i in range(N):
        for j in range(i+1, N):
            dx = x[i] - x[j]
            dy = y[i] - y[j]
            c = gcd(dx, dy)
            acc.append((dx // c, dy // c))
    c = Counter(acc)
    v, (p, q) = max([(v, k) for k, v in c.items()])
    return max(N - v, 1)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]" 
    y = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    result = solve(N, x, y)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, x: "List[int]", y: "List[int]"):
    ds = []
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            dx = x[j] - x[i]
            dy = y[j] - y[i]
            ds.append((dx, dy))

    return 1 if N == 1 else (N - max(Counter(ds).values()))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]" 
    y = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    result = solve(N, x, y)
    print(result)

if __name__ == '__main__':
    main()
def data_input():
    D = int(input())
    C = tuple(map(int, input().split()))

    S = []
    for i in range(D):
        s = tuple(map(int, input().split()))
        S.append(s)

    return D, C, S


def score(D, C, S, T):
    """入力D, C, Sと出力Tからスコアを計算する関数"""

    last = [0] * 26  # 0で初期化されている

    def decrease(d, last):
        """d日めにiを開催した時の満足度の減少を返す関数"""
        res = 0
        for i in range(26):
            ith = C[i] * (d+1 - last[i])
            res -= ith
        return res

    V = []  # V[d]はd日めの満足度を表す
    for d, i in enumerate(T):
        if d == 0:
            v = 0
        last[i] = d + 1
        v += S[d][i] + decrease(d, last)
        # print(d, i, v, S[d][i], decrease(d, last), last)
        V.append(v)
    return V

T = []
for d in range(D):
    local_max = 0
    for i in range(26):
        if score(d, C, S, T+[i])[-1] >= local_max:
            max_i = i
            local_max = score(d, C, S, T+[i])[-1]
            # print(f'local_max at {d}-day is updated to {local_max}')
    T.append(max_i)

V = score(D, C, S, T)

for v in V:
    print(v)

### FIXED CODE ###

D = 365

for i in range(D):
  print(1)
for i in range(input()):
	x1, y1, x2, y2, x3, y3, x4, y4 = map(float, raw_input().split())
	if (x1 == x2 and x3 == x4) or (y1 == y2 and y3 == y4):
		print "YES"
		continue
	elif (y1-y2)/(x1-x2) == (y3-y4)/(x3-x4):
		print "YES"
		continue
	print "NO"

### FIXED CODE ###

for i in range(int(input())):
    x1, y1, x2, y2, x3, y3, x4, y4 = map(float, input().split())
    if abs((y1 - y2) * (x3 - x4) - (y3 - y4) * (x1 - x2)) < 1.e-10:
        print('YES')
    else:
        print('NO')
#100

A, B = map(int, input().rsrtip().split())
if A > 8 or B > 8:
    print("Yay")
else:
    print(":(")

### FIXED CODE ###

#100

A, B = map(int, input().rstrip().split())
if A > 8 or B > 8:
    print(":(")
else:
    print("Yay!")
A,B={int(x) for x in input().split(" ")}

ans=A+B

printf("error" if ans >=10 else ans)

### FIXED CODE ###

A, B = [int(x) for x in input().split(" ")]

ans = A + B

print("error" if ans >= 10 else ans)
X = int(input())

p = 2
res = 0
for b in B:
    p = 2
    cp = p
    while True:
        tmp = b ** p
        if tmp > X:
            break
        else:
            res = max(res,tmp)
            if b == 1: break
            cp = p
            p += 1

### FIXED CODE ###

def function(X):
    B = list(range(31, 0, -1))
    res = 0
    for b in B:
        p = 2
        cp = p
        while True:
            tmp = b ** p
            if tmp > X:
                break
            else:
                res = max(res,tmp)
                if b == 1: break
                cp = p
                p += 1
    return res

X = int(input())
print(function(X))
def main():
    INF = 10 ** 9 + 10

    D = int(input())
    *C, = map(int, input().split())
    # C[type]
    # sum(ci*(d-last(d,i) for ci in C)だけ下がる
    S = [[int(x) for x in input().split()] for _ in range(D)]
    # S[day][type]:=happiness

    last = [-1] * 26

    def diff(d, t):
        ret = S[d][t]
        ret -= sum(ci * (d - last[i]) for i, ci in enumerate(C) if i != t)
        return ret

    T = []
    score = 0
    for d in range(D):
        delta = -INF
        take_t = -1
        for t_ in range(26):
            if delta < (buf := diff(d, t_)):
                delta = buf
                take_t = t_

        last[take_t] = d
        score += buf
        T.append(take_t)
    print(*T, sep='\n')
    # print(score)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    INF = 10 ** 9 + 10

    D = int(input())
    *C, = map(int, input().split())
    # C[type]
    # sum(ci*(d-last(d,i) for ci in C)だけ下がる
    S = [[int(x) for x in input().split()] for _ in range(D)]
    # S[day][type]:=happiness

    last = [-1] * 26

    def diff(d, t):
        ret = S[d][t]
        ret -= sum(ci * (d - last[i]) for i, ci in enumerate(C) if i != t)
        return ret

    T = []
    score = 0
    for d in range(D):
        delta = -INF
        take_t = -1
        for t_ in range(26):
            buf = diff(d, t_)
            if delta < buf:
                delta = buf
                take_t = t_

        last[take_t] = d
        score += buf
        T.append(take_t + 1)
    print(*T, sep='\n')
    # print(score)


if __name__ == '__main__':
    main()
# D
def touhi(a,r,n):
    return a*(pow(r, n) - 1)//(r-1)
  
H = int(input()) 
n = math.floor(math.log2(H))+1
print(touhi(a=1, r=2, n=n))

### FIXED CODE ###

import math
def touhi(a,r,n):
    return a*(pow(r, n) - 1)//(r-1)
H = int(input()) 
n = math.floor(math.log2(H))+1
print(touhi(a=1, r=2, n=n))
import math

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

d = max(d for d in range(1, math.ceil(M / (N - 1))) if M % d == 0)
print(d)


### FIXED CODE ###

import math

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

if N == 1:
    print(M)
else:
    d = max(d for d in range(1, math.ceil(M / (N - 1))) if M % d == 0)
    print(d)
def inpl(): return list(map(int, input().split()))
Q = int(input())
 
MOD = 10**6 + 3
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
 
size = MOD + 1
g1, g2, inverse = [0]*size, [0]*size, [0]*size
 
g1[:2] = [1, 1] # 元テーブル
g2[:2] = [1, 1] #逆元テーブル
inverse[:2] = [0, 1] #逆元テーブル計算用テーブル

for i in range(2, size):
    g1[i] =  ( g1[i-1] * i ) % MOD 
    inverse[i] = (-inverse[MOD % i] * (MOD//i) ) % MOD 
    g2[i] =  (g2[i-1] * inverse[i]) % MOD

for _ in range(Q):
    x, d, n = inpl()
    print((g1[n] * cmb((x*inverse[d] + n - 1)%MOD, n, MOD) * pow(d, n, MOD))%MOD)

### FIXED CODE ###

import sys
#input = sys.stdin.readline

def inpl(): return list(map(int, input().split()))
Q = int(input())
 
MOD = 10**6 + 3
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
 
size = MOD + 1
g1, g2, inverse = [0]*size, [0]*size, [0]*size
 
g1[:2] = [1, 1] # 元テーブル
g2[:2] = [1, 1] #逆元テーブル
inverse[:2] = [0, 1] #逆元テーブル計算用テーブル

for i in range(2, size):
    g1[i] =  ( g1[i-1] * i ) % MOD 
    inverse[i] = (-inverse[MOD % i] * (MOD//i) ) % MOD 
    g2[i] =  (g2[i-1] * inverse[i]) % MOD

for _ in range(Q):
    x, d, n = inpl()
    xd = x*inverse[d]%MOD
    if d != 0:
        if n < ((MOD-x)*inverse[d] + 1)%MOD:
            n = n%MOD
            print((g1[(xd + n - 1)%MOD] * g2[(xd-1)%MOD] * pow(d, n, MOD))%MOD)
        else:
            print(0)
    else:
        print(pow(x, n, MOD))
N, M = map(int, input().split())
D = [None] * M
for i in range(M):
  a, b = map(int, input().split())
  D[i] = (a, b)
D.reverse()

V = list(range(N))
C = [1] * N
def root(x):
  px = V[x]
  if px == x:
    return px
  else:
    return root(px)

def find(x, y):
  return root(x) == root(y)

def union(x, y):
  rx = root(x)
  ry = root(y)
  if rx != ry:
    V[ry] = rx
    C[rx] += C[ry]

def size(x):
  return C[root(x)]

f = N * (N - 1) // 2
F = []
for a, b in D:
  a -= 1
  b -= 1
  F.append(f)
  if not find(a, b):
    f = max(0, f - size(a) * size(b))
    union(a, b)

F.reverse()
for f in F:
  print(f)

### FIXED CODE ###

N, M = map(int, input().split())
D = [None] * M
for i in range(M):
  a, b = map(int, input().split())
  D[i] = (a, b)
D.reverse()

P = list(range(N))
C = [1] * N
R = [1] * N
def root(x):
  if P[x] == x:
    return x
  else:
    rx = root(P[x])
    P[x] = rx
    return rx

def find(x, y):
  return root(x) == root(y)

def union(x, y):
  rx = root(x)
  ry = root(y)
  if rx != ry:
    if R[ry] > R[rx]:
      rx, ry = ry, rx
    P[ry] = rx
    C[rx] += C[ry]
    R[rx] = max(R[rx], R[ry] + 1)

def size(x):
  return C[root(x)]

f = N * (N - 1) // 2
F = []
for a, b in D:
  a -= 1
  b -= 1
  F.append(f)
  if not find(a, b):
    f = max(0, f - size(a) * size(b))
    union(a, b)

F.reverse()
for f in F:
  print(f)
from collections import Counter 

a,b = map(int,input().split())
l = ''
for i in range(a):
    t = input()
    l+=t

c = Counter(list(l))
# print(c)
dp = [0,0,0]
for i in c:
    if c[i]%2 ==1:
        dp[0] +=1
    elif c[i]%4 == 0:
        dp[2] += 1
    elif c[i]%2 == 0:
        dp[1] += 1
# print(dp)
ans = 'No'
if a%2 ==1 and b%2 ==1:
    A = 1
    B = (a+b-2)//2
A = 0
elif  a%2 ==0 and b%2 ==0:
    B= 0
elif a%2 ==0 and b%2 ==1:
    B = a//2
else:
    B= b//2
if A >= dp[0] and B >= dp[1]:
    ans = 'Yes'
print(ans)


### FIXED CODE ###

from collections import Counter 

a,b = map(int,input().split())
l = ''
for i in range(a):
    t = input()
    l+=t

c = Counter(list(l))
# print(c)
dp = [0,0,0]
for i in c:
    if c[i]%2 ==1:
        dp[0] +=1
    elif c[i]%4 == 0:
        dp[2] += 1
    elif c[i]%2 == 0:
        dp[1] += 1
# print(dp)
ans = 'No'
if a%2 ==1 and b%2 ==1:
    A = 1
    B = (a+b-2)//2
    if A >= dp[0] and B >= dp[1]:
        ans = 'Yes'
elif  a%2 ==0 and b%2 ==0:
    A = 0
    B= 0
    if A >= dp[0] and B >= dp[1]:
        ans = 'Yes'
elif a%2 ==0 and b%2 ==1:
    A = 0
    B = a//2
    if A >= dp[0] and B >= dp[1]:
        ans = 'Yes'
else:
    A=0
    B= b//2
    if A >= dp[0] and B >= dp[1]:
        ans = 'Yes'
print(ans)
#input = raw_input

res = None
G = None

def dfs(jibun_v, p, jibun_c):
    global res
    global G

    res[jibun_v] = jibun_c
    #print(jibun_v, p, jibun_c)

    tonari_nodes = G[jibun_v]
    for tonari_v, w in tonari_nodes:
        #if tonari_v == p or res[tonari_v] != -1:
        if tonari_v == p or res[tonari_v] != -1:
            continue

        if w % 2 == 0:
            tonari_c = jibun_c
        else:
            tonari_c = 1 - jibun_c

        dfs(tonari_v, jibun_v, tonari_c)
    

def main():
    N= int(input())

    global G
    G = [[] for _ in range(N)]

    for i in range(N-1):
        u, v, w = map(int, input().split(" "))
        u -= 1
        v -= 1
        w = w % 2
        G[u].append([v, w])
        G[v].append([u, w])

    global res
    res = [-1 for _ in range(N)]
    
    jibun_v = 0
    p = -1
    jibun_c = 0
    dfs(jibun_v, p, jibun_c)

    for i in range(N):
        print(res[i])

main()
        

### FIXED CODE ###

import math

N, K = [int(elm) for elm in input().split(" ")] 

K2 = math.log2(K)

out = sum([ (0.5) ** int(math.ceil(K2 - math.log2(me))) if me < K else 1 for me in range(1, N+1)]) / N

print(out)