Harryxun/stf_run huggingface dataset:
import math

[n, x] = map(int, input().split(" "))
xs = list(map(int, input().split(" ")))

xs.append(x)
xs.sort()
gc = xs[1] - xs[0]

for i in range(1, n):
    gc = math.gcd(gc,  xs[i] - xs[i - 1])

print(gc)

### FIXED CODE ###

def getGcd(num1, num2):
    while True:
        tmp = num1
        num1 = num2 % num1
        num2 = tmp
        if(num1 == 0):
            return tmp

[n, x] = map(int, input().split(" "))
xs = list(map(int, input().split(" ")))

xs.append(x)
xs.sort()

gc = xs[1] - xs[0]

for i in range(1, n + 1):
    gc = getGcd(gc,  xs[i] - xs[i - 1])

print(gc)
#!/usr/bin/env python3
s, t = input().split()
print(t+s)


### FIXED CODE ###

#!/usr/bin/env python3
a, b, c = map(int, input().split())

if a + b + c >= 22:
  print('bust')
else:
  print('win')
str = input()
abc = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z','aa']
i = 0
while abc[i] in str:
    if i <= 26:
        i += 1
    else:
        break

if i < 26:
    print(abc[i])
    
else:
    print("None")

### FIXED CODE ###

str = input()
abc = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z','aa']
i = 0
while abc[i] in str:
    if i < 26:
        i += 1
    else:
        break

if i < 26:
    print(abc[i])

else:
    print("None")
import heapq

N,M = (int(x) for x in input().split())
AB = []
sum = 0

for i in range(N):
    a,b = (int(x) for x in input().split())
    AB.append([a,b])

AB = sorted(AB , key = lambda x : x[1])

for i in range(M):
    if AB[N-i-1][0] <= M-i:
        sum += AB[N-i-1][1]
        AB.pop(N-i-1)

print(sum)
    


### FIXED CODE ###

import heapq

N,M = (int(x) for x in input().split())
AB = []
sum = 0

for i in range(N):
    a,b = (int(x) for x in input().split())
    AB.append([a,b])

AB = sorted(AB , key = lambda x : x[0])
heap = []
j = 0

for i in range(M+1):
    while j<N and AB[j][0] < i+1:
        heapq.heappush(heap,-AB[j][1])
        j += 1

    if len(heap):
        sum += -heapq.heappop(heap)
                           
print(sum)
import math

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

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

middle = math.ceil(max(a) / 2)
oldMiddle = 0
h = middle // 2
rightMin = max(a)

while h > 0:
    cut = 0
    for i in range(n):
        cut += math.ceil(a[i] / middle) - 1
    h = math.ceil(abs(middle - oldMiddle) / 2)
    oldMiddle = middle
    if cut <= k:
        if (middle - h == rightMin):
            break
        middle -= h
    else:
        rightMin = middle
        middle += h

print(middle)

### FIXED CODE ###

import math

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

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

middle = math.ceil(max(a) / 2)
oldMiddle = 0
h = middle // 2
rightMin = max(a)

while h > 0:
    cut = 0
    if middle == 0:
        middle = 1
        break
    for i in range(n):
        cut += math.ceil(a[i] / middle) - 1
    h = math.ceil(abs(middle - oldMiddle) / 2)
    oldMiddle = middle
    if cut <= k:
        if (middle - h == rightMin):
            break
        middle -= h
    else:
        rightMin = middle
        middle += h

print(middle)
n=input()
data=list(map((int, input().split()))
print('%d %d %d' %(min(data), max(data),n=int(input())
data=list(map(int, input().split()))
print('%d %d %d' % (min(data), max(data), sum(data) )) sum(data) )))

### FIXED CODE ###

n=int(input())
data=list(map(int, input().split()))
print('%d %d %d' % (min(data), max(data), sum(data) ))
while True:
    a,b=map(int,raw_input().split("."))
    if a<0:break
    s,s2="",""

#    while a!=0:                                                                        
#       s+=str(a%2)                                                                     
#        a/=2                                                                           
    cnt=0

    while b!=0 and cnt<=4:
        b*=2
	s2+=str(b/10)
        b%=10
        cnt+=1
    s2="0"*4

    if len(s2)<=4:
        print "%08d"%(int(format(a,"b")))
    else:
        print "NA"

