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

S = input()
S = S[::-1]
#print(S)

mod = 10**9+7

dp = [0]*13
dp[0] = 1
for i in range(len(S)-1,-1,-1):
	ch = int(S[i]) if S[i]!='?' else -1
	temp = [0]*13
	for d in range(10):
		if ch!=-1 and ch!=d:
			continue
		for m in range(13):
			temp[(10*m+d)%13] += dp[m]
	for m in range(13):
		temp[m] %= mod
	dp = temp
print(dp[5])


### FIXED CODE ###

S = input()
S = S[::-1]
#print(S)

mod = 10**9+7

tblpow = [1]
for i in range(1,len(S)+1):
	tblpow.append(10*tblpow[i-1]%13)

dp = [0]*13
dp[0] = 1
for i in range(len(S)-1,-1,-1):
	ch = int(S[i]) if S[i]!='?' else -1
	temp = [0]*13
	for d in range(10):
		if ch!=-1 and ch!=d:
			continue
		for m in range(13):
			temp[(d*tblpow[i]+m)%13] += dp[m]
	for m in range(13):
		temp[m] %= mod
	dp = temp
print(dp[5])
### BUGGY CODE ###

N = int(input())
p = list(map(float,input().split()))

dp = [[0]*(N+1) for _ in range(N+1)]
dp[0][0] = 1
#dp[i][j] i枚投げた時 j枚 表が出る確率
for i in range(1,N+1):
    for j in range(i+1):
        dp[i][j] = dp[i-1][j-1]*p[i-1] + dp[i-1][j]*(1-p[i-1])
