Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N = int(sys.stdin.readline())
GA, SA, BA = list(map(int, sys.stdin.readline().split()))
GB, SB, BB = list(map(int, sys.stdin.readline().split()))

values = []
weights = []
if GB / GA > 1:
    values.append(GB - GA)
    weights.append(GA)
if SB / SA > 1:
    values.append(SB - SA)
    weights.append(SA)
if BB / BA > 1:
    values.append(BB - BA)
    weights.append(BA)
# dp[i]: 重さ i 以下で選ぶのの価値の最大値
dp = [0] * (N + 1)
dp[0] = N
if values:
    for i in range(1, N + 1):
        x = dp[i - 1]
        for w, v in zip(weights, values):
            if i - w >= 0:
                x = max(x, dp[i - w] + v)
        dp[i] = x
    N = dp[N]

values = []
weights = []
if GA / GB > 1:
    values.append(GA - GB)
    weights.append(GB)
if SA / SB > 1:
    values.append(SA - SB)
    weights.append(SB)
if BA / BB > 1:
    values.append(BA - BB)
    weights.append(BB)
# dp[i]: 重さ i 以下で選ぶのの価値の最大値
dp = [0] * (N + 1)
dp[0] = N
if values:
    for i in range(1, N + 1):
        x = dp[i - 1]
        for w, v in zip(weights, values):
            if i - w >= 0:
                x = max(x, dp[i - w] + v)
        dp[i] = x
    N = dp[N]
print(int(N))


### FIXED CODE ###

import math
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N = int(sys.stdin.readline())
GA, SA, BA = list(map(int, sys.stdin.readline().split()))
GB, SB, BB = list(map(int, sys.stdin.readline().split()))

values = []
weights = []
if GB / GA > 1:
    values.append(GB - GA)
    weights.append(GA)
if SB / SA > 1:
    values.append(SB - SA)
    weights.append(SA)
if BB / BA > 1:
    values.append(BB - BA)
    weights.append(BA)
# dp[i]: 重さ i 以下で選ぶのの価値の最大値
dp = [0] * (N + 1)
dp[0] = N
if values:
    for i in range(1, N + 1):
        x = dp[i - 1]
        for w, v in zip(weights, values):
            if i - w >= 0:
                x = max(x, dp[i - w] + v)
        dp[i] = x
    N = dp[N]

values = []
weights = []
if GA / GB > 1:
    values.append(GA - GB)
    weights.append(GB)
if SA / SB > 1:
    values.append(SA - SB)
    weights.append(SB)
if BA / BB > 1:
    values.append(BA - BB)
    weights.append(BB)
# dp[i]: 重さ i 以下で選ぶのの価値の最大値
dp = [0] * (N + 1)
dp[0] = N
if len(values) == 3:
    for i in range(1, N + 1):
        x = dp[i - 1]
        for w, v in zip(weights, values):
            if i - w >= 0:
                x = max(x, dp[i - w] + v)
        dp[i] = x
    N = dp[N]
if len(values) == 2:
    w1, w2 = weights
    v1, v2 = values
    if (v1 + w1) / w1 < (v2 + w2) / w2:
        v1, v2 = v2, v1
        w1, w2 = w2, w1
    c1 = N // w1
    c2 = (N - w1 * c1) // w2
    ret = N + v1 * c1 + v2 * c2
    while c1 >= 0:
        a = N - w1 * c1 - w2 * c2
        c1 -= max(1, math.ceil((w2 - a) / w1))
        c2 = (N - w1 * c1) // w2
        ret = max(ret, N + v1 * c1 + v2 * c2)
        if w1 * c1 + w2 * c2 == N:
            break
    N = ret
if len(values) == 1:
    N += N // weights[0] * values[0]
print(int(N))
### BUGGY CODE ###

n,p=map(int,input().split())

if n==1:
  print(p)
