Harryxun/stf_run huggingface dataset:
import math

A,B,Q = map(int, input().split())
S=[0]*A
T=[0]*B
for i in range(A):
  S[i] = int(input())
for i in range(B):
  T[i] = int(input())
S.append(10**11)
S.insert(0,(-1)*(10**11))
T.append(10**11)
T.insert(0,(-1)*(10**11))
for i in range(Q):
  x = int(input())
  floor = 0
  ceil = len(S)-1
  while ceil-floor > 1:
    half = math.floor((floor+ceil)/2)
    s = S[half]
    if s < x:
      floor = half
    elif x < s:
      ceil = half
    else:
      floor = half
      ceil = half+1
  nearest_x_S = [S[floor]-x, S[ceil]-x]
        
  floor = 0
  ceil = len(S)-1
  while ceil-floor > 1:
    half = math.floor((floor+ceil)/2)
    t = T[half]
    if t < x:
      floor = half
    elif x < t:
      ceil = half
    else:
      floor = half
      ceil = half+1
  nearest_x_T = [T[floor]-x, T[ceil]-x]
  
  ans_cand = []
  for x_S in nearest_x_S:
    for x_T in nearest_x_T:
      if x_S*x_T > 0:
        ans_cand.append(max(abs(x_S),abs(x_T)))
      else:
        ans_cand.append(abs(x_S)+abs(x_T)+min(abs(x_S),abs(x_T)))
  print(int(min(ans_cand)))
  
  


### FIXED CODE ###

mod = 1000000007
eps = 10**-9
inf = 10**15


def main():
    import sys
    from bisect import bisect_left
    input = sys.stdin.buffer.readline

    A, B, Q = map(int, input().split())
    S = [-inf]
    for _ in range(A):
        S.append(int(input()))
    S.append(inf)
    T = [-inf]
    for _ in range(B):
        T.append(int(input()))
    T.append(inf)

    for _ in range(Q):
        x = int(input())
        i = bisect_left(S, x)
        j = bisect_left(T, x)
        ans = []
        ans.append(x - S[i-1] + abs(S[i-1] - T[j-1]))
        ans.append(x - S[i-1] + abs(S[i-1] - T[j]))
        ans.append(x - T[j-1] + abs(T[j-1] - S[i-1]))
        ans.append(x - T[j-1] + abs(T[j-1] - S[i]))
        ans.append(S[i] - x + abs(S[i] - T[j-1]))
        ans.append(S[i] - x + abs(S[i] - T[j]))
        ans.append(T[j] - x + abs(T[j] - S[i-1]))
        ans.append(T[j] - x + abs(T[j] - S[i]))
        print(min(ans))


if __name__ == '__main__':
    main()
a = input()
if 'A' in a and 'B' in a:
    print("Yes")
else:
    print("No")
--------------------------------
n, a, b = map(int, input().split())
period = a+b
times = n//period
k = n%period
n =  a if k >a else k
print(times*a + n)
---------------------------
a, b = [int(x) for x in input().split()]
 
if (b < a):
    temp = b
    b = a
    a = temp
 
 
x = 1
while True:
    if (int(x*0.08) == a and int(x*0.1) == b):
        print(x)
        break
    else:
        if (x > 1500):
            print(-1)
            break
        else:
            x += 1

1, 2 and 3
------------------------
s = input()
q = int(input())
qs = [input().split() for i in range(q)]
n = False
left= right = ""
for operation in qs:
    if operation[0] == '1':
        n = not n
    if operation[0] == '2':
        t , f, c = operation
        f = int(f)
        if n:
            f = 1 if f != 1 else 2
        if f == 1:
            left=c+left
        elif f == 2:
            right+=c
s = left+s+right
print(s[::-1] if n else s)

### FIXED CODE ###

s = input()
q = int(input())
qs = [input().split() for i in range(q)]
n = False
left= right = ""
for operation in qs:
    if operation[0] == '1':
        n = not n
    if operation[0] == '2':
        t , f, c = operation
        f = int(f)
        if n:
            f = 1 if f != 1 else 2
        if f == 1:
            left=c+left
        elif f == 2:
            right+=c
