Harryxun/stf_run huggingface dataset:
N,Q = map(int,input().split())
par = [i for i in range(N+1)]
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]
def same(x,y):
    return find(x) == find(y)
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x] = y
for i in range(Q):
    x,y,z=map(int,input().split())
    unite(x,y)
    
for i in range(1,N+1):
    find(i)
print(len(set(par[1:])))


### FIXED CODE ###

n,m=map(int,input().split())
xy=[[] for _ in range(n+1)]
for _ in range(m):
    x,y,z=map(int,input().split())
    xy[x].append(y)
    xy[y].append(x)

from collections import deque

visited=[0]*(n+1)
count=0

for i in range(1,n+1):
    if visited[i]==0:
        stack=deque()
        stack.append(i)
        visited[i]+=1
        while stack:
            a=stack.pop()
            for j in xy[a]:
                if visited[j]==0:
                    visited[j]+=1
                    stack.append(j)
        count+=1
print(count)
S = raw_input()

def count_least_turns(s, n=0):
    stripped = s.lstrip(s[0])
    if len(stripped) <= 1:
        return n
    return count_least_turns(stripped, n + 1)

print count_least_turns(S)


### FIXED CODE ###

S = raw_input()

s = S
n = 0
while len(s):
    s = s.lstrip(s[0])
    if len(s):
        n += 1

print n
i = int(input())
l = list(map(int, input().split()))
s = sorted(l)
f = 0

for n in range(i):
    if l[n] == n+1:
        continue
    else:
        f = f + 1
        continue
print(f)
if f == 2:
    print('YES')
elif f == 0:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

a = list(map(int, input().split()))
b = a[0] + a[1]
if b%2 == 0:
  print(int(b/2))
else:
  print('IMPOSSIBLE')
a,b,k=map(int,input.split())

a=max(a-k,0)
k=max(k-a,0)
b=max(b-k,0)
print(a,b)

### FIXED CODE ###


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

a1=max(a-k,0)
k=max(k-a,0)
b=max(b-k,0)
print(a1,b)
import numpy as np

N = int(input())
A = np.array([int(i) for i in (input()).split(" ")])
minA = np.min(A)

if(minA == np.max(A)):
    print(minA)