print(sum(dp[N][(N+1)//2:]))

### FIXED CODE ###

N = int(input())
p = list(map(float,input().split()))

dp = [[0]*(N+1) for _ in range(N+1)]
dp[0][0] = 1
#dp[i][j] i枚投げた時 j枚 表が出る確率
for i in range(1,N+1):
    for j in range(i+1):
        dp[i][j] = dp[i-1][j-1]*p[i-1] + dp[i-1][j]*(1-p[i-1])
print(sum(dp[N][(N+1)//2:]))
### BUGGY CODE ###

import math
def func(x,y,z):
    ans = x**2 + y**2 + z**2+ x*y + y*z + z*x
    #print("x={},y={},z={},ans={}".format(x,y,z,ans))
    return ans

N = int(input())
for n in range(1,N+1):
    root_n = round(math.sqrt(n+1))
    count = 0
    #dp = [[0] * root_n for i in root_n]
    for x in range(1,root_n):
        for y in range(1,root_n):
            for z in range(1,root_n):
                if func(x,y,z)==n:
                    count=count+1
    print(count)
                
                

### FIXED CODE ###


import math
def func(x,y,z):
    ans = x**2 + y**2 + z**2+ x*y + y*z + z*x
    return ans

N = int(input())
array_N = [0]*N
root_n = round(math.sqrt(N+1))

for x in range(1,root_n):
    for y in range(1,root_n):
        for z in range(1,root_n):
            if func(x,y,z) <= N:
                array_N[func(x,y,z)-1] = array_N[func(x,y,z)-1] +1
                
for i in range(N):
    print(array_N[i])
### BUGGY CODE ###

c = input()

m = map(int, raw_input().split())
h = []
conte = 0
while(True):
	entrou = False
	
	
	
	for i in range(len(m)-1,-1,-1):
		if (not entrou and m[i]%2==0):
			entrou = True;
			conte += 1
			m[i] /= 2
		if(m[i]%2==0):
			m[i] *= 3
		
		else:
			m.pop(i)
	
	if(not entrou):
		print conte
		break

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
res = 0
for i in a:
    while i%2==0:
        res += 1
        i //= 2
print(res)
### BUGGY CODE ###

s = input()
#11011010001011
l = len(s)
while True:
	s2 = s.replace("10","").replace("01","")
	if s == s2:
		break
	s = s2



print(l - len(s))

### FIXED CODE ###

s = input()
#11011010001011
c = max(s.count("1") - s.count("0"),s.count("0") - s.count("1"))

if len(s) == 1:
	print(0)
else:
	print(len(s)-c)
### BUGGY CODE ###

N, Y = list(map(int, input().split()))
c = 0
for i in range(N+1):
    for j in range(N-i+1):
        for k in range(N-i-j+1):
            #print(i,j,k)
            if 10000 * i + 5000 * j + 1000 * k == Y and i + j + k == N:
                print(i, j, k)
                c = 1
                break
        if c == 1:
            break
    if c == 1:
        break
if c == 0:
    print(-1,-1,-1)

### FIXED CODE ###

N, Y = list(map(int, input().split()))
c = 0
for i in range(N+1):
    for j in range(N-i+1):
        if 10000 * i + 5000 * j + 1000 * (N-i-j) == Y:
            print(i, j, (N-i-j))
            c = 1
            break
    if c == 1:
        break
if c == 0:
    print(-1, -1, -1)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = A[0]
for i in range(1,N):
    ans = ans * A[i]
if ans > 10**18:
    ans = -1
print(ans)

### FIXED CODE ###

N = int(input())
A = sorted(list(map(int,input().split())))
ans = A[0]
if ans == 0:
    print(ans)
    exit()
else:
    for i in range(1,N):
        ans = ans * A[i]
        if ans > 10**18:
            ans = -1
            break
    print(ans)
### BUGGY CODE ###

import numpy as np

H, W, M = map(int, input().split())
bom = [[0]*W for _ in range(H)]
row = [0] * H
col = [0] * W

for _ in range(M):
    h, w = map(int, input().split())
    bom[h-1][w-1] += 1
    row[h-1] += 1
    col[w-1] += 1

ans = 0

for i in range(H):
    cnt = row[i]
    r = bom[i]

    tmp = np.array(col) - np.array(r)
    maxi = np.max(tmp)

    ans = max(ans, (cnt + maxi))

print(ans)


### FIXED CODE ###

H, W, M = map(int, input().split())
bom = set()
row = [0] * H
col = [0] * W

for _ in range(M):
    h, w = map(int, input().split())
    bom.add((h-1, w-1))
    row[h-1] += 1
    col[w-1] += 1

max_row = max(row)
max_col = max(col)
ans = max_row + max_col - 1

p, q = [], []

for i in range(H):
    if row[i] == max_row:
        p.append(i)

for j in range(W):
    if col[j] == max_col:
        q.append(j)

flag = False
for i in p:
    for j in q:
        if (i, j) not in bom:
            ans += 1
            flag = True
            break
    if flag:
        break

print(ans)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

def main():
	n = int(input())
	s = tuple(input())

	ans = 0

	for i in range(3,n):
		for j in range(i-2):
			for k in range(j+1,i):
				if s[i] != s[j] != s[k] != s[i]:
					if k - j != i - k:
						ans += 1

	print(ans)

if __name__ == '__main__':
	main()

### FIXED CODE ###

import sys
import bisect
readline = sys.stdin.readline

def main():
	n = int(input())
	s = tuple(input())

	ans = 0
	r = []
	g = []
	b = []
	for i in range(3):
		if s[i] == 'R':
			r.append(i)
		elif s[i] == 'G':
			g.append(i)
		else:
			b.append(i)

	for i in range(3,n):
		if s[i] == 'R':
			r.append(i)
		elif s[i] == 'G':
			g.append(i)
		else:
			b.append(i)

		for j in range(i-2):
			if (j-i) % 2 == 0:
				if s[i] == s[j]:
					continue
				elif 'R' not in [s[i],s[j]]:
					ans += bisect.bisect_left(r,i) - bisect.bisect_left(r,j)
					index = bisect.bisect_left(r,j + (i-j)//2 )
					if index < len(r):
						if r[index] == j + (i-j)//2:
							ans -= 1
				elif 'G' not in [s[i],s[j]]:
					ans += bisect.bisect_left(g,i) - bisect.bisect_left(g,j)
					index = bisect.bisect_left(g,j + (i-j)//2 )
					if index < len(g):
						if g[index] == j + (i-j)//2:
							ans -= 1
				elif 'B' not in [s[i],s[j]]:
					ans += bisect.bisect_left(b,i) - bisect.bisect_left(b,j)
					index = bisect.bisect_left(b,j + (i-j)//2 )
					if index < len(b):
						if b[index] == j + (i-j)//2:
							ans -= 1
			else:
				if s[i] == s[j]:
					continue
				elif 'R' not in [s[i],s[j]]:
					ans += bisect.bisect_left(r,i) - bisect.bisect_left(r,j)

				elif 'G' not in [s[i],s[j]]:
					ans += bisect.bisect_left(g,i) - bisect.bisect_left(g,j)

				elif 'B' not in [s[i],s[j]]:
					ans += bisect.bisect_left(b,i) - bisect.bisect_left(b,j)


	print(ans)

if __name__ == '__main__':
	main()
### BUGGY CODE ###

import math

def hcfnaive(a, b):
    if (b == 0):
        return a
    else:
        return hcfnaive(b, a % b)

def gcd(a, b, c):
    return hcfnaive(a, hcfnaive(b, c))

##def gcd(a, b, c, cnt):
  ##  i = 0
    ####  i = i + 1
        ##if len(list(filter(is_prime, [a, b, c]))) == 0:
          ##  if (a % i == 0) and(b % i == 0) and (c % i == 0):
            ##    return gcd(a / i, b / i, c / i, cnt * i)
        ##else:
          ##  return cnt

def is_prime(n):
    if n % 2 == 0 and n > 2:
        return False
    return all(n % i for i in range(3, int(math.sqrt(n)) + 1, 2))

ans = 0
k = int(input())
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans = ans + gcd(a, b, c)

print(ans)

### FIXED CODE ###

import math

def hcfnaive(a, b):
    if (b == 0):
        return a
    else:
        return hcfnaive(b, a % b)

def gcd(a, b, c):
    return hcfnaive(a, hcfnaive(b, c))

##def gcd(a, b, c, cnt):
  ##  i = 0
    ####  i = i + 1
        ##if len(list(filter(is_prime, [a, b, c]))) == 0:
          ##  if (a % i == 0) and(b % i == 0) and (c % i == 0):
            ##    return gcd(a / i, b / i, c / i, cnt * i)
        ##else:
          ##  return cnt

def is_prime(n):
    if n % 2 == 0 and n > 2:
        return False
    return all(n % i for i in range(3, int(math.sqrt(n)) + 1, 2))

ans = 0
k = int(input())
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans = ans + gcd(a, b, c)

print(ans)
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
L = [[0] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    L[a-1].append(b-1)
    L[b-1].append(a-1)
L[0][0] = 1
d = [0] * n
ans = [0] * n
dq = deque([0])
while len(dq) > 0:
    t = dq.popleft()
    for i in range(1, len(L[t])):
        if d[L[t][i]] == 0:
            d[L[t][i]] = d[t] + 1
            ans[L[t][i]] = t + 1
        else:
            if d[L[t][i]] > d[t] + 1:
                d[L[t][i]] = d[t] + 1
                ans[L[t][i]] = t + 1
        if L[L[t][i]][0] == 0:
            dq.append(L[t][i])
    else:
        L[t][0] = 1
print('Yes')
print(*ans[1:], sep='\n')

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    L = [[0] for _ in range(n)]
    for _ in [0] * m:
        a, b = map(int, input().split())
        L[a-1].append(b-1)
        L[b-1].append(a-1)
    L[0][0] = 1
    ans = [0] * n
    dq = deque([0])
    while dq:
        t = dq.popleft()
        for i in range(1, len(L[t])):
            next = L[t][i]
            if ans[next] != 0:
                continue
            ans[next] = t + 1
            dq.append(next)
        else:
            L[t][0] = 1
    print('Yes')
    print(*ans[1:], sep='\n')

main()
### BUGGY CODE ###

# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

readl= lambda: list(map(int, sys.stdin.readline().split()))
readt= lambda: tuple(map(int, sys.stdin.readline().split()))
read = lambda: sys.stdin.readline().rstrip()
readi = lambda: int(read())
readmi = lambda: map(int, sys.stdin.readline().split())
readms = lambda: map(str, sys.stdin.readline().split())

n = readi()
d = []
for i in range(n):
    k = readi()
    d.append(k)
d = deque(d)
for i in range(n):
    print(max(list(d)[1:n]))
    d.rotate(-1)


### FIXED CODE ###

# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

readl= lambda: list(map(int, sys.stdin.readline().split()))
readt= lambda: tuple(map(int, sys.stdin.readline().split()))
read = lambda: sys.stdin.readline().rstrip()
readi = lambda: int(read())
readmi = lambda: map(int, sys.stdin.readline().split())
readms = lambda: map(str, sys.stdin.readline().split())

n = readi()
d = []
h = []
for i in range(n):
    k = readi()
    d.append(k)
    heapq.heappush(h,-k)
t1 = -heapq.heappop(h)
t2 = -1
if h:
    t2 = -heapq.heappop(h)
if n == 1:
    print(d[0])
else:
    for i in range(n):
        if d[i] == t1:
            print(t2)
        else:
            print(t1)
### BUGGY CODE ###

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

# 1: now, -1: visited, 0: none
b[0] = 1
now = 0
count = 0
while (b[1] != 1):
   next = a[now] - 1

   if (b[next] == -1):
      print(-1)
      exit()

   b[now] = -1
   b[next] = 1

   now = next
   count += 1

print(count)


### FIXED CODE ###

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

# 1: now, -1: visited, 0: none
b[0] = 1
now = 0
count = 0
while (b[1] != 1 and count <= n):
   next = a[now] - 1

   if (b[next] == -1):
      print(-1)
      exit()

   b[now] = -1
   b[next] = 1

   now = next
   count += 1

if (b[1] == 1):
   print(count)
else:
   print(-1)
### BUGGY CODE ###

from collections import deque

line1 = input()
n, k = [int(num) for num in line1.split(" ")]
line2 = input()
h = [int(num) for num in line2.split(" ")]

d = deque([0], k)

for i in range(1, len(h)):
    min_cost = float("inf")
    for j,cost in enumerate(d):
        if i-j < 0: break
        steps_taken = len(d)-j
        min_cost = min(min_cost, cost + abs(h[i]-h[i-steps_taken]))
    d.append(min_cost)

print(d[-1])

### FIXED CODE ###

from collections import deque

line1 = input()
n, k = [int(num) for num in line1.split(" ")]
line2 = input()
h = [int(num) for num in line2.split(" ")]

d = deque([0], k)

for i in range(1, len(h)):
    min_cost = float("inf")
    for j,cost in enumerate(reversed(d)):
        steps_taken = j+1
        if i-steps_taken < 0: break
        step_cost = abs(h[i]-h[i-steps_taken])
        min_cost = min(min_cost, cost + abs(h[i]-h[i-steps_taken]))
        if step_cost == 0: break
    d.append(min_cost)

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

n = int(input())
a = list(map(int, input().split()))
anslist = []
for i in range(n):
    anslist += [str(a.index(i+1)+1)]
print(" ".join(anslist))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
mydict = {}
for i in range(n):
    mydict[str(i+1)] = a[i]
mydict = sorted(mydict.items(), key= lambda x:x[1])
for j in range(n):
    print(mydict[j][0], end=' ')
### BUGGY CODE ###

N = int(input())

def count_n(n):
    ans = 0
    for x in range(1,int(N**0.5)+1):
        if 6*x**2 == n:
            ans = 1
            return ans
        for y in range(1,int(N**0.5)+1):
                if (3*x**2 + y**2 + 2*x*y)  == n:
                    ans += 3
    return ans

for i in range(1,N+1):
    print(count_n(i))

### FIXED CODE ###

n = int(input())
a = [0]*(n+1)
for i in range(1, 102):
    for j in range(1, 102):
        for k in range(1, 102):
            if (i*i + j*j + k*k + i*j + j*k + i*k) <= n:
                a[i*i + j*j + k*k + i*j + j*k + i*k] +=1
                
for x in a[1:]:
    print(x)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
for i in range(q):
    l, r = map(int, input().split())
    print(s[l-1:r].count("AC"))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()

t = [0] * (N)
for i in range(N-1):
    t[i+1] = t[i] + (1 if S[i:i+2]=="AC" else 0)

for j in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

nm = input().split()
n = int(nm[0])
m = int(nm[1])

roads = []

for i in range(m):
    a = input().split()
    roads.append([int(a[0]), int(a[1])])

visited = [1]
output = [0]*(n-1)
shortest = [1]
while len(visited) < n:
    for i in range(len(shortest)):
        for k in range(len(roads)):
            if shortest[i] in roads[k]:
                t = roads[k].index(shortest[i])
                if roads[k][(t+1) % 2] not in visited:
                    shortest.append(roads[k][(t+1) % 2])
                    visited.append(roads[k][(t+1) % 2])
                    output[roads[k][(t+1) % 2] - 2] = shortest[i]

print('Yes')
for i in range(len(output)):
    print(output[i])


### FIXED CODE ###

from collections import deque

n, m = map(int, input().split())
room = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    room[a-1].append(b)
    room[b-1].append(a)

point = [0 for i in range(n)]
d = deque([0])

while len(d) > 0:
    p = d.popleft()
    for v in room[p]:
        if point[v-1] == 0:
            d.append(v-1)
            point[v-1] = p+1

print('Yes')
for i in range(1, n):
    print(point[i])
### BUGGY CODE ###

import itertools

def main():
  s = input()
  k = int(input())
  alphabet = sorted(list(set(list(s))))

  list_sub = []
  num = 1
  while num <= k:
    temp = list(itertools.product(alphabet, repeat=num))
    temp = ["".join(com) for com in temp if "".join(com) in s]
    list_sub.extend(temp)
    num += 1
  list_sub.sort()
  print(list_sub[k-1])

if __name__ == "__main__":
  main()

### FIXED CODE ###

s = input()
k = int(input())

list_sub = []
for i in range(len(s)):
  temp = [s[i:i+j] for j in range(1, min(len(s)-i+1, k+1))]
  list_sub += temp

list_sub = list(set(list_sub))
list_sub.sort()

print(list_sub[k-1])
### BUGGY CODE ###

import numpy as np
N,K=map(int,input().split())
L=[0]*(N+1)
for i in range(K):
  a,b=map(int,input().split())
  for i in range(a,b+1):
    L[N-i]+=1
qw=[i for i in L]
p=np.poly1d(L)
k=np.poly1d(qw)
ans=0
mod=998244353
s=p.coef
if len(s)>=N:
  ans+=s[-N]

for i in range(N):
  p=p*k
  s=p.coef
  if len(s)>=N:
    ans+=s[-N]
    p=np.poly1d(s[-N:])
  ans%=mod
print(ans)

### FIXED CODE ###

N,K=map(int,input().split())
dp=[0]*(N)
dp[0]=1
mod=998244353
L=list()
for i in range(K):
  a,b=map(int,input().split())
  L.append([a,b])
R=[0,1]
for i in range(1,N):
  for j in range(K):
    a,b=L[j]
    if i>=b:
      dp[i]+=R[i-a+1]-R[i-b]
    elif i>=a:
      dp[i]+=R[i-a+1]
    dp[i]%=mod
  R.append(R[-1]+dp[i])
print(dp[-1])
### BUGGY CODE ###

import heapq
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            self.rank[x] += (self.rank[x] == self.rank[y])

def kruskal(n, edge):
    ans = 0
    uf = UnionFind(n)
    for i in range(len(edge)):
        d, v, u = heapq.heappop(edge)
        
        if uf.find(v) != uf.find(u):
            uf.union(v, u)
            n -= 1
            ans += d
        if n < 1: return ans
    return ans

n = int(input())
x, y = [None]*n, [None]*n
dist = [[0] * n for _ in range(n)]

for i in range(n):
    a, b = map(int, input().split())
    x[i] = (a, i)
    y[i] = (b, i)

x.sort(key=lambda x:x[0])
y.sort(key=lambda y:y[0])

edge = []
for i in range(n-1):
    heapq.heappush(edge, (x[i+1][0]-x[i][0], x[i][1], x[i+1][1]))
    heapq.heappush(edge, (y[i+1][0]-y[i][0], y[i][1], y[i+1][1]))

del x, y
print(kruskal(n, edge))

### FIXED CODE ###

import heapq
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            self.rank[x] += (self.rank[x] == self.rank[y])

def kruskal(n, edge):
    ans = 0
    uf = UnionFind(n)
    while True:
        d, v, u = heapq.heappop(edge)
        
        if uf.find(v) != uf.find(u):
            uf.union(v, u)
            n -= 1
            ans += d
        if n < 2: return ans
    return ans

n = int(input())
x, y = [None]*n, [None]*n

for i in range(n):
    a, b = map(int, input().split())
    x[i] = (a, i)
    y[i] = (b, i)

x.sort(key=lambda x:x[0])
y.sort(key=lambda y:y[0])

edge = []
for i in range(n-1):
    heapq.heappush(edge, (x[i+1][0]-x[i][0], x[i][1], x[i+1][1]))
    heapq.heappush(edge, (y[i+1][0]-y[i][0], y[i][1], y[i+1][1]))

del x, y
print(kruskal(n, edge))
### BUGGY CODE ###

import itertools
n, m, r = map(int, input().split())
list_r = [one_r-1 for one_r in map(int, input().split())]

dist = [[float("inf")] * n for _ in range(n)]
for i in range(n):
  dist[i][i] = 0
for i in range(m):
  a, b, c = map(int, input().split())
  dist[a-1][b-1] = c
  dist[b-1][a-1] = c
for k in range(n):
  for i in range(n):
    for j in range(n):
      if dist[i][j] > dist[i][k] + dist[k][j]:
        dist[i][j] = dist[i][k] + dist[k][j]

result = float("inf")
for one_cand in itertools.permutations(list_r):
  temp = 0
  for i in range(r-1):
    temp += dist[one_cand[i]][one_cand[i+1]]
  if temp < result:
    result = temp
print(result)

### FIXED CODE ###

from itertools import permutations
import sys

def main():
    
    N, M, R = map(int, sys.stdin.readline().split())
    r = [i - 1 for i in map(int, sys.stdin.readline().split())]
    
    d = [[float('inf')] * N for _ in range(N)]
    
    for i in range(N):
        d[i][i] = 0
        
    for i in range(M):
        a, b, c = map(int,sys.stdin.readline().split())
        d[a-1][b-1] = c
        d[b-1][a-1] = c
        
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
    
    ans = 10**12
    
    for each in permutations(r):
        t_dis = 0
        for i in range(R-1):
            t_dis += d[each[i]][each[i+1]]  
        
        ans = min(ans, t_dis)
    
    print(ans)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


def main():
    S = input()
    K = int(input())

    N = len(S)
    substring = set()
    for i in range(N):
        for j in range(i + 1, N + 1):
            substring.add(S[i:j])

    substring = list(substring)
    substring.sort()
    print(substring[K - 1])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


def main():
    S = input()
    K = int(input())

    N = len(S)
    substring = set()
    for i in range(N):
        for j in range(1, 6):
            substring.add(S[i:i + j])

    substring = list(substring)
    substring.sort()
    print(substring[K - 1])


if __name__ == '__main__':
    main()
### BUGGY CODE ###

n=int(input())
x=input()
f=[0]*n
for i in range(1,n):
    popcount=format(i,'b').count('1')
    f[i]=f[i%popcount]+1
# print(f)
for i in range(len(x)):
    if x[i]=='1':
        x_changed=x[:i]+'0'+x[i+1:]
    else:
        x_changed=x[:i]+'1'+x[i+1:]
    num_changed=int(x_changed,2)
    # print(x_changed,num_changed)
    popcount=format(num_changed,'b').count('1')
    if num_changed<n:
        print(f[num_changed])
    else:
        print(f[num_changed%popcount]+1)

### FIXED CODE ###

## 最初のmodをどうにか高速にやりたい → modの性質を使う
## xiのpopcount（1の数）はxのpopcount+1または-1
n=int(input())
x_str=input()
x_popcount=x_str.count('1')
dp=[0]*(x_popcount+1)
for i in range(1,x_popcount+1):
    popcount=format(i,'b').count('1')
    dp[i]=dp[i%popcount]+1
# print(dp)
# x=int(x_str,2)
if x_popcount>1:
    pows_minus=[pow(2,i,(x_popcount-1)) for i in range(n)]
    # x_minus=x%(x_popcount-1)
    x_minus=0
    for i in range(n):
        if x_str[i]=='1':
            x_minus+=pows_minus[n-1-i]
pows_plus=[pow(2,i,(x_popcount+1)) for i in range(n)]
# x_plus=x%(x_popcount+1)
x_plus=0
for i in range(n):
    if x_str[i]=='1':
        x_plus+=pows_plus[n-1-i]

for i in range(len(x_str)):
    ## xi=xi mod popcount(x)+-1
    xi=-1
    if x_str[i]=='1':
        if x_popcount>1: ## else: xi=-1
            xi=(x_minus-pows_minus[n-1-i])%(x_popcount-1)
    else:
        xi=(x_plus+pows_plus[n-1-i])%(x_popcount+1)
    if xi==-1:
        print(0)
    else:
        print(dp[xi]+1)