Harryxun/stf_run huggingface dataset:
K, A, B = map(int, input().split())
count = 1
coin = 0
if B - A <= 2:
  print(K + 1)
  
else:
  for i in range(K):
    if coin == 1:
      count += B
      coin -= 1
    elif count >= A and i != k-1:
      count -= A
      coin += 1
    else:
      count += 1
  print(count)
  
  

### FIXED CODE ###

K, A, B = map(int, input().split())
ans = 0
if B - A <= 2:
  print(K + 1)

else:
  K -= A - 1
  ans += (K//2) * (B - A) + A
  ans += K % 2
  print(ans)
N,K=map(int,input().split())
A=list(map(int,input().split()))
from fractions import gcd
g=A[0]
for a in A[1:]:
    g=gcd(g,a)
print(['IMPOSSIBLE','POSSIBLE'][((g==1 or K%g==0) and max(A)>=K)

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
from fractions import gcd
g=A[0]
for a in A[1:]:
    g=gcd(g,a)
print(['IMPOSSIBLE','POSSIBLE'][(g==1 or K%g==0) and max(A)>=K])
n, k = map(int, input().split())
TD = [[] for i in range(n)]
for i in range(n):
  TD[i] = list(map(int, input().split()))
  
TD.sort(key = lambda x:x[1], reverse = True)

ans = 0
huku = []
su = set([])

for i, j in TD[:k]:
  ans += j
  if i in su:
    huku.append([i,j])
  su.add(i)
ans += len(su)**2
huku.sort(key = lambda x:x[1], reverse = True)

ansl = []
ansl.append(ans)
for i,j in TD[k:]:
  if i in su:
    continue
  else:
    temp = ansl[-1] + j - huku.pop()[1] + (len(su)+1)**2 -len(su)**2
    su.add(i)
    ansl.append(temp)

print(max(ansl))

### FIXED CODE ###

n, k = map(int, input().split())
TD = [[] for i in range(n)]
for i in range(n):
  TD[i] = list(map(int, input().split()))
  
TD.sort(key = lambda x:x[1], reverse = True)

ans = 0
huku = []
su = set([])

for i, j in TD[:k]:
  ans += j
  if i in su:
    huku.append([i,j])
  su.add(i)
ans += len(su)**2
huku.sort(key = lambda x:x[1], reverse = True)

ansl = []
ansl.append(ans)
for i,j in TD[k:]:
  if i in su:
    continue
  elif huku == []:
    break
  else:
    temp = ansl[-1] + j - huku.pop()[1] + (len(su)+1)**2 -len(su)**2
    su.add(i)
    ansl.append(temp)

print(max(ansl))
N, M = map(int, input().split())

p = [0]*M
k = [""] * M

for i in range(M):
    p[i], k[i] = input().split()
    p[i] = int(p[i])
    

ans = [0]*N
pen = [0]*N
accept = 0
pena = 0
for i in range(M):
    if k[i] == "WA" and ans[p[i]] == 0:
        pen[p[i]] += 1
    elif k[i] == "AC" and ans[p[i]] == 0:
        pena += pen[p[i]]
        ans[p[i]] = 1
        accept += 1
        
print(str(accept) + " " + str(pena))

### FIXED CODE ###

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

p = [0] * M
k = [""] * M

for i in range(M):
    p[i], k[i] = input().split()
    p[i] = int(p[i])-1
    

ans = [0]*N
pen = [0]*N
accept = 0
pena = 0
for i in range(M):
    if k[i] == "WA" and ans[p[i]] == 0:
        pen[p[i]] += 1
    elif k[i] == "AC" and ans[p[i]] == 0:
        pena += pen[p[i]]
        ans[p[i]] = 1
        accept += 1
        
print(str(accept) + " " + str(pena))
import numpy as np
# from itertools import accumulate

N = int(input())
s = input()
w = np.array(list(map(lambda x: 1 if x == 'W' else 0, s)))
e = np.array(list(map(lambda x: 1 if x == 'E' else 0, s)))
w = np.add.accumulate(w)
e = np.flip(np.add.accumulate(np.flip(e)))
# print(w)
# print(e)
ans = []
for i in range(N):
    num = 0
    if 0 < i: num += w[i - 1]
    if i < N - 1: num += e[i + 1]
    ans.append(num)
# print(ans)
print(min(ans))

### FIXED CODE ###

from itertools import accumulate
N = int(input())
s = input()
w = list(map(lambda x: 1 if x == 'W' else 0, s))
e = list(map(lambda x: 1 if x == 'E' else 0, s))
e.reverse()
w = list(accumulate(w))
e = list(accumulate(e))
e.reverse()
# print(w)
# print(e)
ans = []
for i in range(N):
    num = 0
    if 0 < i: num += w[i - 1]
    if i < N - 1: num += e[i + 1]
    ans.append(num)
# print(ans)
print(min(ans))
x,y = map(int,input().split())
s=[0,]
d={
  1:30000,
  2:20000,
  3,10000,
}

if x in d:
  s.append(d[x])

if y in d:
  s.append(d[y])

if x==1 and y==1:
  s.append(40000)
  
print(sum(s))

### FIXED CODE ###

x,y = map(int,input().split())
s=[0,]
d={
  1:300000,
  2:200000,
  3:100000,
}

if x in d:
  s.append(d[x])

if y in d:
  s.append(d[y])

if x==1 and y==1:
  s.append(400000)
  
print(sum(s))
N = int(input())
a = 1
while a * a <= N:
  if N % a = 0:
    k = a
  a += 1
print(k + (N/k) - 2)


### FIXED CODE ###

N = int(input())
a = 1
while a * a <= N:
  if N % a == 0:
    k = a
  a += 1
b = N //k
print(b + k - 2)
import math
A, B, X = map(int, input().split())
L = []
for ln_N in range(17):
    N = math.floor((X - B * ln_N) / A)
    if N <= 0:
        L.append(0)
    else:
        if math.floor(math.log10(N)+1) == ln_N:
            L.append(N)
print(min(1000000000,max(L)))


### FIXED CODE ###

S = input()
L = ['SAT','FRI','THU','WED','TUE','MON','SUN']
for i,l in enumerate(L):
  if S == l:
    print(i+1)
    break
print(8-int((input()-400)/200))

### FIXED CODE ###

X=int(input())
N=8-int((X-400)/200)
print(N)
n = int(input())
h = list(map(int,input().split()))

ans = []
count = 0
for i in range(n-1):
  if h[i] >= h[i+1]:
    print(h[i])
    print(h[i+1])
    count+=1
  elif h[i] <= h[i+1]:
    ans.append(count)
    count = 0
  else:
    ans.append(count)
    
print(max(ans))

### FIXED CODE ###

n = int(input())
h = list(map(int,input().split()))
ans = []
ans.append(0)
count = 0
for i in range(n-1):
  if h[i] >= h[i+1]:
    count += 1
    ans.append(count)
  else:
    count=0
print(max(ans))
S=int(input())
x=int(math.sqrt(S))
y=S-x**2
print(2,0,x+2,y,1,x)

### FIXED CODE ###

S=int(input())
a=10**9
b=0
c=S%a
d=S//a+1
if S==1000000000000000000:
    print(0,0,10**9,0,0,10**9)
else:
    print(0,1,a,b,c,d)
N, M = map(int, input().split())
sc = [list(map(int,input().split())) for i in range(M)]

sc = list(map(list, set(map(tuple, A))))
for i in range(len(sc)):
    tmp0 = sc[i][0]
    tmp1 = sc[i][1]
    for j in range(1, len(sc)-i+1):
        if tmp0 == sc[-j][0] and tmp1 != sc[-j][1]:
            print(-1)
            exit()

if N == 3:
    #for i in range(100,1000):
        #i_str = str(i)
    for j in range(len(sc)):
        if sc[j][0] == 1 and sc[j][0] == 0:
            print(-1)
            exit()
        if sc[j][0] == 1:
            num = sc[j][1]
    

### FIXED CODE ###

N, M = map(int, input().split())
P = [list(map(int,input().split())) for i in range(M)]

ans = -1

for x in range(1000):
    if len(str(x)) != N: 
        continue
    else:
        count = 0
        s = str(x)
        for p in P:
            if int(s[int(p[0]) - 1]) == p[1]:
                count += 1
        if count == M:
            ans = x
            break

print(ans)
def ceildiv(a, b):
    return -(-a // b)

int h, w = map(int, input().split())

if (h==1 or w==1):
    print(1)
else:
    print(ceildiv(h,2)*ceildiv(w,2) + (ceildiv(h,2)-1)*(ceildiv(w,2)-1))

### FIXED CODE ###

ks = [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())
print(ks[k-1])
[x,y]=list(map(int,input().split()))
if ((x%3)+(y%3))%3!=0:
	print(0)
else:
	n=int((x+y)/3)
	r=y-n
	if r<0 or r>n:
		print(0)
	else:
		if r>n-r:
			r=n-r
		mod=1000000007
		kaijo=[1]
		for i in range(1,n+1):
			kaijo.append(kaijo[-1]*i%mod) #これで、kaijo[i]=i!となる。
		gyakugen=[pow(kaijo[n-r],mod-2,mod)]
		for i in reversed(range(1,n-r)):
			gyakugen.append(gyakugen[-1]*i) #これで、gyakugen[i]=n-r-iの逆元となる
		kotae=kaijo[n]*gyakugen[0]*gyakugen[n-2*r]%mod

		print(kotae)

### FIXED CODE ###

[x,y]=list(map(int,input().split()))
if ((x%3)+(y%3))%3!=0:
	print(0)
else:
	n=int((x+y)/3)
	r=y-n
	if r<0 or r>n:
		print(0)
	else:
		if r>n-r:
			r=n-r
		mod=1000000007
		kaijo=[1]
		for i in range(1,n+1):
			kaijo.append(kaijo[-1]*i%mod) #これで、kaijo[i]=i!となる。
		gyakugen=[pow(kaijo[n-r],mod-2,mod)]
		for i in reversed(range(1,n-r+1)):
			gyakugen.append(gyakugen[-1]*i%mod) #これで、gyakugen[i]=n-r-iの逆元となる
		kotae=kaijo[n]*gyakugen[0]*gyakugen[n-2*r]%mod

		print(kotae)
n, k = input().split()
n = int(n) #友人の数
k = int(k) #基準の高さ
m = []
result = 0
for i in range(n):
  m.append(int(input()))
#各人の身長を基準の高さと比較
for i in range(len(m)):
  if k <= m[i]:
    result += 1
  else:
    result += 0
print(result)

### FIXED CODE ###

N = input()
N = int(N)
if N%2 == 0:
  import math
  a = N/2/N  
  print('{:.6f}'.format(a))
else :
  a = (N+1)/2/N
  print('{:.6f}'.format(a))
import math

n,m=map(int,input().split())
a = list(map(int, input().split()))
ans = a[0]
for i in range(1,n):
    ans = ans * a[i] // math.gcd(ans, a[i])


b = [int(i/2) for i in a]
ans2= b[0]
for i in range(1,n):
    ans2 = ans2 * b[i] // math.gcd(ans2, b[i])


if ans2>m:
    print(0)
else:
    print((m-ans2)//ans+1)

### FIXED CODE ###

import fractions,sys

n,m=map(int,input().split())
a = list(map(int, input().split()))
# ans = a[0]
# for i in range(1,n):
#     ans = ans * a[i] // fractions.gcd(ans, a[i])
ff=[]
for j in  a:
    count=0
    for i in range(1,36):
        if j%(2**i)==0:
            count+=1
    ff.append(count)
ff=[i==ff[0] for i in ff]

 
b = [int(i/2) for i in a]
# b_list=[i%4==0 for i in b]
# bb=sum(b_list)
# if bb!=0 and bb!=n:
if all(ff)==False:
    print(0)
    exit()

ans2= b[0]
for i in range(1,n):
    ans2 = ans2 * b[i] // fractions.gcd(ans2, b[i])

# tf=[(ans2/i)%2==0 for i in b]
# and any(tf)
if ans2>m:
    print(0)
else:
    print((m-ans2)//(ans2*2)+1)
import collections

n = int(input());
S = [];

for i in range(n):
  S.append(input());

c = collections.Counter(S)

num = c.most_common()[0][1];
ans = [];

for i in range(len(c)):
  if c.most_common()[i][1] == num:
    ans.append(c.most_common()[i][0]);
    continue;
    
  else:
    break;
    
for a in len(ans):
  print(ans[a]);

### FIXED CODE ###

import collections

n = int(input());
S = [];

for i in range(n):
  S.append(input());

c = collections.Counter(S)

num = c.most_common()[0][1];
ans = [];

for a,b in c.most_common():
    if b == num:
      ans.append(a);
      continue;
    
    else:
      break;

ans = sorted(ans);

for i in ans:
  print(i);
nums = input().split()

if nums[0] =< nums[1] and nums[1] =< nums[2]:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

nums = input().split()

if int(nums[0]) < int(nums[1]) and int(nums[1]) < int(nums[2]):
    print("Yes")
else:
    print("No")
import copy
import sys
H, W, M= map(int,input().split())
height = [0]*H
width = [0]*W
object = []
for i in range(H):
   object += copy.deepcopy(width)
for s in sys.stdin.readlines():
    h, w = map(int, s.split())
    height[h-1] += 1
    width[w-1] += 1
    object[h-1][w-1] = 1
h_max = max(height)
w_max = max(width)
cand_w = []
cand_h = []
for i in range(W):
   if width[i] == w_max:
      cand_w.append(i)
for i in range(H):
   if height[i] == h_max:
      cand_h.append(i)
ans = h_max + w_max - 1
p = len(cand_h)*len(cand_w)
if M > p:
   for i in range(len(cand_h)):
      for j in range(len(cand_w)):
         if object[cand_h[i]][cand_w[j]] == 0:
            ans += 1
else:
   ans += 1
print(ans)

### FIXED CODE ###

import copy
import sys
H, W, M= map(int,input().split())
height = [0]*H
width = [0]*W
object = []
for s in sys.stdin.readlines():
    h, w = map(int, s.split())
    height[h-1] += 1
    width[w-1] += 1
    object.append([h-1, w-1])
h_max = max(height)
w_max = max(width)
cand_w = []
cand_h = []
for i in range(W):
   if width[i] == w_max:
      cand_w.append(i)
for i in range(H):
   if height[i] == h_max:
      cand_h.append(i)
ans = h_max + w_max
c = 0
p = len(cand_h)*len(cand_w)
cand_h = set(cand_h)
cand_w = set(cand_w)
if M >= p:
   for i in range(len(object)):
      if object[i][0] in cand_h and object[i][1] in cand_w:
         c += 1
print(ans - (c == p))
n = int(input())
a = list(map(int,input().split()))
ans = [0] * int(1e5)
for i in range(n):
    ans[a[i]-1] += 1
    ans[a[i]] += 1
    ans[a[i]+1] += 1
print(max(ans))





### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = [0] * (int(1e5)+5)
for i in range(n):
    ans[a[i]-1] += 1
    ans[a[i]] += 1
    ans[a[i]+1] += 1
print(max(ans))
s = input()
arr = [int(i) for i in s.split('')]
result = 0
for i in range(arr):
  result = result+arr[i]
if(result>=22):
  print("bust")
else:
  print("win")

### FIXED CODE ###

a,b,c = map(int,input().split())
if a+b+c >= 22:
  	print("bust")
else:
  print("win")
= int(input())
b = list(map(int, input().split()))
if n == 2:
    print(b[0] * 2)
else:
    res = [0] * n
    for i in range(n-2):
        if b[i] < b[i+1]:
            res[i] = b[i]
            res[i+1] = b[i]
        else:
            res[i+1] = b[i+1]
    if b[-2] < b[-1]:
        res.append(b[-1])
    else:
        res[-1] = b[-1]
        res.append(b[-1])
    print(sum(res))


### FIXED CODE ###

n = int(input())
b = list(map(int, input().split()))
if n == 2:
    print(b[0] * 2)
else:
    res = [0] * n
    res[0] = b[0]
    for i in range(n-2):
        if b[i] < b[i+1]:
            res[i+1] = b[i]
        else:
            res[i+1] = b[i+1]
    if b[-2] < b[-1]:
        res.append(b[-1])
    else:
        res.append(b[-1])
    print(sum(res))
_=input()
X=int(eval(input().replace(*' *')))
print(X if X <= 1e18 else -1)

### FIXED CODE ###

N=int(input())
X=list(map(int, input().split()))
ans=1
if 0 in X:
    print(0)
else:
    for i in range(N):
        ans *= X[i]
        if 10**18<ans:
            print(-1)
            break
    else:
        print(ans)
from random import randint
n = int(input())
l = list(map(int, input().split()))
ans = 0
for i in range (len(a)-1) :
  try:
    if l[i] == l[i + 1]:
        ans += 1
        l[i + 1] = randint(0, 10000)
  except:
    continue
print(ans)

### FIXED CODE ###

from random import randint
n = int(input())
l = list(map(int, input().split()))
ans = 0
for i in range (len(l)-1) :
  try:
    if l[i] == l[i + 1]:
        ans += 1
        l[i + 1] = randint(0, 10000)
  except:
    continue
print(ans)
N=map(int, input().split())
if N % 2 == 1:
   print((N+1)/2)
else:
    print(N/2)



### FIXED CODE ###

N = int(input())
if N % 2 == 1:
    print(int((N+1)/2))
else:
    print(int(N/2))
import sympy

R = float(input())
2*sympy.pi.evalf(30)*R

### FIXED CODE ###

import math
R = int(input())
print(2*math.pi*R)
args = input()
 
if(args == "ABC"){
print("ARC")
}elif(args=="ARC"){
print("ABC")
}

### FIXED CODE ###

args = input()
if args == "ABC":
 print("ARC")
elif(args=="ARC"):
 print("ABC")
import math

def overlap(p1, p2, d):
    return (p1[0] - p2[0])**2 + (p1[1] - p2[1])**2 <= d**2

def intersection(o1,o2):
    a  = 2*(o2[0] - o1[0])
    b  = 2*(o2[1] - o1[1])
    c  = (o1[0] - o2[0])*(o1[0] + o2[0]) + (o1[1] - o2[1])*(o1[1] + o2[1])
    a2 = a**2 + b**2
    b2 = a*c + a*b*o1[1] - b**2*o1[0]
    c2 = b**2*(o1[0]**2 + o1[1]**2 - 1) + c**2 + 2*b*c*o1[1]
    judge = b2**2 - a2*c2
    if judge < 0:
        return None, None
    elif abs(judge) < 1.0e-6:
        x = -b2/a2
        y = -(a*x + c)/b
        return [x,y], None
    else:
        x1 = (-b2 + math.sqrt(b2**2 - a2*c2))/a2
        x2 = (-b2 - math.sqrt(b2**2 - a2*c2))/a2
    if abs(b) == 0:
        y1 = o1[1] + math.sqrt(1 - (x1 - o1[0])**2)
        y2 = o1[1] - math.sqrt(1 - (x1 - o1[0])**2)
    else:
        y1 = -(a*x1 + c)/b
        y2 = -(a*x2 + c)/b
    return [x1, y1], [x2, y2]

while True:
    n = int(input())
    if n == 0:
        break
    p = []
    for i in range(n):
        p.append(list(map(float, input().split(","))))
    ans = 1
    for i in range(n - 1):
        for j in range(i + 1, n):
            if not overlap(p[i], p[j], 2):
                continue
            p1, p2 = intersection(p[i], p[j])
            cnt1 = 0
            cnt2 = 0
            for k in range(n):
                if p1 and overlap(p1, p[k], 1):
                    cnt1 += 1
                if p2 and overlap(p2, p[k], 1):
                    cnt2 += 1
            ans = max([ans, cnt1, cnt2])
    print(ans)



### FIXED CODE ###

import math

def dist(p1, p2):
    return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)

def intersection(o1,o2):
    if dist(o1,o2) > 2:
        p1, p2 =  [None, None], [None, None]
    elif dist(o1,o2) == 2:
        p1, p2 =  [(o1[0] + o2[0])/2, (o1[1] + o2[1])/2], [None, None]
    else:
        m = [(o1[0] + o2[0])/2, (o1[1] + o2[1])/2]
        v = [m[0] - o1[0], m[1] - o1[1]]
        v_abs = dist(v,[0,0])
        w = [v[1], -v[0]]
        w_abs = dist(w,[0,0])
        n = [w[0]/w_abs, w[1]/w_abs]
        l = math.sqrt(1 - v_abs**2)
        p1 = [m[0] + l*n[0], m[1] + l*n[1]]
        p2 = [m[0] - l*n[0], m[1] - l*n[1]]
    return p1, p2
err = 1.0e-6
while True:
    n = int(input())
    if n == 0:
        break
    p = []
    for i in range(n):
        p.append(list(map(float, input().split(","))))
    ans = 1
    for i in range(n - 1):
        for j in range(i + 1, n):
            p1, p2 = intersection(p[i], p[j])
            cnt1 = 0
            cnt2 = 0
            for k in range(n):
                if p1[0] and dist(p1, p[k]) <= 1 + err:
                    cnt1 += 1
                if p2[0] and dist(p2, p[k]) <= 1 + err:
                    cnt2 += 1
            ans = max([ans, cnt1, cnt2])
    print(ans)
n,m,X,Y = input().split()
x = list(map(int,input().split()))
y = list(map(int,input().split()))
x.append(X)
y.append(Y)
print(max(x)<min(y)?"No war":"War")

### FIXED CODE ###

n,m,X,Y = map(int,input().split())
x = list(map(int,input().split()))
y = list(map(int,input().split()))
x.append(X)
y.append(Y)
if max(x)<min(y):
    print("No War")
else:
    print("War")
k = input()
s = int(input())
 
if len(k) <= k:
  print(s)
  
else:
  print(s[:k] + "...")

### FIXED CODE ###

k = int(input())
s = input()
 
if len(s) <= k:
  print(s)
  
else:
  print(s[:k] + "...")
N = input(int())
ans = 1
i = []

list = [i for i in input().split()]

for a in range(N-1):
  ans = ans * i[a]

if ans > 10**18:
    ans = -1

print(ans)

### FIXED CODE ###

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

ans = 1

if 0 in a:
    print("0")
    exit()

for i in a:
    ans *= i

    if ans > 10**18:
        print("-1")
        exit()
        
print(ans)
import math
N=int(input())

import math
factN=math.factorial(N)
count=0

factor = []
tmp = int(math.sqrt(factN)) + 1
for num in range(2,tmp):
    while factN % num == 0:
            factN //= num
            factor.append(num)

factor_set=list(set(factor))

p=1
for x in factor_set:
    p*=(factor.count(x)+1)
    
    
print(factor)
print(p)

### FIXED CODE ###

def pfn(N):
    factor=[]
    N=int(N)
    if N==1:
        return []
    else:
        for num in range(2, N+1):
            while N % num==0:
                N //=num
                factor.append(num)
        return factor
            
N=int(input())
factor=[]
for i in range(1, N+1):
    factor+=pfn(i)
    
p=1
factor_set=list(set(factor))
for x in factor_set:
    p*=factor.count(x)+1
    
print(p%(10**9+7))
i=int(intput())
print(i*i)


### FIXED CODE ###

i=int(input())
print(i*i)
n = input()
n1 = int(n)
n2 = int(sum(list(n)))

if n1 % n2 == 0:
  print("YES")
else:
  print("No")

### FIXED CODE ###

n = input()
n1 = int(n)
n2 = int(sum([int(v) for v in list(n)]))

if n1 % n2 == 0:
  print("Yes")
else:
  print("No")
o=list(input())
e=list(input())+[""]
n=max(len(o),len(e))
for i in range(n):
  print(o[i],end="")
  print(e[i],end="")

### FIXED CODE ###

o=list(input())
e=list(input())+[""]
for x,y in zip(o,e):print(x+y,end="")
N, A, B, C = map(int, input().split(' '))
L = [int(input()) for i in range(N)]
# 上限
MAX = 10 ** 9
#再帰関数
def dfs(cur, a, b, c):
  if cur == N:
    return abs(a - A) + abs(b - B) + abs(c - C) - 30 if min(a, b, c) > 0 else MAX
  ret0 = dfs(cur + 1, a, b, c)
  ret1 = dfs(cur + 1, a + l[cur], b, c) + 10
  ret2 = dfs(cur + 1, a, b + l[cur], c) + 10
  ret3 = dfs(cur + 1, a, b, c + l[cur]) + 10
  print(ret0,ret1,ret2,ret3)
  return min(ret0,ret1,ret2,ret3)
print(dfs(0, 0, 0, 0))

### FIXED CODE ###

N, A, B, C = map(int, input().split(' '))
L = [int(input()) for i in range(N)]
# 上限
MAX = 10 ** 9
#再帰関数
def dfs(cur, a, b, c):
  if cur == N:
    return abs(a - A) + abs(b - B) + abs(c - C) - 30 if min(a, b, c) > 0 else MAX
  ret0 = dfs(cur + 1, a, b, c)
  ret1 = dfs(cur + 1, a + L[cur], b, c) + 10
  ret2 = dfs(cur + 1, a, b + L[cur], c) + 10
  ret3 = dfs(cur + 1, a, b, c + L[cur]) + 10
  return min(ret0,ret1,ret2,ret3)
print(dfs(0, 0, 0, 0))
x=(input())
print(x**3)

### FIXED CODE ###

x=int(input())
print(x**3)
n,k = map(int,input().split())
ls = []

for i in range(n):
    a,b = [int(i) for i in input().split()]
    tmp = [a] * b
    ls.append(tmp)

ls = sum(ls,[])
ls.sort(k-1)
print(ls)

### FIXED CODE ###

n,k = map(int,input().split())
ls = []

for i in range(n):
    a,b = [int(i) for i in input().split()]
    ls.append([a,b])

ls.sort()
for a,b in ls:
    if b >= k:
        print(a)
        break
    else:
        k -= b
import numpy as np

S = input()
 
MOD = 10 ** 9 + 7
N = 13
 
DP = np.zeros(N)
 
# 初期値
DP[0] = 1
digit = 1
 
# 0 -> 5 -> ?5 -> ??5 -> ...に対する余りがどこになるかを更新していく
for i in range(len(S) - 1, -1, -1):
    nextDP = np.zeros(N)
 
    if S[i] == "?":
        for k in range(10):
            for j in range(N):
                nextDP[(k * digit + j) % N] += DP[j]
                nextDP[(k * digit + j) % N] %= MOD
    else:
        k = int(S[i])
        for j in range(N):
            nextDP[(k * digit + j) % N] += DP[j]
            nextDP[(k * digit + j) % N] %= MOD
 
    digit *= 10
    digit %= N
    DP = nextDP
 
print(int(DP[5]))
 
 

### FIXED CODE ###

S = input()
 
MOD = 10 ** 9 + 7
N = 13
 
DP = [0] * N
 
# 初期値
DP[0] = 1
digit = 1
 
# 0 -> 5 -> ?5 -> ??5 -> ...に対する余りがどこになるかを更新していく
for i in range(len(S) - 1, -1, -1):
    nextDP = [0] * N
 
    if S[i] == "?":
        for k in range(10):
            for j in range(N):
                nextDP[(k * digit + j) % N] += DP[j]
                nextDP[(k * digit + j) % N] %= MOD
    else:
        k = int(S[i])
        for j in range(N):
            nextDP[(k * digit + j) % N] += DP[j]
            nextDP[(k * digit + j) % N] %= MOD
 
    digit *= 10
    digit %= N
    DP = nextDP[:]
 
print(DP[5])
 
"""
??2??5

"""
N_K=list(map(int,input().split()))
N=N_K[0]
K=N_K[1]
cost=list(map(int,input().split()))
f_inf=float('inf')
answers=[f_inf for i in range(N)]
answers[0]=0
for i in range(0,N):
	if i+K<=N-1:
		for j in range(0,K+1):
			answers[i+j] = min(answers[i+j]
			,(answers[i]+abs(cost[i]-cost[i+j])))
	elif K>=N:
		for j in range(0,N-i):
			answers[i+j] = min(answers[i+j]
			,(answers[i]+abs(cost[i]-cost[i+j])))
	else:
		for j in range(0,N-K-1):
			answers[i+j] = min(answers[i+j]
			,(answers[i]+abs(cost[i]-cost[i+j])))
print(answers[N-1])

### FIXED CODE ###

N_K=list(map(int,input().split()))
N=N_K[0]
K=N_K[1]
cost=list(map(int,input().split()))
answers=[0,abs(cost[1]-cost[0])]
if K==1:
	S=0
	for i in range(N-1):
		S += abs(cost[i]-cost[i+1])
	print (S)
else:
	for i in range(2,N):
		comp=[]
		if i<K:
			comp=[answers[i-j]+abs(cost[i]-cost[i-j]) for j in range(1,i+1)]
			answers.append(min(comp))
		else:
			comp=[answers[i-j]+abs(cost[i]-cost[i-j]) for j in range(1,K+1)]
			answers.append(min(comp))			
	print(answers[-1])
N=int(input())
X=input()

k=0
for i in range(N):
  if X[i]=="1":
    k+=1

A=int(X,2)
#apは0->1の時の一回目の変換の値。
ap=A%(k+1)
am=A%(k-1)

popc_list=[-1]*(k+3)

def F(num):
  #print(str(num)+"called")
  if num==0:
    return 0
  if popc_list[num]!=-1:
    return popc_list[num]
  
  popc=0
  for s in bin(num):
    if s == "1":
      popc+=1
      
  popc_list[num]=F(num%popc)+1
  return popc_list[num]
  

for i in range(N):
  if X[i] == "0":
    print(F((ap+pow(2,N-1-i,k+1))%(k+1))+1)
  else:
    print(F((am-pow(2,N-1-i,k-1))%(k-1))+1)
"""
print(popc_list)
print(k)
"""

### FIXED CODE ###

N=int(input())
X=input()

k=0
for i in range(N):
  if X[i]=="1":
    k+=1

A=int(X,2)
#apは0->1の時の一回目の変換の値。
ap=A%(k+1)

am=100
if k != 1:
  am=A%(k-1)

popc_list=[-1]*(k+3)

def F(num):
  #print(str(num)+"called")
  if num==0:
    return 0
  if popc_list[num]!=-1:
    return popc_list[num]
  
  popc=0
  for s in bin(num):
    if s == "1":
      popc+=1
      
  popc_list[num]=F(num%popc)+1
  return popc_list[num]
  

for i in range(N):
  if X[i] == "0":
    print(F((ap+pow(2,N-1-i,k+1))%(k+1))+1)
  else:
    if k == 1:
      print(0)
      continue
    print(F((am-pow(2,N-1-i,k-1))%(k-1))+1)
"""
print(popc_list)
print(k)
"""