s = left+s+right
print(s[::-1] if n else s)
sum = 0
while 1:
   x = raw_input()
   sum = sum + 1
   if x == " 0 ":
      break
for i in range(0,sum):
   print 'Case %s: %s' %(i, x)

### FIXED CODE ###

sum = 0
while 1:
   x = raw_input()
   sum = sum + 1
   if x == '0':
      break
   print 'Case %s: %s' %(sum, x)
n = int(input())
l = []
for _ in range(n):
  x,y = map(int, input().split())
  l.append([x+y,x-y])
l.sort()

temp = l[0][1]
count = n
i = 1
for i in range(1,n):
  if temp <= l[i][1]:
    pass
  else:
    temp = min(temp,l[i][1])
    count -= 1
print(count)

### FIXED CODE ###

h = int(input())
w = int(input())
n = int(input())

m = max(h,w)
a = n // m
b = n % m
if b == 0:
  print(a)
else:
  print(a+1)
import fractions

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

print(fractions.ceil(h,a))

### FIXED CODE ###

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

if n[0] % n[1] != 0:
  t = 1

print(n[0] // n[1] + t)
N=int(input())
V = list(int(i) for i in input().split()) 
C = list(int(i) for i in input().split()) 
S=[]
for i in range(N):
	S.append(V[i]-C[i])
for i in range(N):
	if S[i]>0:
		ans=ans+S[i]
print(ans)

### FIXED CODE ###

N=int(input())
V = list(int(i) for i in input().split()) 
C = list(int(i) for i in input().split()) 
S=[]
ans=0
for i in range(N):
    S.append(V[i]-C[i])
for i in range(N):
	if S[i]>0:
		ans=ans+S[i]
print(ans)
# AOJ 0517: Longest Steps
# Python3 2018.6.30 bal4u

while True:
	n, k = map(int, input().split())
	if n == 0: break
	c = [0]*(n+1)
	f = 0;
	for i in range(k):
		a = int(input())
		if a == 0: f = 1
		else: c[a] = 1
	ans = w0 = w = 0
	for i in range(1, n+1):
		if c[i]: w += 1
		elif w > 0:
			if w0 + w + f > ans: ans = w0 + w + f
			w0 = w if f and c[i+1] else 0
			w = 0
	if w0 + w + f > ans: ans = w0 + w + f
	print(ans)


### FIXED CODE ###

# AOJ 0517: Longest Steps
# Python3 2018.6.30 bal4u

while True:
	n, k = map(int, input().split())
	if n == 0: break
	c = [0]*(n+2)
	f = 0;
	for i in range(k):
		a = int(input())
		if a == 0: f = 1
		else: c[a] = 1
	ans = w0 = w = 0
	for i in range(1, n+1):
		if c[i]: w += 1
		elif w > 0:
			if w0 + w + f > ans: ans = w0 + w + f
			w0 = w if f and c[i+1] else 0
			w = 0
	if w0 + w + f > ans: ans = w0 + w + f
	print(ans)
l = len(colors)
count1 = 0
for i in range(l):
	if int(colors[i]) == (i % 2):
		count1 += int(colors[i])
print(min(count1, l-count1))

### FIXED CODE ###

colors = input()
l = len(colors)
count1 = 0
for i in range(l):
	if int(colors[i]) == (i % 2):
		count1 += 1
print(min(count1, l-count1))
#!/usr/bin/env python3
n = int(input())
h = list(map(int, input().split()))
streak = 0
history = []
if n == 1:
    print(0)
else:
    for i in range(n-1):
        if h[i] >= h[i+1]:
            streak += 1
        else:
            history.append(streak)
            streak = 0
    print(max(max(history), streak))


### FIXED CODE ###

#!/usr/bin/env python3
n = int(input())
h = list(map(int, input().split()))
streak = 0
history = []
for i in range(n-1):
    if h[i] >= h[i+1]:
        streak += 1
    else:
        history.append(streak)
        streak = 0
history.append(streak)
print(max(history))
while 1:
    n = input()
    if n == 0: break
    sums = []
    a, b, c = 0, 0, input()
    for i in xrange(n - 1):
        sums.append(a + b + c)
        a, b, c = b, c, input()
    print max(sums)

### FIXED CODE ###

while 1:
    n = input()
    if n == 0: break
    sums = [-100000]
    for i in xrange(n):
        num = input()
        sums.append(max(sums[-1] + num, num))
    print max(sums)
import sys
s = list(str(input().rstrip()))
s = list(map(int,s))

change = 0
cflag=[]
for i in range(len(s)-1):
  if s[i]!=s[i+1]:
    change+=1
    cflag+=[i+1]
if change==0:
  print(len(s))
  sys.exit()
elif change ==1:
  ones = s.count(1)
  zeros = s.count(0)
  print(max(ones,zeros))
  sys.exit()
elif change ==2:
  print(max(1+cflag[0],1+len(s)-cflag[1]))
  sys.exit()
  
0/0
t=[]
for i in range(len(s)):
  if s[i]==0:t+=[1]
  else: t+=[0]
while True:
  firs=s.index(1)
  last=len(s)-1-s[::-1].index(1)
  print(firs,last)
  break

### FIXED CODE ###

s = input()

cflag=[]
for i in range(len(s)-1):
  if s[i]!=s[i+1]:
    cflag+=[i+1]
  
ans = len(s)
for flag in cflag:
  ans = min(ans,max(flag,len(s)-flag) )
print(ans)
n = input()
   
S = range(1, 14)
H = range(1, 14)
C = range(1, 14)
D = range(1, 14)
   
for i in range(0, n):
   mk = raw_input()split()
   num = int, raw_input()split()
      if mk == 'S':
         S[r-1] = 0
      elif mk == 'H':
         S[r-1] = 0
      elif mk == 'C':
         S[r-1] = 0
      elif mk == 'D':
         S[r-1] = 0
   
for i in S:
   if S[i] != 0:
      print 'S'+str(S[i])
  
for i in H:
   if S[i] != 0:
      print 'H'+ str(H[i])
  
for i in C:
   if S[i] != 0:
      print 'C'+str(C[i])
  
for i in D:
   if S[i] != 0:
      print 'D'+str(D[i])

### FIXED CODE ###

n=input()
  
s=range(1,14)
h=range(1,14)
c=range(1,14)
d=range(1,14)
   
for i in range(n):
   m, k=raw_input().split()
   if m == 'S':
      s[int(k)-1] = 0
   elif m == 'H':
      h[int(k)-1] = 0
   elif m == 'C':
      c[int(k)-1] = 0
   elif m == 'D':
      d[int(k)-1] = 0
  
for i in range(0, 13):
   if s[i] != 0:
      print 'S '+str(s[i])
  
for i in range(0, 13):
   if h[i] != 0:
      print 'H '+str(h[i])
  
for i in range(0, 13):
   if c[i] != 0:
      print 'C '+str(c[i])
  
for i in range(0, 13):
   if d[i] != 0:
      print 'D '+str(d[i])
#D-atcoderくんと変なジャンケン
s=input()
import collections
S=dict(collections.Counter(s))
a=S["p"]
b=S["g"]
x=((a+b)//2)
print(x-a)

### FIXED CODE ###

#D-atcoderくんと変なジャンケン
s=input()+"g"+"p"
import collections
S=dict(collections.Counter(s))
a=S["p"]-1
b=S["g"]-1
x=((a+b)//2)
print(x-a)
l = [int(input()) for _ in range(5)]
ans = 0
for j in range(5):
    if 0 < l[j] % 10:
        ans += (l[j] // 10 + 1) * 10
    else:
        ans += l[j]
l %= 10
ans -= min(l)
ans += 10
print(ans)


### FIXED CODE ###

l = [int(input()) for _ in range(5)]
ans = 0
m = 0
for i in l:
    if i % 10 != 0:
        p = 10 - i % 10
    else:
        p = 0
    ans += i + p
    m = max(m, p)
print(ans - m)
N=int(input())
A=list(map(int,input().split()))
B=[]
C=[]
for i in range(N):
    if A[i]<=0:
        B.append(-A[i])
    else:
        C.append(A[i])
b=min(B)
c=min(C)
d=min(b,c)
if B==[]:
    print(sum(C))
elif len(B)%2==0:
       print(sum(B)+sum(C))
else:
       print(sum(B)+sum(C)-2*c)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
B=[]
C=[]
for i in range(N):
    if A[i]<=0:
        B.append(-A[i])
    else:
        C.append(A[i])
if len(B)%2==0:
       print(sum(B)+sum(C))
else:
        if C==[]:
            print(sum(B)+sum(C)-2*min(B))
        else:
            print(sum(B)+sum(C)-2*min(min(B),min(C)))
n=int(input())
dat=list(map(int, input().split()))
      
re = 0

while (True):
       for e in dat:
            if e%2==1:
                break
            else:
                e = e/2
         re = re+1

print(re)

### FIXED CODE ###

import sys

def main():
    N = int(input())
    A = [int(_) for _ in input().split()]

    t = 0
    while True:
        for i in range(N):
            if A[i] % 2 == 0:
                A[i] //= 2
            else:
                print(t)
                sys.exit()
        t += 1

main()
A=[list(map(int,input().split())) for i in range(3)]
AB=[[0 for i in range(3)] for j in range(3)]
N=int(input())
for i in range(N):
    x=input()
    for j in range(3):
        for k in range(3):
            if A[i][j]==x:
                AB[i][j]=1
c=1
for i in range(3):
    if A[i][0]*A[i][1]*A[i][2]==1:
        c=0
        print("Yes")
        break
    if A[0][i]*A[1][i]*A[2][i]==1:
        c=0
        print("Yes")
        break
    if A[0][0]*A[1][1]*A[2][2]==1:
        c=0
        print("Yes")
        break
    if A[0][2]*A[1][1]*A[2][0]==1:
        c=0
        print("Yes")
        
if c==1:
    print("No")

### FIXED CODE ###

A=[list(map(int,input().split())) for i in range(3)]
AB=[[0 for i in range(3)] for j in range(3)]
N=int(input())
for i in range(N):
    x=int(input())
    for j in range(3):
        for k in range(3):
            if A[j][k]==x:
                AB[j][k]=1
c=1
for i in range(3):
    if AB[i][0]*AB[i][1]*AB[i][2]==1:
        c=0
        break
    if AB[0][i]*AB[1][i]*AB[2][i]==1:
        c=0
        break
    if AB[0][0]*AB[1][1]*AB[2][2]==1:
        c=0
        break
    if AB[0][2]*AB[1][1]*AB[2][0]==1:
        c=0
        break
        

if c==1:
    print("No")
else:
  	print("Yes")
import math
n = int(input())

print(math.factorial(n) % (10**9+7)

### FIXED CODE ###

import math
n = int(input())

print(math.factorial(n) % (10**9+7))
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 numpy as np
import math
A, B, C, D = list(map(int, input().split()))

def lcm(x, y):
    return (x * y) / math.gcd(x, y)
E = lcm(C, D)

u = np.arange(A,B+1)
count_U = len(u)
u_c = [i for i in u if i % C == 0]
count_C = len(u_c)
u_d = [i for i in u if i % D == 0]
count_D = len(u_d)
u_e = [i for i in u if i % E == 0]
count_E = len(u_e)

answer = count_U - (count_C + count_D -count_E)
print(answer)


### FIXED CODE ###

from fractions import gcd
 
a, b, c, d = map(int, input().split())
a = a - 1
 
def main():
    cd = c * d // gcd(c, d)
    print(b - a - f(c) - f(d) + f(cd))
 
def f(x):
    return b // x - a // x
 
main()
dict={}
output=[]

iteration=int(input())
for _ in range(iteration):
    item=input()
    
    if dict.get(item) is None:
        dict[item]=0 
    dict[item]+=1 
max_val=max(dict.values())
for i in range(iteration):
    max_key=max(dict,key=dict.get)
    if(max_val!=dict[max_key]):
        break
    output.append(max_key)
    
    del dict[max_key]
output.sort()
print('\n'.join(output))

### FIXED CODE ###


from sys import stdin
def read():
    return stdin.readline().strip()

dict={}
output=[]

iteration=int(read())

max_val=-1

for _ in range(iteration):
    item=read()
    
    if dict.get(item) is None:
        dict[item]=0 
    dict[item]+=1 
    max_val = max(dict[item],max_val)
#max_val=max(dict.values())
for k,v in dict.items():
    
    if(max_val==v):
        output.append(k)
    
    
output.sort()
print('\n'.join(output))
import math

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

n = int(input())
l = make_divisors(n)

ans = 999999999999999999
for i in range(0, len(l), 2):
  a = l[i]
  b = l[i+1]
  ans = min(ans,(a+b-2))
  
print(ans)


### FIXED CODE ###

import math

n = int(input())
ans = n-1

for i in range(1, math.floor(math.sqrt(n))+1):
  if n % i == 0:
    ans = min(ans, (i+(n/i)-2))
      
print(int(ans))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

A, B, N = MAP()

left, right = 0, N

def f(x):
    return int(A*x/B) - A*int(x/B)


# while right-left > 1:
#     mid1 = (left + right)*1// 3
#     mid2 = (left + right)*2// 3

#     if f(mid1) < f(mid2):
#         if left == mid1:
#             break
#         left = mid1
#     else:
#         if right == mid1:
#             break
#         right = mid2

# ans = f(left)
# for i in range(left, right+1):
#     ans = max(ans, f(i))
# print(ans)
# ans = 0
# # whilefor i in range(1, N+1):
# #     ans = max(ans, f(i))
# # print(ans)

# x = N//2
# if f(x) <= f(x)
# direc = "R"

ans = 0
if B > N:
    ans = f(N)
else:
    ans = f(i*B-1)

print(ans)

### FIXED CODE ###

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

A, B, N = MAP()

left, right = 0, N

def f(x):
    return int(A*x/B) - A*int(x/B)


# while right-left > 1:
#     mid1 = (left + right)*1// 3
#     mid2 = (left + right)*2// 3

#     if f(mid1) < f(mid2):
#         if left == mid1:
#             break
#         left = mid1
#     else:
#         if right == mid1:
#             break
#         right = mid2

# ans = f(left)
# for i in range(left, right+1):
#     ans = max(ans, f(i))
# print(ans)
# ans = 0
# # whilefor i in range(1, N+1):
# #     ans = max(ans, f(i))
# # print(ans)

# x = N//2
# if f(x) <= f(x)
# direc = "R"

ans = 0
if B > N:
    ans = f(N)
else:
    ans = f(B-1)

print(ans)
A, B, C, K = map(int, input().split())

if A > K:
    print(K)
elif A+B >= K:
    print(A)
else:
    print(A - (K-(A+B)))


### FIXED CODE ###

S = input()
T = input()[:-1]

if S == T:
    print("Yes")
else:
    print("No")
import bisect


n, x = map(int, input().split())
a = list(sorted(map(int, input().split())))
if x == sum(x):
    print(n)
else:
    acc = [0 for i in range(n)]
    acc[0] = a[0]
    for i in range(1, n):
        acc[i] += a[i - 1] + a[i]
    index = bisect.bisect_right(acc, x)
    if index == n:
        print(index - 1)


### FIXED CODE ###

n, x = map(int, input().split())
a = list(sorted(map(int, input().split())))
if x == sum(a):
    print(n)
else:
    acc = 0
    for i in range(n):
        acc += a[i]
        if acc > x:
            break
    if i == n:
        print(n - 1)
    else:
        print(i)
import math

a,b,c = input().split()

ans = ""

if(c -a - b < 0 and 4*a*b>(c-a-b)*)*(c-a-b)):
    ans = "Yes"
else:
    ans = "No"

print(ans)



### FIXED CODE ###

import math

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

if((4*a*b)<(c-a-b)*(c-a-b) and c-a-b>0):
    ans = "Yes"
else:
    ans = "No"

print(ans)
import sys
input = sys.stdin.readline.rstrip()
def main():
    moji=input()
    cycle=int(input())
    flont_or_back=0
    flont=""
    back=""
    for i in range(cycle):
        line=input()
        if line[0]=="1":
            flont_or_back+=1
        else:
            fi=line[2]
            ci=line[4]
            if flont_or_back%2==0:
                if fi=="1":
                    flont=ci+flont
                else:
                    back+=ci
            else:
                if fi=="1":
                    back+=ci
                else:
                    flont=ci+flont
    moji=flont+moji+back
    if flont_or_back%2==0:
        print(moji)
    else:
        print(moji[::-1])
    

if __name__ == '__main__':
    main() 
  

### FIXED CODE ###

def main():
    moji=input()
    cycle=int(input())
    flont_or_back=0
    flont=""
    back=""
    for i in range(cycle):
        line=input()
        if line[0]=="1":
            flont_or_back+=1
        else:
            fi=line[2]
            ci=line[4]
            if flont_or_back%2==0:
                if fi=="1":
                    flont=ci+flont
                else:
                    back+=ci
            else:
                if fi=="1":
                    back+=ci
                else:
                    flont=ci+flont
    moji=flont+moji+back
    if flont_or_back%2==0:
        print(moji)
    else:
        print(moji[::-1])
    

if __name__ == '__main__':
    main()
n,d = map(int,input().split())
x = [list(map(int,input().split())) for a in range(n)]
c = 0
 
for i in range(n-1):
  for j in range(i+1,n):
    b = 0
    for m in range(d):
      b += (int(x[i][m])-int(x[j][m]))**2
    if (b**0.5)　== float(int(b**0.5)):
      c += 1
      
print(c)

### FIXED CODE ###

n,d = map(int,input().split())
w = [list(map(int,input().split())) for a in range(n)]
c = 0
 
for i in range(n-1):
  for j in range(i+1,n):
    b = 0
    for m in range(d):
      b += (w[i][m]-w[j][m])**2
    if (b**0.5)==float(int(b**0.5)):
      c += 1
      
print(c)
#! /usr/bin/python
import sys
if sys.version_info[0] >= 3: raw_input = input

def insertion_sort(a,g):
  global cnt
  for i in range(g, len(a)):
    v = a[i]
    j = i - g
    while j >= 0 and a[j] > v:
      a[j+g] = a[j]
      j = j - g
      cnt += 1
      a[j+g] = v

def shell_sort(a):
  global cnt
  cnt = 0
  g = []
  h = 1
  while h <= len(a):
    g.append(h)
    h = 3*h + 1
  g.reverse()
  m = len(g)
  print(m)
  print(''.join(map(str, g)))
  for i in range(m):
    insertion_sort(a, g[i])

a = [int(raw_input()) for i in range(raw_input())]
shell_sort(a)
print(cnt)
for e in a: print(e)


### FIXED CODE ###

def insertionSort(A, n, g):
    global cnt
    for i in range(g, n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j+g] = A[j]
            j = j - g
            cnt += 1
        A[j+g] = v
 
n = int(input())
A = [int(input()) for i in range(n)]
 
cnt = 0
G = [1]
for i in range(99):
    if n < 1 + 3*G[-1]:
        break
    G.append(1 + 3*G[-1])
m = len(G)
G.reverse()
for i in range(m):
    insertionSort(A, n, G[i])
 
print(m)
print(*G)
print(cnt)
print(*A, sep='\n')
import math as m

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

gstackl = [0]
gstackr = [0]

ans = 0

for i in range(0, n):
	gstackl.append(m.gcd(gstackl[i], al[i]))

for i in reversed(range(1, n)):
	gstackr = [m.gcd(gstackr[0], al[i])] + gstackr

gstackr.append(0)

#print(gstackl)
#print(gstackr)

for i in range(n):
	l = gstackl[i]
	r = gstackr[i]
	#print("{} {}".format(l, r))
	a = m.gcd(l, r)
	#print(a)
	if a > ans:
		ans = a

print(ans)

### FIXED CODE ###

import fractions as m

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

gstackl = [0]*n
gstackr = [0]*n

ans = 0

for i in range(1, n):
	gstackl[i] = m.gcd(gstackl[i-1], al[i-1])
	gstackr[n-i-1] = m.gcd(gstackr[n-i], al[n-i])

#print(gstackl)
#print(gstackr)

for i in range(n):
	l = gstackl[i]
	r = gstackr[i]
	#print("{} {}".format(l, r))
	a = m.gcd(l, r)
	#print(a)
	if a > ans:
		ans = a

print(ans)
str_original = input()
N = len(str_original)
loop = floor(N/2)

count = 0
for i in range(loop):
  if str_original[i] != str_original[N-i]:
     count+= 1
      
return count

### FIXED CODE ###

str_original = input()
N = len(str_original)
loop = int(N/2)
 
count = 0
for i in range(loop):
  if str_original[i] != str_original[(N-1)-i]:
     count+= 1
      
print(count)
print(sum(list(range(int(input())))))

### FIXED CODE ###

N = int(input())
print(N*(N-1)//2)
x = int(input())
li = list(range(2,x+1))
ans = [1]
n = 2
while li[0]**n < x:
    for i in range(x-1):
        if li[i]**n > x:
            ans.append(li[i-1]**n)
            break
    n += 1
print(max(ans))

### FIXED CODE ###

x = int(input())
if x == 1:
    print(1)
    exit()
li = list(range(2,x+1))
ans = [1]
n = 2
while li[0]**n < x:
    for i in range(x-1):
        if li[i]**n > x:
            ans.append(li[i-1]**n)
            break
    n += 1
print(max(ans))
N = int(input())
X = input()
x = int(X, 2)
zero_pop = X.count('1') + 1
one_pop = X.count('1') - 1
zero_mod = x % zero_pop
one_mod = x % one_pop

def popcount(n):
    return bin(n).count('1')
def f_count(n):
    ans = 0
    while n != 0:
        n %= popcount(n)
        ans += 1
    return ans
for i in range(N):
    if X[i] == '1' and X.count('1') == 1:
        print(0)
        continue
    if X[i] == '1':
        x = (one_mod - 2**(N-1 -i) % one_pop) % one_pop
    else:
        x = (2**(N-1 -i) % zero_pop + zero_mod) % zero_pop
    print(f_count(x) + 1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)
N = int(input())
X = input()
zero_pop = X.count('1') + 1
one_pop = X.count('1') - 1
one_mod, zero_mod = 0, 0

for b in X:
    if one_pop != 0:
        one_mod = (one_mod * 2 + int(b)) % one_pop
    zero_mod = (zero_mod * 2 + int(b)) % zero_pop

pop = {0:0}
def popcount(n):
    if n in pop:
        return pop[n]
    pop[n] = popcount(n // 2) + n % 2
    return pop[n]
memo = {0:0}
def f_count(n):
    if n in memo:
        return memo[n]
    memo[n] = f_count(n % popcount(n)) + 1
    return memo[n]
one_p = {0:1}
def one_pow(n):
    if n in one_p:
        return one_p[n]
    one_p[n] = one_pow(n - 1) * 2 % one_pop
    return one_p[n]
zero_p = {0:1}
def zero_pow(n):
    if n in zero_p:
        return zero_p[n]
    zero_p[n] = zero_pow(n - 1) * 2 % zero_pop
    return zero_p[n]
for i in range(N):
    if X[i] == '1' and one_pop == 0:
        print(0)
        continue
    if X[i] == '1':
        x = one_mod
        x -= one_pow(N-1-i)
        x %= one_pop
    elif X[i] == '0':
        x = zero_mod
        x += zero_pow(N-1-i)
        x %= zero_pop
    
    print(f_count(x) + 1)