### FIXED CODE ###

def convert(x,p):
    if p==12:
	return
    convert(x/2,p+1)
    if p==3:
        ans.append(".")
    ans.append(str(x%2))

while True:
    n=input()
    if n<0:break
    ans=[]
    shift=int(n*16)
    if n==shift/16.0 and shift<4096:
        convert(shift,0)
	print "".join(ans)
    else:
        print "NA"
import sys
sys.setrecursionlimit(2000)
_ = input()
h = list(map(int, input().split()))
inf = float('inf')
dp = [inf] * len(h)

def rec_opt(i):
    if dp[i] < inf:
        return dp[i]
    if i == 0:
        return 0
    elif i ==1:
        return abs(h[0] - h[1])
    else:
        ans = min(inf, rec_opt(i-1) + abs(h[i] - h[i-1]))
        if i > 1:
            ans = min(ans, rec_opt(i-2) + abs(h[i] - h[i-2]))
        dp[i] = ans
    return dp[i]
print(rec_opt(len(h)-1))

### FIXED CODE ###

_ = int(input())
h = list(map(int, input().split()))

opt = [0] * len(h)
opt[1] = abs(h[0]-h[1])

for i in range(2,len(h)):
    A = opt[i-1] + abs(h[i-1] - h[i])
    B = opt[i-2] + abs(h[i-2] - h[i])
    opt[i] = min(A, B)

print(opt[len(h)-1])
import numpy as np

N = int(input())
A = list(map(int, input().split()))

a = np.array(A)
l = int(((N**2)+1)/2)
b = np.tile((1,-1),(1,l))
c = (np.delete(b, 2*l-1, axis=None)).reshape(N,N)
# print(c)
# d = c.reshape(N,N)
inv = 0.5*( np.triu(c) - ( np.tril(c) - np.eye(N) ) )
# g = np.eye(N)
# print(inv)
x = 2*(np.dot(inv,a))
# print(x)
print(1)
# ans = list(map(str, list(map(int, list(x)))))
# print(" ".join(ans))

### FIXED CODE ###

import numpy as np
N = int(input())
A = list(map(int, input().split()))
a = np.array(A)
# l = int(((N*N)+1)/2)
b = []
for i in range(N):
    if i%2==0:
        b.append(1)
    else:
        b.append(-1)
c = np.dot(np.array(b),a)
x = [c]
for j in range(1,N):
    x_j = 2*a[j-1] - x[j-1]
    x.append(x_j)
ans = list(map(str, list(map(int, list(x)))))
print(" ".join(ans))
n = int(input())
l = list(map(int,input().split()))
ans = 0
g = set(l)
m = list(g)
m.sort()
for i in range(n):
  judge = 0
  for j in range(i+1,n):
    for k in range(j+1,n):
      if(m[i]<[j]+[k]):
        ans += 1
      else:
        break
    if(judge==0):
      break
print(ans)


### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
ans = 0
l.sort(reverse=True)
for i in range(n-2):
  for j in range(i+1,n-1):
    for k in range(j+1,n):
      if(l[i]!=l[j])and(l[j]!=l[k])and(l[i]!=l[k])and(l[i]<l[j]+l[k]):
        ans += 1
print(ans)
n,m=map(int,input().split())
s=input()
for i in m:
  a,b=map(int,input().split())
  lan=s[a-1:b]
  print(lan.count("AC"))

### FIXED CODE ###

n,m=map(int,input().split())
s=input()
ACsuu=[0 for i in range(n)]
for i in range(1,n):
  ACsuu[i]=ACsuu[i-1]+(1 if s[i-1:i+1]=="AC" else 0)
for i in range(m):
  a,b=map(int,input().split())
  print(ACsuu[b-1]-ACsuu[a-1])
import bisect

N = int(input())
A = list(map(int,input().split()))

Q = int(input())

A.sort()
B = list(set(A))
X = [[0 for j in range(2)] for i in range(len(B))]
for i in range(len(B)):
  b=bisect.bisect_left(A,B[i])
  c=bisect.bisect_right(A,B[i])
  num = c - b #B[i]の要素数
  X[i][0] = B[i]
  X[i][1] = num