else:
    check = np.unique(minA // np.arange(1,minA))
    for i in check[::-1]:
        #全てのAに対してiで割り切れるか＝最大公約数
        #iで割り切れた数＝len(A)-1なら，残りの数にiをかけて最大公約数に出来る．
        if(np.sum((A % i>0)) < 2):
            print(i)
            break

### FIXED CODE ###

import numpy as np
import fractions

N = int(input())
A = np.array([int(i) for i in (input()).split(" ")])

maxA = np.max(A)


if(maxA == np.min(A)):
    print(maxA)
elif(N==2):
    print(maxA)
else:
    R=np.zeros((N))
    L=np.zeros((N))
    M=np.zeros((N))

    L[0] = 0
    R[N-1] = 0
    for i in range(1,N):
        #0~i-1番目までの最大公約数
        L[i] = fractions.gcd(A[i-1],L[i-1])
        #i~N番
        R[N-1-i] = fractions.gcd(A[N-1-i+1],R[N-1-i+1])

    M[0] = R[0]
    M[-1] = L[-1]
    for i in range(1,N-1):
        M[i] = fractions.gcd(L[i],R[i])

    print("{}".format(int(np.max(M))))
N=int(input())
people=[]
cost=[]

for i in range(N):
  people.append(int(input())
                
for p in range(len(people)):
  cost.append(0)
  for person in people:
    cost[-1]+=(person-p)**2
                
print(min(cost))

### FIXED CODE ###

N=int(input())
people=[]
cost=[]
 
people=list(map(int,input().split()))

for p in range(101):
    cost.append(0)
    for person in people:
      cost[-1]+=(person-(p+1))**2

print(min(cost))
n = int(input())

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

m = int(input())

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

max_diff = max(max(d),max(t))

diff = [0]*(max_diff+10)

for i in d:
    diff[i] += 1

flag = True

for i in t:
    if diff[i] > 0:
        diff[i] -= 1
    else:
        flag = False
        break

if flag:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

from collections import Counter
 
N = int(input())
D = list(input().split())
 
M = int(input())
T = list(input().split())
 
D_count = Counter(D)
T_count = Counter(T)

for k, v in T_count.items():
    if D_count[k] < v:
        print('NO')
        exit()
 
print('YES')
a,b=int(input().split())

print(max(a*b,a-b,a+b))

### FIXED CODE ###

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

print(max(a+b,a-b,a*b))
def lcm(a, b):
    import math
    return a // math.gcd(a, b) * b


def f(x, c, d):
    res = x
    res -= x//c
    res -= x//d
    res += x//lcm(c,d)
    return res

A, B, C, D = map(int, input().split())

ans = f(B, C, D) - f(A-1, C, D)
print(int(ans))

### FIXED CODE ###

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


def f(x, c, d):
    res = x
    res -= x//c
    res -= x//d
    res += x//lcm(c,d)
    return res

A, B, C, D = map(int, input().split())

ans = f(B, C, D) - f(A-1, C, D)
print(int(ans))
# -*- coding: utf-8 -*-

N = int(input())
A = list(map(int, input().split()))
#A.sort(reverse=True)

pairCounter=0
for i in range(N):
  if A[i] < 0:
    continue
  for b in range(9):
    pair=2**b - A[i]
    if A.count(pair) >0:
      A[i] = -1
      A[A.index(pair)] = -1
      pairCounter+=1
      break

print(pairCounter)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import collections

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
c=collections.Counter(A)

pairCounter=0

beki=29
nibeki=2**beki

for i in range(N):
  target = A[i]
  if c[target] < 1:
    continue
  c[target]-= 1

  while (nibeki > target):
    beki-=1
    nibeki=2**beki

  pair = nibeki * 2 - target
  if pair in c.keys() and c[pair] > 0:
    c[pair]-= 1
    pairCounter+=1

print(pairCounter)
a, b, c = input.split(",")
print(a, b, c)

### FIXED CODE ###

a, b, c = input().split(",")
print(a, b, c)
s=input()
t=input()
score = 0
L = []
for i in range(len(s)-len(t)+1):
  cut = s[i:i+len(t)]
  for j in range(len(t)):
    if cut[j] == t[j] or cut[j] =="?":
      score += 1
  if score == len(t):
    s = s[:i] + t + s[i+len(t):]
    L.append(s.replace("?","a"))
  score = 0
if L = []:
  print("UNRESTORABLE")
else:
  L = sorted(L)
  print(L[0])
    


### FIXED CODE ###

s=input()
t=input()
score = 0
L = []
for i in range(len(s)-len(t)+1):
  k = s
  cut = k[i:i+len(t)]
  for j in range(len(t)):
    if cut[j] == t[j] or cut[j] =="?":
      score += 1
  if score == len(t):
    
    k = k[:i] + t + k[i+len(t):]
    L.append(k.replace("?","a"))
  score = 0
if L == []:
  print("UNRESTORABLE")
else:
  L = sorted(L)
  print(L[0])
from collections import defaultdict
from fractions import Fraction
import sys
input = sys.stdin.readline
def powmod(x, n,mod):
  if n == 0:
   return 1
  K = 1
  while n > 1:
   if n % 2 != 0:
    K = K * x%mod
    x = x ** 2%mod
    n = (n - 1) // 2
   else:
    x = x ** 2%mod
    n = n // 2%mod

  return K * x # 指数を割り続け n が 1 に至ったら終了
N=int(input())
mod=10**9+7
dic=defaultdict(lambda: 0)
dica=defaultdict(lambda: 0)
c=0
d=0
e=0
for i in range(N):
 A,B = map(int,input().split())
 if A==0 and B==0:
  e+=1
 elif A==0:
  c+=1
 elif B==0:
  d+=1
 else:
   x=Fraction(A,B)
   if x>0:
    if x in dic:
     dic[x]+=1
    else:
     dic[x]=1
   else:
    if x in dic:
     dica[x]+=1
    else:
     dica[x]=1
ans=1
for k in dic:
 ans*=(powmod(2,dic[k],mod)+powmod(2,dica.pop(-1/k),mod) -1)
 ans%=mod
for k in dica:
 ans*=powmod(2,dica[k],mod)
 ans%=mod
ans*=(powmod(2,c,mod)+powmod(2,d,mod)-1)
print((ans-1+e)%mod)


### FIXED CODE ###

from collections import defaultdict
from math import gcd
import sys
input = sys.stdin.readline
N=int(input())
mod=10**9+7
dic=defaultdict(lambda: [0,0])
c=0
d=0
e=0
for i in [0]*N:
 A,B = map(int,input().split())
 if A==0 and B==0:
  e+=1
 elif A==0:
  c+=1
 elif B==0:
  d+=1
 else:
  g=gcd(A,B)
  A//=g
  B//=g
  if A*B>0:
   dic[(abs(A),abs(B))][0]+=1
  else:
   dic[(abs(B),abs(A))][1]+=1
ans=1
for k in dic:
 ans=ans*(pow(2,dic[k][0],mod)+pow(2,dic[k][1],mod) -1)
ans=ans*(pow(2,c,mod)+pow(2,d,mod)-1)
print((ans-1+e)%mod)
N = input()
print(N/2)

### FIXED CODE ###

N = input()
print(int((int(N)+1)/2))
n=int(input())
a=sorted([[i]+list(map(int,input().split()))for i in range(n)],key=lambda x:x[1])
s=[]
for i in range(n-1):
    s.append((a[i+1][1]-a[i][1],a[i][0],a[i+1][0]))
a=sorted(a,key=lambda x:x[2])
for i in range(n-1):
    s.append((a[i+1][2]-a[i][2],a[i][0],a[i+1][0]))
s.sort()
t=[i for i in range(n)]
def f(x):
    if x==t[x]:
        return x
    x=t[x]
    return f(t[x])
c=0
for i,j,h in s:
    j,h=f(j),f(h)
    if h!=j:
        t[j]=h
        c+=i
print(c)

### FIXED CODE ###

n=int(input())
a=sorted([[i]+list(map(int,input().split()))for i in range(n)],key=lambda x:x[1])
s=[]
for i in range(n-1):
    s.append((a[i+1][1]-a[i][1],a[i][0],a[i+1][0]))
a=sorted(a,key=lambda x:x[2])
for i in range(n-1):
    s.append((a[i+1][2]-a[i][2],a[i][0],a[i+1][0]))
s.sort()
t=[i for i in range(n)]
def f(x):
    if x==t[x]:
        return x
    t[x]=f(t[x])
    return f(t[x])
c=0
for i,j,h in s:
    j,h=f(j),f(h)
    if h!=j:
        t[j]=h
        c+=i
print(c)
N, M = map(int, input().split())

memo =  [[] for _ in range(M+1)]

for _ in range(M):
    Ai, Bi = map(int, input().split())
    memo[Ai].append(Bi)
    memo[Bi].append(Ai)

# print(memo)

visited = [False] * (N+1)
visited[1] = True
ans = [0]*(N+1)

queue = [1]

while queue:
    room = queue.pop(0)
    for connected_room in memo[room]:
        # print(connected_room)
        if visited[connected_room] == True:
            continue
        ans[connected_room] = room
        visited[connected_room] = True
        queue.append(connected_room)
print("Yes")
for a in ans[2:]:
    print(a)


### FIXED CODE ###

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

memo =  [[] for _ in range(N+1)]

for _ in range(M):
    Ai, Bi = map(int, input().split())
    memo[Ai].append(Bi)
    memo[Bi].append(Ai)

# print(memo)

visited = [False] * (N+1)
visited[1] = True
ans = [0]*(N+1)

queue = [1]

while queue:
    room = queue.pop(0)
    for connected_room in memo[room]:
        # print(connected_room)
        if visited[connected_room] == True:
            continue
        ans[connected_room] = room
        visited[connected_room] = True
        queue.append(connected_room)
print("Yes")
for a in ans[2:]:
    print(a)
S = input()
K = int(input())
for i,j in enumerate(S):
    if not j == "1":
        tmp = i+1
        break
if K < tmp:
    print("1")
else:
    print(j)

### FIXED CODE ###

S = input()
K = int(input())
tmp = None
for i,j in enumerate(S):
    if not j == "1":
        tmp = i+1
        break
if tmp == None:
    print("1")
elif K < tmp:
    print("1")
else:
    print(j)
N = int(input())
L = [list(map(int, input().split())) for _ in range(N)]


for x in range(101):
    for y in range(101):
        h = L[-1][2] + abs(x-L[-1][0]) + abs(y-L[-1][1])
        for l in L: 
            if l[2] == 0:
                if h - (abs(x-l[0]) + abs(y-l[1])) < 0:
                    flag = 0
                    break
            else:
                if h == -1:
                    tmp = l[2] + abs(x-l[0]) + abs(y-l[1])
                h = l[2] + abs(x-l[0]) + abs(y-l[1])
                
                if tmp == h:
                    flag = 1
                    tmp = h
                else:
                    flag = 0
                    break
                
                
        if flag == 1:
            gx = x
            gy = y
            gh = h
            break
                
                    
    if flag == 1:
        break
        
print(gx, gy, gh)

### FIXED CODE ###

N = int(input())
L = [list(map(int, input().split())) for _ in range(N)]

L.sort(key=lambda x:x[2])

for x in range(101):
    for y in range(101):
        h = L[-1][2] + abs(x-L[-1][0]) + abs(y-L[-1][1])
        for l in L: 
            if l[2] == 0:
                if h - (abs(x-l[0]) + abs(y-l[1])) > 0:
                    flag = 0
                    break
            else:

                if h == l[2] + abs(x-l[0]) + abs(y-l[1]):
                    flag = 1
                
                else:
                    flag = 0
                    break
                
                
        if flag == 1:
            gx = x
            gy = y
            gh = h
            break
                
                    
    if flag == 1:
        break
        
print(gx, gy, gh)
a,b = map(int,input())
if (a*b)%2==0:
  print('Even')
else:
  print('Odd')
  

### FIXED CODE ###

a,b = map(int,input().split())
if (a*b)%2==0:
  print('Even')
else:
  print('Odd')
import numpy as np
N = int(input())

txy = [[0,0,0]]
for i in range(N):
    txy.append(list(map(int,input().split())))

out='Yes'
for i in range(1,N+1):
    x = np.array(txy[i])
    y = np.array(txy[i-1])
    mv = x-y
    # print(mv)
    dam = mv[0] - (mv[1] + mv[2])
    if dam%2==1 or dam<0:
        out='No'

print(out)


### FIXED CODE ###

import numpy as np
N = int(input())

txy = [[0,0,0]]
for i in range(N):
    txy.append(list(map(int,input().split())))

out='Yes'
for i in range(1,N+1):
    x = np.array(txy[i])
    y = np.array(txy[i-1])
    mv = abs(x-y)
    # print(mv)
    dam = mv[0] - (mv[1] + mv[2])
    if dam%2==1 or dam<0:
        out='No'

print(out)
hoge = ["FizzBuzz" if i % 3 == 0 and i % 5 == 0 else("Fizz" if i % 3 == 0 else("Buzz" if i % 5 == 0 else str(i))) for i in range(10001)]

while True:
    m, n = map(int, input().split())
    if m == 0:
        break
    man = [str(i) for i in range(1, m+1)]
    a, b = divmod(n, m)
    man = a*man+man[:b]
    idx = 0
    for i in range(1, n+1):
        if hoge[i] == input():
            idx += 1
        else:
            v = man[idx]
            man = list(filter((v).__ne__, man))
            if len(man) == 1:
                break
    print(*sorted(list(set(man))))

### FIXED CODE ###

hoge = ["FizzBuzz" if i % 15 == 0 else("Fizz" if i % 3 == 0 else("Buzz" if i % 5 == 0 else str(i))) for i in range(10001)]

while True:
    m, n = map(int, input().split())
    if m == 0:
        break
    man = list(range(1, m+1))
    game = [input() for _ in range(n)]
    idx = 0
    for i in range(n):
        if game[i] != hoge[i+1]:
            del man[idx]
            if len(man) == 1:
                break
        else:
            idx += 1
        idx %= len(man)
    print(*man)
s=str(input())
if int(s[0:4])*10000+int(str[5:7])*100+int(str[8:10])>20190430:
  print('TBD')
else:
  print('Heisei')

### FIXED CODE ###

s=str(input())
if int(s[0:4])*10000+int(s[5:7])*100+int(s[8:10])>20190430:
  print('TBD')
else:
  print('Heisei')
a = input()
b = len(list(a))
c = int(a)
d = ''

if b % 2 == 0:
    d = '9' * (b // 2)
    print('0'.join(d))

else:
    if b > 1:
        d = '9' * (b // 2)
    '0'.join(d)
    d = int(d)
    if b > 1:
        print(d + int(a[1:]) + 1)
    else:
        print(int(a))

### FIXED CODE ###

a = input()
b = len(list(a))
c = int(a)
d = ''

if b % 2 == 0:
    d = '9' * (b // 2)
    print('0'.join(d))

else:
    if b == 1:
        print(a)
    else:
        d = '9' * (b // 2)
        d = '0'.join(d)
        d = int(d + '0')
        print(c - d)
N,K = int(input()), int(input())
new = abs(N-K)
while(new<N):
    N = new
    new = abs(new-K)
print(N)



### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[10]:


N,K = map(int,input().split())
new = N % K
n2 = K - new

print(min(new,n2))
a,b,c = map(str, raw_input().split())
print b[1]

### FIXED CODE ###

a,b,c = map(str, raw_input().split())
print a[0] + b[0] + c[0]
elements = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
K = input()
th = K-1
print(elements[th])

### FIXED CODE ###

elements = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
K = int(input())
th = K-1
print(elements[th])
import bisect
A, B, Q = map(int, input().split())
INF = 10 ** 18
s = [-INF] + [int(input()) for i in range(A)] + [INF]
t = [-INF] + [int(input()) for i in range(B)] + [INF]
for q in range(Q):
    x = int(input())
    b, d = bisect.bisect_left(s, x), bisect.bisect_left(t, x)
    res = INF
    for S in [s[b + 1], s[b]]:
        for T in [t[d + 1], t[d]]:
            d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
            res = min(res, d1, d2)
    print(res)

### FIXED CODE ###

import bisect
A, B, Q = map(int, input().split())
INF = 10 ** 18
s = [-INF] + [int(input()) for i in range(A)] + [INF]
t = [-INF] + [int(input()) for i in range(B)] + [INF]
for q in range(Q):
    x = int(input())
    b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
    res = INF
    for S in [s[b - 1], s[b]]:
        for T in [t[d - 1], t[d]]:
            d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
            res = min(res, d1, d2)
    print(res)
S = []
for _ in range(2):
    S.append(input())

if S == [1, 2]
  print('3')
elif S == [1, 3]:
  print('2')
elif S == [2, 3]:
  print('1')

### FIXED CODE ###

a = int(input())
b = int(input())
c = a + b

if c == 3:
  print('3')
elif c == 4:
  print('2')
else:
  print('1')
n = int(input())
x = int(input(), 2)

print(x * (x+1))

### FIXED CODE ###

s = [c for c in input()]
k = int(input())

import copy

if len(s) == 1:
    print(k//2)

elif len(s) == len(set(s)):
    print(0)
    
elif s[0] != s[-1]:
    c = 0
    for i in range(1, len(s)):
        if s[i-1] == s[i]:
            c = c + 1
            s[i] = 'Z'
    print(c*k)

else: # s[0]==s[-1]
    s2 = copy.copy(s)
    c = 0
    for i in range(1, len(s)):
        if s[i-1] == s[i]:
            c = c + 1
            s[i] = 'Z'
    if s[-1] == 'Z':
        print(c*k)
    else:
        c2 = 1
        s2[0] = 'Z'
        for i in range(1, len(s)):
            if s2[i-1] == s2[i]:
                s2[i] = 'Z'
                c2 = c2 + 1
        if s2[-1] == 'Z':
            if k % 2 == 0:
                print(int((c+c2)*(k/2)))
            else:
                print(int((c+c2)*((k-1)/2)+c))
        else:
            print(c + c2*(k-1))
A,B=map(int,input().split())
print(max(A+B,A-B,A*B)

### FIXED CODE ###

A,B=map(int,input().split())
print(max(A+B,A-B,A*B))
import copy
n, k = map(int, input().split())
alist = list(map(int, input().split()))

ans = 10**20
count = 0
tempbin = ""
maxx = 0

for i in range(2**n):
    tempbin = format(i,'b')
    tempbin = tempbin.zfill(n)
    count = 0
    templist = alist.copy()
    if tempbin.count("1") != k:
        continue
    for j in range(1,n):
        if tempbin[j] == "1":
            maxx = max(templist[:j])
            if maxx >= templist[j]:
                count += maxx + 1 - templist[j]
                templist = maxx + 1
    ans = min(ans,count)

print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
 
a = list(map(int, input().split()))
 
min_cost = float("inf")
for i in range(2**n):
    if bin(i).count("1") != k:
        continue
 
    min_h = a[0]
    cost = 0
    for j in range(1, n):
        if i >> j & 1:
            min_h += 1
            cost += max(0, min_h-a[j])
 
        min_h = max(min_h, a[j])
 
    min_cost = min(min_cost, cost)
 
print(min_cost)
#!/usr/bin/env python3
import pandas as pd

n ,m = map(int, input().split())
a = pd.Series(list(map(int, input().split())))
t = a >= a.sum() * 1/(4*m)
if t.sum() >= m:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

#!/usr/bin/env python3
import numpy as np

n ,m = map(int, input().split())
a = np.array(list(map(int, input().split())))
t = a >= a.sum() * 1/(4*m)
if t.sum() >= m:
    print('Yes')
else:
    print('No')
N = int(input())
A = [[] for _ in range(N)]
for i in range(N):
    for _ in range(int(input())):
        A[i].append([int(s) for s in input().split()])

ret = 0
for i in range(2 ** N):#2**Nだけ正解の候補がある
    bits = [i >> j & 1 for j in range(N)]#　N桁の２進数iについて、逆順に並べた配列が生成
    #print(bits)
    for i, a in enumerate(A):#i→人、a→人iの証言のリスト
        if bits[i] == 0:#人iが正直者じゃない場合、continueして次の人の証言に移行
            continue
        for x, y in a:
            # print(bits, bits[x - 1], y)
            if bits[x - 1] == y:#正解の候補と証言が一致する場合、その人の次の証言を参照
                continue
            break　　　　　　　　　#そうでない場合、その人の証言を聞くのをやめて次の人の証言を聞く
        else:#breakでループを抜けなかったときにのみ、elseが実行
            continue#このcontinueは２つ上のfor文のcontinueつまり、間違った証言がある場合、一つ下のbreakが評価されて、次の正解候補にうつる
        break
    else:#breakでループを抜けなかったときにのみ、elseが実行
        ret = max(ret, sum(bits))
print(ret)

### FIXED CODE ###

N = int(input())
A = [[] for _ in range(N)]
for i in range(N):
    for _ in range(int(input())):
        A[i].append([int(s) for s in input().split()])

ret = 0
for i in range(2 ** N):#2**Nだけ正解の候補がある
    bits = [i >> j & 1 for j in range(N)]#　N桁の２進数iについて、逆順に並べた配列が生成
    #print(bits)
    for i, a in enumerate(A):#i→人、a→人iの証言のリスト
        if bits[i] == 0:#人iが正直者じゃない場合、continueして次の人の証言に移行
            continue
        for x, y in a:
            # print(bits, bits[x - 1], y)
            if bits[x - 1] == y:#正解の候補と証言が一致する場合、その人の次の証言を参照
                continue
            break#そうでない場合、その人の証言を聞くのをやめて次の人の証言を聞く
        else:#breakでループを抜けなかったときにのみ、elseが実行
            continue#このcontinueは２つ上のfor文のcontinueつまり、間違った証言がある場合、一つ下のbreakが評価されて、次の正解候補にうつる
        break
    else:#breakでループを抜けなかったときにのみ、elseが実行
        ret = max(ret, sum(bits))
print(ret)
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

dp = [1000000] * (10 ** 5)
dp[0] = 0
for i in range(H):
    if dp[i] == 1000000:
        continue
    for j in range(N):
        a, b = AB[k]
        if dp[i] + b < dp[i + a]:
            dp[i + a] = dp[i] + b
print(min(dp[H:]))


### FIXED CODE ###

def main():
    from sys import stdin
    readline = stdin.readline
    H, N = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(N)]

    dp = [100000000] * (H + 10 ** 4 + 1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == 100000000:
            continue
        for j in range(N):
            a, b = AB[j]
            if dp[i] + b < dp[i + a]:
                dp[i + a] = dp[i] + b
    print(min(dp[H:]))


main()
# atCoder Beginner Contest 147 a

import sys


def main():
    l = list(sys.stdin.readline().split())
    [int(e) for e in l]
    if sum(l) <= 21:
        print('win')
    else:
        print('bust')


main()


### FIXED CODE ###

# atCoder Beginner Contest 147 a

import sys


def main():
    l = list(sys.stdin.readline().split())
    l = [int(e) for e in l]
    if sum(l) <= 21:
        print('win')
    else:
        print('bust')


main()
n = int(input())
a = input()
if a[:n/2+1]==a[n/2+1:]:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

n = int(input())
a = input()
if a[:n//2]==a[n//2:]:
  print("Yes")
else:
  print("No")
from string import ascii_uppercase


def actual(n, s):
    answer = ''

    for char in s:
        # mod 26 で 26パターンに分類できる。 `-13` はidx調整項
        idx_shift_n = (ord(char) % 26) + n - 13

        answer += ascii_uppercase[idx_shift_n]

    return answer


n = int(input())
s = input()

print(actual(n, s))

### FIXED CODE ###

def actual(n, s):
    # 方針: 0->25 の世界で nだけシフトさせる → 65-90の世界に復元
    answer = ''

    ord_A = ord('A')

    for char in s:
        x = ord(char) - ord_A  # Aが0になるように初期化する
        y = (x + n) % 26  # mod 26 で 26パターンに分類できる
        z = y + ord_A  # 復元できるように補正する

        answer += chr(z)

    return answer


n = int(input())
s = input()
 
print(actual(n, s))
N, K = map(int,input().split())

dic = {}
i = 0
while (2 ** i) <= (10 ** 5):
    dic[i] = 0
    i += 1

for i in range(1, N+1):
    cnt = 0
    while i * (2 ** cnt) < K:
        cnt += 1
    dic[cnt] += 1

ans = 0
for k, v in dic.items():
    if v > 0:
        ans += v * (0.5 ** k) / N

print(ans)

### FIXED CODE ###

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

ans = 0
for i in range(1, N+1):
    cnt = 0
    while i * (2 ** cnt) < K:
        cnt += 1
    ans += (0.5 ** cnt) / N

print(ans)