else:
  ans=1
  for i in range(1,100000000):
    tmp=i**n
    if (p>=tmp) and (p%tmp == 0):
     ans=i
    if(p<tmp):
      break
  print(ans)


### FIXED CODE ###

n,p=map(int,input().split())

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

kekka=factorize(p)

ans=1
for i in range(len(kekka)):
    ans=ans* kekka[i][0] ** (kekka[i][1]//n)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

def main():
    n, x = map(int, input().split())
    A = list(map(int, input().split()))

    def segfunc(x, y):
        if x <= y:
          return x
        else:
          return y

    def init(init_val):
        # set_val
        for i in range(n):
            seg[i+num-1] = init_val[i]
        # built
        for i in range(num-2, -1, -1):
            seg[i] = segfunc(seg[2*i+1], seg[2*i+2])

    def update(k, x):
        k += num - 1
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[2*k+1], seg[2*k+2])

    def query(p, q):
        if q <= p:
            return ide_ele
        p += num - 1
        q += num - 2
        res = ide_ele
        while q-p>1:
            if p&1 == 0:
                res = segfunc(res, seg[p])
            if q&1 == 1:
                res = segfunc(res, seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = segfunc(res, seg[p])
        else:
            res = segfunc(segfunc(res, seg[p]), seg[q])
        return res

    # identity element
    ide_ele = 10**9+1

    # num: n以上の最小の2のべき乗
    num = 2**(n-1).bit_length()
    seg = [ide_ele]*2*num

    init(A)

    ans = float('inf')
    for k in range(n):
        t = k*x
        for i in range(n):
            if k <= i:
                t += query(i-k, i+1)
            else:
                t += min(query(0, i+1), query(n-(k-i), n))
        ans = min(t, ans)
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

n, x = map(int,sys.stdin.readline().split())
A = list(map(int,sys.stdin.readline().split()))

ans = 10**18
mins = [a for a in A]
for k in range(n):
    for i in range(n):
        if k <= i:
            mins[i] = min(A[i-k], mins[i])
        else:
            mins[i] = min(A[n-(k-i)], mins[i])
    ans = min(sum(mins)+k*x, ans)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
    s = input().rstrip()
    n = len(s)
    ans = 0
    for l in range(4,n):
        for i in range(n-l+1):
            if int(s[i:i+l])%2019 == 0:
                ans += 1
    print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
mod = 2019
def main():
    s = input().rstrip()
    n = len(s)
    d = {}
    d[0] = 1
    ten = 1
    T = 0
    for x in reversed(s):
        T += ten*int(x)
        ten *= 10
        T %= mod
        ten %= mod
        if T in d:
            d[T] += 1
        else:
            d[T] = 1

    print(sum(i*(i-1)//2 for i in d.values()))
if __name__ == "__main__":
    main()
### BUGGY CODE ###

na,nb,k = map(int, input().split())
ta = list(map(int, input().split()))
tb = list(map(int, input().split()))
 
 
def get_bcnt( usek,tb=tb ):
    tb_sum = [ sum(tb[:i]) + tt for i, tt in enumerate(tb)]
    tb_sum_tf = [ i <= usek for i in tb_sum]
    
    if False in tb_sum_tf:
        return tb_sum_tf.index(False)
    else:
        return len(tb)
    
 
readbook = [ i+1 + get_bcnt( k - sum( ta[:i] ) )  for i in range(na) if sum( ta[:i+1] ) <= k ]
readbook.append( get_bcnt(k) )
print( max(readbook) )

### FIXED CODE ###

na,nb,k = map(int, input().split())
ta = list(map(int, input().split()))
tb = list(map(int, input().split()))

a = [0]
for i in range(na):
  a.append( a[i] + ta[i] )
b = [0]
for i in range(nb):
  b.append( b[i] + tb[i] )

ans, j=0, nb
for i in range(na + 1):
  if a[i] > k:
    break
  while True:
    if a[i] + b[j] > k:
      j -= 1
    else:
      break
  ans = max(ans, i+j)
    
print(ans)
### BUGGY CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N,K = inpl()
hh = inpl()
dp = [INF]*N
dp[0] = 0

for i in range(1,N):
    tmp = INF
    for j in range(1,K+1):
        tmp = min(abs(hh[i]-hh[i-j])+dp[i-j],tmp)
        if i == j:
            break
    dp[i] = tmp

print(dp[-1])


### FIXED CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N,K = inpl()
hh = inpl()
dp = [INF]*N
dp[0] = 0

for i in range(1,N):
    tmp = INF
    for j in range(1,K+1):
        tmp = min(abs(hh[i]-hh[i-j])+dp[i-j],tmp)
        if i == j:
            break
    dp[i] = tmp

print(dp[-1])
### BUGGY CODE ###

N,M,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
sumA=[0]
for i in range(N):
  sumA.append(sumA[-1]+A[i])
sumB=[0]
for i in range(M):
  sumB.append(sumB[-1]+B[i])

ans=0
for i in range(N+1):
  k=K-sumA[i]
  if k<0:
    break
  l=len([x for x in sumB if x<=k])-1
  ans=max(ans,i+l)
print(ans)

### FIXED CODE ###

import bisect
N,M,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
sumA=[0]
for i in range(N):
  sumA.append(sumA[-1]+A[i])
sumB=[0]
for i in range(M):
  sumB.append(sumB[-1]+B[i])

ans=0
for i in range(N+1):
  k=K-sumA[i]
  if k<0:
    break
  l=bisect.bisect_right(sumB,k)-1
  ans=max(ans,i+l)
print(ans)
### BUGGY CODE ###

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

ans = 0
for i in range(k):

    if a > 0:
        ans += 1
        a -= 1
        continue
    if b > 0:
        b -= 1
        continue
    if c > 0:
        ans -= 1
        c -= 1
        continue
print(ans)

### FIXED CODE ###

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

ans = 0

if k < a:
    print(k*1)
else:
    ans = a*1
    k -= a
    if k > 0:
        k -= b*1
        if k > 0:
            ans += k*-1
    print(ans)
### BUGGY CODE ###

n = int(input())
s = list(input())
e_count = s[1:].count('E')
ans_list = []

for _ in range(n):
    if s[_] == "E":
        s[_] = -1
    else:
        s[_] = 1

for i in range(n):
    ans_list.append(sum(s[:i])+e_count)

print(min(ans_list))

### FIXED CODE ###

n = int(input())
s = list(input())
cnt = 0
ans_list = [0]
e_cnt = 0

for i in range(1,n):
    if s[i-1] == "E" and s[i] == "E":
        cnt -= 1
        e_cnt += 1
    if s[i-1] == "E" and s[i] == "W":
        cnt -= 0
    if s[i-1] == "W" and s[i] == "E":
        cnt += 0
        e_cnt += 1
    if s[i-1] == "W" and s[i] == "W":
        cnt += 1
    ans_list.append(cnt)

print(min(ans_list) + e_cnt)
### BUGGY CODE ###

N = int(input())
a = list(input().split())
A = [int(a[i])for i in range(N)]
frag = [0 for i in range(60)]
mod = 10 ** 9 + 7

for i in range(N):
    for j in range(len(bin(A[i])) - 2):
        if A[i] & (1 << j):
            frag[j] += 1

print(sum([(frag[i] * (N - frag[i]) * 2 ** i) for i in range(60)]) % mod)

### FIXED CODE ###

N = int(input())
a = list(input().split())
A = [int(a[i])for i in range(N)]
frag = [0 for i in range(60)]
mod = 10 ** 9 + 7
ans = 0

for i in range(60):
    j = 1 << i
    cnt = sum((k & j) >> i for k in A)
    ans += (cnt * (N - cnt)) << i
    ans %= mod
    
print(ans)
### BUGGY CODE ###

N = int(input())
L = input().split()
Li = []
for i in L:
  Li.append(int(i))
ret = 0
for i in range(0, len(Li)-2):
  for j in range(i+1,len(Li)-1):
    for k in range(j+1,len(Li)):
      if Li[i]+Li[j] > Li[k] and Li[j]+Li[k] > Li[i] and Li[k]+Li[i] > Li[j]:
        ret += 1
print(ret)

### FIXED CODE ###

from bisect import bisect
N = int(input())
L = list(map(int, input().split()))
L.sort()
ret = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        ret += bisect(L,L[i]+L[j]-1)-j-1
print(ret)
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
LR = [0]*q
for i in range(q):
    LR[i] = list(map(int,input().split()))
A = [0]*n
for i in range(n-1):
    if s[i] == "A" and s[i+1] == "C":
        A[i] = 1
for i in range(q):
    print(sum(A[LR[i][0]-1:LR[i][1]-1]))

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
LR = [0]*q
for i in range(q):
    
    LR[i] = list(map(int,input().split()))
A = [0]*n
for i in range(n-1):
    if s[i] == "A" and s[i+1] == "C":
        A[i+1] = 1
    A[i+1] += A[i]
for i in range(q):
    print(A[LR[i][1]-1]-A[LR[i][0]-1])
### BUGGY CODE ###

N, K, Q, *A = map(int, open(0).read().split())
print(*["Yes" if Q < K + A.count(a)
        else "No" for a in range(1, N + 1)], sep='\n')


### FIXED CODE ###

from sys import stdin
from collections import Counter

lines = stdin.readlines()

N, K, Q = map(int, lines[0].split())
ans = [0] * N
A = Counter((int(i) - 1 for i in lines[1:]))
for k in A.keys():
    ans[k] += A[k]
print("\n".join(("Yes" if Q < K + a
                 else "No" for a in ans)))
### BUGGY CODE ###

N, K = map(int, input().split())
x = []
for i in range(N):
    x.append(list(map(int, input().split())))
ans = []
for i in range(N):
    for j in range(N):
        for l in range(N):
            for m in range(N):
                count = 0
                x1 = min(x[i][0], x[j][0])
                x2 = max(x[i][0], x[j][0])
                y1 = min(x[l][1], x[m][1])
                y2 = max(x[l][1], x[m][1])

                for k in range(N):
                    if x1 <= x[k][0] and x[k][0] <= x2 and y1 <= x[k][1] and x[k][1] <= y2:
                        count += 1
                if count >= K:
                    ans.append((x2 - x1) * (y2 - y1))
print(min(ans))


### FIXED CODE ###

N, K = map(int, input().split())
x = []
for i in range(N):
    x.append(list(map(int, input().split())))
ans = []
for i in range(N):
    for j in range(i+1, N):
        for l in range(N):
            for m in range(l+1, N):
                count = 0
                x1 = min(x[i][0], x[j][0])
                x2 = max(x[i][0], x[j][0])
                y1 = min(x[l][1], x[m][1])
                y2 = max(x[l][1], x[m][1])

                for k in range(N):
                    if x1 <= x[k][0] and x[k][0] <= x2 and y1 <= x[k][1] and x[k][1] <= y2:
                        count += 1
                if count >= K:
                    ans.append((x2 - x1) * (y2 - y1))
print(min(ans))
### BUGGY CODE ###

N, K, *h = map(int, open(0).read().split())

dp = [10 ** 10] * N
dp[0] = 0
for i in range(N - 1):
    for j in range(1, K + 1):
        if i + j > N - 1:
            break
        dp[i + j] = min(dp[i + j], dp[i] + abs(h[i + j] - h[i]))
print(dp[N - 1])


### FIXED CODE ###

n, k = [int(e) for e in input().split()]
h = [int(e) for e in input().split()]
cost = [0] * n
cost[1] = abs(h[1] - h[0])
for i in range(1, n):
  cost[i] = min(abs(h[i] - h[j]) + cost[j] for j in range(max(0, i - k), i))
print(cost[n - 1])
### BUGGY CODE ###

X, t = map(int,input().split())
r = 0
cont = 0
while X > 0 and cont < t :
    X = X - 1
    cont = cont + 1
    
print(X)

### FIXED CODE ###

X, t = map(int,input().split())
if (X - t) >= 0:
    print(X - t)
else:
    print(0)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
l = sorted([R, G, B])[::-1]

count = 0
for l0 in range(N//l[0]+1):
  n0 = N-l0*l[0]
  for l1 in range(n0//l[1]+1):
    l2 = (n0 - l1*l[1])/l[2]
    if l2%1.0 == 0 and l2 >= 0:
      count += 1
print(count)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
l = sorted([R, G, B])[::-1]

count = 0
for l0 in range(N//l[0]+1):
  n0 = N-l0*l[0]
  for l1 in range(n0//l[1]+1):
    l2 = n0 - l1*l[1]
    if l2%l[2] == 0 and l2 >= 0:
      count += 1
print(count)
### BUGGY CODE ###

import sys
sa=input()
sb=input()
sc=input()
ss={'a':sa,'b':sb,'c':sc}
t='a'
while True:
  t=ss[t][0]
  if len(ss[t])==0:
    print(t.upper())
    sys.exit()
  elif len(ss[t])==1:
    ss[t]==''
  else: 
  	ss[t]=ss[t][1:]


### FIXED CODE ###

s={i:list(input())for i in'abc'}
i='a'
while s[i]:i=s[i].pop(0)
print(i.upper())
### BUGGY CODE ###

from collections import Counter
from itertools import product

N=int(input())
S=list(input())
S_rev=list(reversed(S[N:]))

bit=list(product(range(2),repeat=N))
leftlist=[] #左半分の分け方の組み合わせを格納
rightlist=[] #右半分について同様

for i in range(len(bit)):
  red=''
  blue=''
  for j in range(N):
    if bit[i][j] == 1:
      red+=S[j] #bitに1が立っているところを赤に
    else:
      blue+=S[j]
  leftlist.append("".join(red + "|" + blue))
left=Counter(leftlist)
             
for i in range(len(bit)):
  red=''
  blue=''
  for j in range(N):
    if bit[i][j] == 1:
      blue+=S_rev[j]
    else:
      red+=S_rev[j]
  rightlist.append("".join(blue + "|" + red))
right=Counter(rightlist)

answer=0

for key,value in left.items():
  answer+= value * right[key] #同じkey(分け方）に対するredとblueの通りを掛け合わせる
print(answer)

### FIXED CODE ###

from collections import Counter
from itertools import product

N=int(input())
S=list(input())
S_rev=list(reversed(S[N:])) #右側から読んだ右半分の文字を考える


leftlist=[] #左半分の分け方の組み合わせを格納
rightlist=[] #右半分について同様

for bit in product(range(2),repeat=N):
  #左半分、右半分について赤と青に塗り分ける
  red_left='' 
  blue_left=''
  red_right=''
  blue_right=''
  for j in range(N):
    if bit[j] == 1:
      red_left+=S[j] #bitに1が立っているところを赤に
      blue_right+=S_rev[j]
    else:
      blue_left+=S[j]
      red_right+=S_rev[j]
  leftlist.append("".join(red_left + "|" + blue_left)) #左の塗り方をリストに格納
  rightlist.append("".join(blue_right + "|" + red_right)) #右について同様
left=Counter(leftlist)
right=Counter(rightlist)

answer=0

for key,value in left.items():
  answer+= value * right[key] #同じkey(分け方）に対するredとblueの通りを掛け合わせる
print(answer)
### BUGGY CODE ###

# coding: utf-8
# Your code here!

x,y,z,k = map(int,input().split())

A = sorted(map(int,input().split()),reverse=True)
B = sorted(map(int,input().split()),reverse=True)
C = sorted(map(int,input().split()),reverse=True)



AB = sorted([a+b for a in A for b in B],reverse=True)

ans = sorted([ab + c for ab in AB[:k] for c in C],reverse=True)

for i in ans[:k]:
    print(i)


### FIXED CODE ###

# coding: utf-8
# Your code here!

x,y,z,k = map(int,input().split())

A = sorted(map(int,input().split()))[::-1]
B = sorted(map(int,input().split()))[::-1]
C = sorted(map(int,input().split()))[::-1]

AB = sorted([a+b for a in A for b in B])[::-1]

ans = sorted([ab + c for ab in AB[:k] for c in C])[::-1]

for i in ans[:k]:
    print(i)
### BUGGY CODE ###

N = int(input())
b = list(int(i) for i in input().split())
b.sort(reverse=True)
sum_N = 0
for i,x in enumerate(b):
    for y in range(i+1,N,1):
        for z in range(y+1,N,1):
            if x>=b[y]+b[z]:
                break
            else:
                sum_N +=1
print(sum_N)

### FIXED CODE ###

import bisect    
    
N = int(input())
b = list(int(i) for i in input().split())
b.sort()
sum_N = 0
for i,x in enumerate(b):
    s = i+1
    for y in range(i+1,N,1):
        index = bisect.bisect_left(b,x+b[y])
        sum_N += max(0,index - y -1)
print(sum_N)
### BUGGY CODE ###

from collections import deque
n,x,y = map(int,input().split())
to = [[] for _ in range(n)]
for i in range(n-1):
    to[i].append(i+1)
    to[i+1].append(i)
x -= 1
y -= 1
to[x].append(y)
to[y].append(x)

ans = [0]*(n-1)
d = {}
for i in range(n-1):
    Q = deque()
    Q.append((i,-1,0))
    flag = [False]*n
    while Q:
        cur,prev,dist = Q.popleft()
        flag[i] = True
        for nxt in to[cur]:
            if nxt == prev: continue
            if flag[nxt]: continue
            flag[nxt] = True
            if (i,nxt) not in d: ans[dist] += 1
            Q.append((nxt,cur,dist+1))
            d[(i,nxt)] = 1
            d[(nxt,i)] = 1

print("\n".join(map(str,ans)))

### FIXED CODE ###

n,x,y = map(int,input().split())
ans = [0]*(n-1)
x -= 1
y -= 1
for i in range(n-1):
    for j in range(i+1,n):
        dist = min(j-i,abs(x-i)+1+abs(j-y),abs(y-i)+1+abs(j-x))
        ans[dist-1] += 1
print("\n".join(map(str,ans)))
### BUGGY CODE ###

x=input()
judge = True
while judge:
    for i in range(len(x)):
        if x[i:i+2] == "ST" :
            x=x[:i] + x[i+2:]
            break
    if "ST" not in x : 
        judge=False
        print(len(x))

### FIXED CODE ###

x=input()
n=len(x)
s_count=0
t_count=0
for i in x:
    if i == "S" : s_count+=1
    else:
        if s_count>0 : 
            s_count-=1
            n-=2
print(n)
### BUGGY CODE ###

import bisect
N, M = list(map(int, input().split(' ')))
As = list(map(int, input().split(' ')))
As = sorted(As)
trimeed = len(As) - 1
for i in range(M):
    hoge = As.pop(-1) // 2
    while As and not As[0]:
        As.pop(0)
    bisect.insort(As, hoge)
print(sum(As))

### FIXED CODE ###

import math
import heapq
n, k = list(map(int, input().split(' ')))
aaa = list(map(int, input().split(' ')))
aaa = [-a for a in aaa]
heapq.heapify(aaa)
for i in range(k):  # TLE?
    t = heapq.heappop(aaa)
    t = math.ceil(t/2)
    heapq.heappush(aaa, t)
print(-sum(aaa))
### BUGGY CODE ###

n,k = map(int,input().split())
l = list(map(int,input().split()))
a = [0]
for i in l:
    if i < k:
        a.append(i)
a.sort()
n = len(a)

def search(m):
    dp = [[0]*(k+1) for i in range(n)]
    dp[0][0] = 1
    now = 0
    for i in range(n):
        if i == m:
            continue
        for j in range(k+1):
            dp[now+1][j] |= dp[now][j]
            if a[i]+j <= k:
                dp[now+1][a[i]+j] |= dp[now][j]
            
        now += 1
    
    for i in range(k-a[m],k):
        if dp[-1][i]:
            return True
    
    return False
le = 0
ri = n


while ri > le+1:
    m = (ri+le)//2

    if search(m):
        ri = m
    else:
        le = m

print(le)


### FIXED CODE ###

n,k = map(int,input().split())
a = [0]+sorted(filter(lambda x: x < k, map(int,input().split())))
n = len(a)

def search(m):

    dp = [1] + [0]*k
    for i in range(n):
        if i == m:
            continue
        for j in range(k,a[i]-1,-1):
            dp[j] |= dp[j-a[i]]
    for i in range(k-a[m],k):
        if dp[i]:
            return True
    return False
le = 0
ri = n


while ri > le+1:
    m = (ri+le)//2

    if search(m):
        ri = m
    else:
        le = m

print(le)
### BUGGY CODE ###

def pc(x):
    cnt = 0
    for i in range(len(x)):
        if x[i]=="1":
            cnt += 1
    return cnt
def f(n,j):
    if n==0:
        return 0
    cnt = 1
    n = n%j
    y = bin(n)[2:]
    if n==0:
        return cnt
    while n%pc(y)!=0:
        cnt += 1
        n = n%pc(y)
        y = bin(n)[2:]
    return cnt+1
N = int(input())
X = input().strip()
k = 0
for i in range(N):
    if X[i]=="1":
        k += 1
n = int(X,2)
for i in range(N):
    if X[i]=="0":
        m = n+2**(N-1-i)
        j = k+1
    else:
        m = n-2**(N-1-i)
        j = k-1
    print(f(m,j))

### FIXED CODE ###

memo = {}
def f(x):
    if x==0:
        return 0
    if x==1:
        return 1
    if x in memo:
        return memo[x]
    k = sum(list(map(int,list(bin(x)[2:]))))
    memo[x] = 1+f(x%k)
    return memo[x]
    
N = int(input())
X = input().strip()
n = sum(list(map(int,list(X))))
if n==0:
    for i in range(N):
        print(1)
elif n==1:
    D = {i:0 for i in range(N)} # mod n+1
    D[0] = 1
    for i in range(1,N):
        D[i] = (D[i-1]*2)%(n+1)
    cnt1 = 0
    for i in range(N):
        if X[i]=="1":
            print(0)
        else:
            a = (cnt1+D[N-1-i])%(n+1)
            print(1+f(a))
else:
    C = {i:0 for i in range(N)}  # mod n-1
    C[0] = 1
    for i in range(1,N):
        C[i] = (C[i-1]*2)%(n-1)
    D = {i:0 for i in range(N)} # mod n+1
    D[0] = 1
    for i in range(1,N):
        D[i] = (D[i-1]*2)%(n+1)
    cnt0 = 0
    cnt1 = 0
    for i in range(N):
        if X[i]=="1":
            cnt0 = (cnt0+C[N-1-i])%(n-1)
            cnt1 = (cnt1+D[N-1-i])%(n+1)
    for i in range(N):
        if X[i]=="1":
            a = (cnt0-C[N-1-i])%(n-1)
            print(1+f(a))
        else:
            a = (cnt1+D[N-1-i])%(n+1)
            print(1+f(a))