M = [0 for j in range(Q)]
N = [0 for j in range(Q)]
for i in range(Q):
  M[i],N[i] = map(int,input().split())

ans = int()
for i in range(Q):
  x = M[i]
  y = N[i]
  ans = 0
  jg = False
  for j in range(len(B)):
    if X[j][0] == y:
      jg = True
      jgx = j
  for j in range(len(B)):
    if X[j][0] == x:
      X[j][0] = y
      if jg = True:
        X[j][1] += X[jgx][1]
        X[jgx][0] = 0
    ans += X[j][0] * X[j][1]
  print(ans)
  #print(X)
  



### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
BC = [list(map(int,input().split())) for i in range(Q)]
B, C = [list(i) for i in zip(*BC)]
#print(B,C,BC)

dic = {}
for a in A:
  dic[a] = dic.get(a,0) + 1
#print(dic)

ans = sum(A)
for q in range(Q):
  ans = ans + (C[q]-B[q]) * dic.get(B[q],0)
  dic[C[q]] = dic.get(B[q],0) + dic.get(C[q],0)
  dic[B[q]] = 0
  print(ans)
#C - Colorful Leaderboard 
N = int(input())
a = list(map(int,input().split()))

mini = 0
color_list = []
for i in a:
    if (i//400)<8 and ((i//400 in color_list) == False):
        mini += 1
        color_list.append(i//400)

maxi = mini
for j in a:
    if maxi == 8:
        break
    if j >= 3200:
        maxi += 1
if mini == 0:#忘れてた
    mini = 1
print(mini,maxi)

### FIXED CODE ###

r,g,b = map(str,input().split())
list_C = [r,g,b]
num = int(''.join(list_C))
if num%4 == 0:
    print('YES')
else:
    print('NO')
N = int(input())
S = list(map(int, input().split()))
y = 0
for i in range(N):
	if S[i] == "Y":
		y = 1
if y == 0:
	print("Three")
else:
	print("Four")

### FIXED CODE ###

N = int(input())
S = list(input().split())
y = 0
for i in range(N):
	if S[i] == "Y":
		y = 1
if y == 0:
	print("Three")
else:
	print("Four")
matrix = [[], [], []]
for row in matrix:
    for i in range(3):
        row.append(input())
print(matrix[0][0] + matrix[1][1] + matrix[2][2])

### FIXED CODE ###

row1 = input()
row2 = input()
row3 = input()
print(row1[0]+row2[1]+row3[2])
import math
import decimal
decimal.getcontext().prec = 12

#getcontext().prec=20
a,b,h,m=map(int,input().split())
a=decimal.Decimal(a)
b=decimal.Decimal(b)
h=decimal.Decimal(h)
m=decimal.Decimal(m)

#print(a,b,h,m)

ang1=decimal.Decimal(360*(h/12)+30*m/60)
ang2=decimal.Decimal(360*m/60)
ang=decimal.Decimal(abs(ang1-ang2))
#print(ang)
if ang>=180.0:
    ang=ang-180.0

#print(ang)
ans = ((a)**2 + (b)**2 - decimal.Decimal(2.0)*(a)*(b)*decimal.Decimal(math.cos(math.radians(ang))))
ans = (math.sqrt(ans))
#print(math.cos(math.radians(ang)))

print(ans)

### FIXED CODE ###

import math
#import decimal
#decimal.getcontext().prec = 12

#getcontext().prec=20
a,b,h,m=map(int,input().split())
#a=decimal.Decimal(a)
#b=decimal.Decimal(b)
#h=decimal.Decimal(h)
#m=decimal.Decimal(m)

#print(a,b,h,m)

#ang1=decimal.Decimal(360*(h/12)+30*m/60)
#ang2=decimal.Decimal(360*m/60)
#ang=decimal.Decimal(abs(ang1-ang2))
ang1=360*(h/12)+30*m/60
ang2=360*m/60
ang=abs(ang1-ang2)
#print(ang)
if ang>=180.0:
#    ang=ang-180.0
    ang=360.0-ang

#print(ang)
#ans = ((a)**2 + (b)**2 - decimal.Decimal(2.0)*(a)*(b)*decimal.Decimal(math.cos(math.radians(ang))))
ans = a**2 + b**2 - 2.0*a*b*math.cos(math.pi*ang/180.0)
ans = math.sqrt(ans)
#print(math.cos(math.radians(ang)))

print(ans)
while True:
    count_shima=input()
    if count_shima==0: break

    A = [list(map(int,raw_input().split())) for i in xrange(count_shima)]

    A.sort()

    weight=0
    frg=0
    for takara,turi in A:
        weight +=takara
        if turi < weight:
            print "NO"
            frg=1
            break
    if frg==0:
        print "YES"

### FIXED CODE ###

def solve(info):
    have = 0
    for m, w in info:
        have += w
        if m < have:
            return "No"
    return "Yes"

while True:
    shima_count = input()
    if shima_count == 0: break
    info = []
    for i in range(shima_count):
        lu, w = map(int, raw_input().split())
        info.append((w, lu))
    info.sort()
    print solve(info)
n=int(input())
s=input()

def rev(x):
    if x=="S":
        return "W"
    else:
        return "S"

def wolfsheep(xy):
    global n,s
    result=[xy[0],xy[1]]

    for i in range(1,n+1):
        if result[i]=="S":
            if s[i]=="o":
                result.append(result[i-1])
            else:
                result.append(rev(result[i-1]))
        else:
            if s[i]=="o":
                result.append(rev(result[i-1]))
            else:
                result.append(result[i-1])

    if result[0]==result[n] and result[1]==result[n+1]:
        return result
    else:
        return 0

#SWパターン
tmp= wolfsheep("SW")
if tmp!=0:
    print("".join(tmp[:-2]))
    exit()

#SSパターン
tmp= wolfsheep("SS")
if tmp!=0:
    print("".join(tmp[:-2]))
    exit()
#WWパターン
tmp= wolfsheep("WW")
if tmp!=0:
    print("".join(tmp[:-2]))
    exit()
#WSパターン
tmp= wolfsheep("WS")
if tmp!=0:
    print("".join(tmp[:-2]))
    exit()

print(-1)

### FIXED CODE ###

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

def rev(x):
    if x=="S":
        return "W"
    else:
        return "S"

def wolfsheep(xy):
    global n,s
    result=[xy[0],xy[1]]

    for i in range(1,n+1):
        s+=s[0]
        if result[i]=="S":
            if s[i]=="o":
                result.append(result[i-1])
            else:
                result.append(rev(result[i-1]))
        else:
            if s[i]=="o":
                result.append(rev(result[i-1]))
            else:
                result.append(result[i-1])

    if result[0]==result[n] and result[1]==result[n+1]:
        return result
    else:
        return 0

#SWパターン
tmp= wolfsheep("SW")
if tmp!=0:
    print("".join(tmp[:-2]))
    exit()

#SSパターン
tmp= wolfsheep("SS")
if tmp!=0:
    print("".join(tmp[:-2]))
    exit()
#WWパターン
tmp= wolfsheep("WW")
if tmp!=0:
    print("".join(tmp[:-2]))
    exit()
#WSパターン
tmp= wolfsheep("WS")
if tmp!=0:
    print("".join(tmp[:-2]))
    exit()

print(-1)
while 1:
	n=input()
	if n==0:break
	hmax=5000
	block=[map(int,raw_input().split()) for i in range(n)]
	field=[[0]*5 for i in range(hmax)]
	h=0
	for d,p,q in block:
		if d==1:
			for li in range(h,-2,-1):
				if field[li][q-1:q+p-1]!=[0]*p or li==-1:
					field[li+1][q-1:q+p-1]=[1]*p
					h=max(h,li+2)
					break
		else:
			for li in range(h,-2,-1):
				if field[li][q-1]!=0 or li==-1:
					for i in range(p):
						field[li+i+1][q-1]=1
					h=max(h,li+1+p)
					break
		i=0
		while 1:
			if field[i]==[1]*5:
				del field[i]
				h-=1
			elif field[i]==[0]*5:
				break
			else:
				i+=1
	print sum([sum(field[li]) for li in range(h)])

### FIXED CODE ###

while 1:
	n=input()
	if n==0:break
	hmax=7500
	block=[map(int,raw_input().split()) for i in range(n)]
	field=[[0]*5 for i in range(hmax)]
	top=[0]*5
	for d,p,q in block:
		if d==1:
			h=max(top[q-1:q-1+p])
			field[h][q-1:q-1+p]=[1]*p
			top[q-1:q-1+p]=[max(top)+1]*p
		else:
			h=top[q-1]
			for i in range(p):
				field[h+i][q-1]=1
			top[q-1]=h+p
		h=0
		while 1:
			if field[h]==[1]*5:
				del field[h]
				top=[x-1 for x in top]
			elif field[h]==[0]*5:
				break
			else:
				h+=1
		for w in range(5):
			for h in range(top[w]-1,-2,-1):
				if field[h][w]==1 or h==-1:
					top[w]=h+1
					break
	print sum([sum(field[h]) for h in range(max(top))])
def wczytaj_liste():
    ciag = input()
    rozdzielona_lista = ciag.split()
    odp = []
    for wyraz in rozdzielona_lista:
        liczba = int(wyraz)
        odp.append(liczba)
    return odp

def Raccon_vs_Monster():
    H, N = wczytaj_liste()
    ruchy = wczytaj_liste()
    suma_obrazen = ruchy.sum()
    if suma_obrazen >= H:
        print('Yes')
    else:
        print('No')

Raccon_vs_Monster()


### FIXED CODE ###

def wczytaj_liste():
    ciag = input()
    rozdzielona_lista = ciag.split()
    odp = []
    for wyraz in rozdzielona_lista:
        liczba = int(wyraz)
        odp.append(liczba)
    return odp

def Raccon_vs_Monster():
    H, N = wczytaj_liste()
    ruchy = wczytaj_liste()
    suma_obrazen = sum(ruchy)
    if suma_obrazen >= H:
        print('Yes')
    else:
        print('No')

Raccon_vs_Monster()
def change_num(tmp, i):
    if tmp[i] == "0":
        return int(tmp, 2)+pow(2, N-i-1)
    else:
        return int(tmp, 2)-pow(2, N-i-1)


N = int(input())
X = input()
flag = 0

for i in range(N):
    tmp = change_num(X, i)
    while True:
        num1 = 0
        for i in bin(tmp):
            # if i == 1:
            if "1" in i:
                num1 += 1

        tmp = tmp % num1
        flag += 1
        if tmp == 0:
            break
    print(flag)
    flag = 0


### FIXED CODE ###

n=int(input())
x=input()
t=int(x,2)
c=x.count('1')
a=t%-~c
b=0 if c<2 else t%~-c
for i in range(n):
  if int(x[i]):
    if c<2: print(0); continue
    else: t=(b-pow(2,n-i-1,c-1))%~-c
  else: t=(a+pow(2,n-i-1,c+1))%-~c
  z=1
  while t:
    d=bin(t).count('1')
    t%=d
    z+=1
  print(z)
n = int(input())
count = 0
 
for i in range(1,n+1):
  if len(int(i))//2 != 1:
    count += 1
 
print(count)

### FIXED CODE ###

n = int(input())
count = 0
 
for i in range(1,n+1):
  if len(str(i))%2 == 1:
    count += 1
 
print(count)
N = input()
if len(set(N[0:2])) == 1 || len(set(N[1:3])):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

N = input()
if (N[0] == N[1] and N[1] == N[2]) or (N[1] == N[2] and N[2] == N[3]):
  print("Yes")
else:
  print("No")
a=[]
    for i in range(1200):
    b=input()
    if b=="":
        continue
    else:
        a=a+[str(x) for x in b.lower().replace(" ","",100)]
for i in "abcdefghijklmnopqrstuvwxyz":
    counter=0
    for j in a:
        if i==j:
            counter+=1
    print(str(i)+" : "+str(counter))

### FIXED CODE ###

import sys
cnts = {}
for line in sys.stdin:
    for c in list(line.lower()): cnts[c] = cnts.get(c,0) + 1
  
for c in range(ord('a'),ord('z')+1): print(chr(c),':',cnts.get(chr(c),0))
#A1 ~ Aiまでの和 O(logN)
def BIT_query(BIT,idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(BIT,idx,x):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return


alps = 'abcdefghijklmnopqrstuvwxyz'

n = int(input())
s = input()
char_hd_d = {}
for alp in alps:
    char_hd_d[alp] = [0]*(n+1)

for i, si in enumerate(s):
    BIT_update(char_hd_d[si], i+1, 1)

q = int(input())
ansl = []
for _ in range(q):
    command, a, b = input().split()
    if command == '1':
        i = int(a)
        c = b
        i_char = s[i-1]
        BIT_update(char_hd_d[i_char], i, -1)
        BIT_update(char_hd_d[c], i, 1)
        s[i-1] = c 
    else:
        l,r = int(a),int(b)
        cnt = 0
        for alp in alps:
            if BIT_query(char_hd_d[alp], r) - BIT_query(char_hd_d[alp], l-1) > 0:
                cnt += 1
        ansl.append(cnt)

for a in ansl:
    print(a)            

### FIXED CODE ###

#A1 ~ Aiまでの和 O(logN)
def BIT_query(BIT,idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(BIT,idx,x):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return


alps = 'abcdefghijklmnopqrstuvwxyz'

n = int(input())
s = list(input())
char_hd_d = {}
for alp in alps:
    char_hd_d[alp] = [0]*(n+1)

for i, si in enumerate(s):
    BIT_update(char_hd_d[si], i+1, 1)

q = int(input())
ansl = []
for _ in range(q):
    command, a, b = input().split()
    if command == '1':
        i = int(a)
        c = b
        i_char = s[i-1]
        BIT_update(char_hd_d[i_char], i, -1)
        BIT_update(char_hd_d[c], i, 1)
        s[i-1] = c 
    else:
        l,r = int(a),int(b)
        cnt = 0
        for alp in alps:
            if BIT_query(char_hd_d[alp], r) - BIT_query(char_hd_d[alp], l-1) > 0:
                cnt += 1
        ansl.append(cnt)

for a in ansl:
    print(a)
S = list(map(int, input()))

i  = 1
counter = 0
while i < len(S):
	if S[i - 1] != S[i]:
		del(S[i - 1 : i + 1])
		counter += 1
		i -= 1
	else:
		i += 1
		
print(counter * 2)

### FIXED CODE ###

S = list(map(int, input()))

print(min(S.count(0), S.count(1)) * 2)
from collections import Counter
n = int(input())
s = Counter(int)
for _ in n:
    word = str(input())
    s[word] += 1
m = int(input())
for _ in m:
    word = str(input())
    if word in s.keys():
        s[word] -= 1
ans = s.most_common(1)
print(ans[1])

### FIXED CODE ###

from collections import Counter, defaultdict
n = int(input())
s= []
t = defaultdict(int)
for _ in range(n):
    s.append(input())
u = Counter(s)
m = int(input())
for _ in range(m):
    word = input()
    t[word] -= 1
    if word in u.keys():
        u[word] -= 1

ans = u.most_common(1)[0][1]
t = sorted(t.items(), key=lambda x:x[1], reverse=True)[0][1]
t = max(t, 0)
print(max(ans,t))
o=input()
e=input()
e=e+""
for i in range(len(o)):
  print(o[i]+e[i],end="")

### FIXED CODE ###

o=list(input())
e=list(input())+[""]
for x,y in zip(o,e):
  print(x+y,end="")
def bitcount(N):  # 立ってるbitの数
    bitcnt = [0]
    for _ in range(N):
        bitcnt += [i + 1 for i in bitcnt]
    return bitcnt


n, x = int(input()), input()

num, cnt = int(x, 2), x.count('1')
num0, num1 = num % (cnt + 1), num % max(cnt - 1, 1)
lbit = bitcount(18)
for i in range(n):
    ans = 1
    if x[i] == '0':
        tmp = num0 + pow(2, n - (i + 1), cnt + 1)
    elif x[i] == '1':
        if cnt == 1:
            print(0)
            continue
        tmp = num1 - pow(2, n - (i + 1), cnt - 1)
    tmp %= ctmp
    ctmp = lbit[tmp]
    while tmp > 0:
        ans += 1
        tmp %= ctmp
        ctmp = lbit[tmp]
    print(ans)


### FIXED CODE ###

def bitcount(N):  # 立ってるbitの数
    bitcnt = [0]
    for _ in range(N):
        bitcnt += [i + 1 for i in bitcnt]
    return bitcnt


n, x = int(input()), input()

num, cnt = int(x, 2), x.count('1')
lbit = bitcount(18)
for i in range(n):
    ans = 1
    if x[i] == '0':
        ctmp = cnt + 1
        tmp = num % ctmp + pow(2, n - (i + 1), ctmp)
    elif x[i] == '1':
        ctmp = cnt - 1
        if ctmp == 0:
            print(0)
            continue
        tmp = num % ctmp - pow(2, n - (i + 1), ctmp)
    tmp %= ctmp
    ctmp = lbit[tmp]
    while tmp > 0:
        ans += 1
        tmp %= ctmp
        ctmp = lbit[tmp]
    print(ans)
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
x=sum(b)
for i in range(len(a)-1):
  if a[i+1]-a[i]==1:
    d=a[i-1]
    x+=c[d]
print(x)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
x=sum(b)
for i in range(len(a)-1):
  if a[i+1]-a[i]==1:
    d=a[i]
    x+=c[d-1]
print(x)
n,m = map(int,input().split())
a_n = list(map(int,input().split()))
b_and_c = []
for i in range(m):
    b_and_c.append(list(map(int,input().split())))

a_n.sort()

b_and_c.sort(key = lambda x : x[1], reverse = True)
index = 0
for i in range(m):
    if a_n[index] >= b_and_c[i][1] or index >= n:
        break
    for j in range(index, n):
        if a_n[j] < b_and_c[i][1]:
            for k in range(j, j + b_and_c[i][0]):
                if k == n:
                    break
                else:
                    if a_n[k] < b_and_c[i][1]:
                        a_n[k] = b_and_c[i][1]
                    else:
                        break
            index = k + 1
            break

print(sum(a_n))

### FIXED CODE ###

n,m = map(int,input().split())
a_n = list(map(int,input().split()))
b_and_c = []
for i in range(m):
    b_and_c.append(list(map(int,input().split())))

a_n.sort()

b_and_c.sort(key = lambda x : x[1], reverse = True)
index = 0
for i in range(m):
    if index >= n:
        break
    elif a_n[index] >= b_and_c[i][1]:
        break
    for j in range(index, n):
        if a_n[j] < b_and_c[i][1]:
            for k in range(j, min(j + b_and_c[i][0], n)):
                if a_n[k] < b_and_c[i][1]:
                    a_n[k] = b_and_c[i][1]
                else:
                    break
            index = k + 1
            break

print(sum(a_n))
N = int(input())
S = input()

ans = 0
str_list = list(S)

for i in range (len(str_list)-2):
  if(str_list[i] == "A"):
    pass
    if(str_list[i+1] == "B"):
      pass
      if(str[i+2] == "C"):
        ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
S = input()

ans = 0
str_list = list(S)

for i in range (len(str_list)-2):
  if(str_list[i] == "A"):
    if(str_list[i+1] == "B"):
      if(str_list[i+2] == "C"):
        ans += 1

print(ans)
import math

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


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


for i in range(1, k + 1):
    if i == k:
        tmp1 = 1
    else:
        tmp1 = combinations_count(k - 1, i - 1) % 1000000007
    if i == (n - k + 1):
        tmp2 = 1
    else:
        tmp2 = combinations_count(n - k + 1, i) % 1000000007
    print((tmp1 * tmp2) % 1000000007)


### FIXED CODE ###

import math

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


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


for i in range(1, k + 1):
    if n - k + 1 >= i:
        tmp1 = combinations_count(k - 1, i - 1) % 1000000007
        tmp2 = combinations_count(n - k + 1, i) % 1000000007
        ans = (tmp1 * tmp2) % 1000000007
        print(ans)
    else:
        print(0)