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

import numpy as np

k,q=map(int,input().split())
D=np.array(list(map(int,input().split())),dtype="i8")

for i in range(q):
    n,x,m=map(int,input().split())
    mD=D%m #元の列のmodを取る
    a=(n-1)//k
    b=(n-1)%k
    ans=0
    cnt=x%m
    for i in range(k):
        if i<b:
            if mD[i]==0: #余り0のとき
                ans+=a+1
            else:
                cnt+=mD[i]*(a+1)
        else:
            if mD[i]==0: #余り0のとき
                ans+=a
            else:
                cnt+=mD[i]*a
    ans+=cnt//m
    print(n-1-ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

k,q=map(int,input().split())
D=list(map(int,input().split()))
A=[]
for i in range(q):
    n,x,m=map(int,input().split())
    mD=list(map(lambda i: i%m, D)) #元の列のmodを取る
    ans=0
    cnt=x%m
    a=(n-1)//k
    b=(n-1)%k
    for d in mD[:b]: #mod kで余る部分
        if d==0:
            ans+=a+1
        cnt+=d*(a+1)
    for d in mD[b:]: #余らない部分
        if d==0:
            ans+=a
        cnt+=d*a
    ans+=cnt//m
    print(n-1-ans)
### BUGGY CODE ###

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

for i in range(1, N+1):
    count = 0
    for a in A:
        if i == a:
            count += 1
    print(count)

### FIXED CODE ###

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

c = collections.Counter(A)
for i in range(1, N+1):
    print(c[i])
### BUGGY CODE ###

import math
Q = int(input())

l = [0 for i in range(Q)]
r = [0 for i in range(Q)]
i = 0
while True:
  try:
    lr=list(map(int,input().split()))
    l[i] = lr[0]
    r[i] = lr[1]
    i+=1
  except:
    break

def is_prime(num):
  if(type(num) != type(0)):
    print('error at '+str(num)+' type = '+str(type(num)))
    print(type(int))
    return 0
  if(num<2):
    return 0
  elif(num == 2):
    return 1
  n = math.ceil(math.sqrt(num))
  for i in range(2,n+1):
    if((num%i) == 0):
      return 0
  return 1

def create_list():
  MAXI = max(r)+1
  
  prime = [1 for i in range(MAXI)]
  prime[0] = 0
  prime[1] = 0
  for i in range(2,MAXI):
    if(prime[i] == 0):
      continue
    else:
      prime[i] = is_prime(i)
      for j in range(i*2,MAXI,i*2):
        prime[j] = 0
      for j in range(i*5,MAXI,i*3):
        prime[j] = 0
      for j in range(i*5,MAXI,i*5):
        prime[j] = 0
  #print(prime)
  sn = [0 for i in range(MAXI+1)]
  for i in range(1,MAXI+1,2):
    #print('int(('+str(i+1)+')/2) = '+str(int((i+1)/2))+' when '+str(prime[int((i+1)/2)]))
    sn[i] = (prime[i] * prime[int((i+1)/2)]) #odd
    sn[i+1] = 0 #even
  return sn

base = create_list()
#print(base)
for i in range(Q):
  if(l[i]==r[i]):
    print(base[l[i]])
  else:
    lnum = base[0:l[i]]
    rnum = base[0:r[i]]
    print( sum(rnum)-sum(lnum) )

### FIXED CODE ###

import math
import sys
sys.setrecursionlimit(10 ** 5 + 10)

Q = int(input())

l = [0 for _ in range(Q)]
r = [0 for _ in range(Q)]
i = 0
while True:
  try:
    lr=list(map(int,input().split()))
    l[i] = lr[0]
    r[i] = lr[1]
    i+=1
  except:
    break

def is_prime(num):
  #if(type(num) != type(0)):
  #  print('error at '+str(num)+' type = '+str(type(num)))
  #  print(type(int))
  #  return 0
  #if(num<2):
  #  return 0
  if(num == 2):
    return 1
  n = math.ceil(math.sqrt(num))
  for i in range(2,n+1):
    if((num%i) == 0):
      return 0
  return 1

def create_list():
  MAXI = max(r)+1
  
  prime = [1 for _ in range(MAXI+1)]
  prime[0] = 0
  prime[1] = 0
  for i in range(2,MAXI):
    if(prime[i] == 0):
      continue
    else:
      prime[i] = is_prime(i)
      for j in range(i*2,MAXI,i*2):
        prime[j] = 0
      for j in range(i*5,MAXI,i*3):
        prime[j] = 0
      for j in range(i*5,MAXI,i*5):
        prime[j] = 0
  #print(prime)
  sn = [0 for _ in range(MAXI+2)]
  for i in range(1,MAXI+1,2):
    #print('int(('+str(i+1)+')/2) = '+str(int((i+1)/2))+' when '+str(prime[int((i+1)/2)]))
    sn[i] += sn[i-1] + (prime[i] * prime[int((i+1)/2)]) #odd
    sn[i+1] = sn[i]
  return sn

base = create_list()
#print(base)
for i in range(Q):
  print( base[r[i]] - base[l[i]-1] )#sum(rnum)-sum(lnum) )
### BUGGY CODE ###

n, x, y = map(int, input().split())
ans = []

for i in range(1, n):
    for j in range(i + 1, n + 1):
        diff1 = j - i
        diff2 = x + y - i - j + 1
        if i <= x and j >= y:
            diff2 = x - y - i + j + 1
        elif x <= i <= y and x <= j <= y:
            diff2 = -x + y + i - j + 1
        elif x < i < y and j > y:
            diff2 = -x - y + i + j + 1
        if diff2 < 1:
            diff2 = diff1
        diff = min(diff1, diff2)
        ans.append(diff)

for i in range(1, n):
    print(ans.count(i))

### FIXED CODE ###

n, x, y = map(int, input().split())
ans = [0]*n

for i in range(1, n):
    for j in range(i + 1, n + 1):
        diff1 = j - i
        diff2 = x + y - i - j + 1
        if i <= x and j >= y:
            diff2 = x - y - i + j + 1
        elif x <= i <= y and x <= j <= y:
            diff2 = -x + y + i - j + 1
        elif x < i < y and j > y:
            diff2 = -x - y + i + j + 1
        if diff2 < 1:
            diff2 = diff1
        diff = min(diff1, diff2)
        ans[diff] = ans[diff] + 1

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

import sys
def input():
  return sys.stdin.readline()[:-1]

N, M=map(int, input().split())
NN=2**N

dp=[[0]+[-1]*(NN-1) for i in range(M+1)]
for i in range(1, M+1):
  a, b=map(int, input().split())
  c=list(map(int, input().split()))
  csum=sum([2**(c[s]-1) for s in range(b)])
  
  for j in range(NN):
    if dp[i-1][j]>-1:
      if dp[i][j]==-1 or dp[i][j]>dp[i-1][j]:
        dp[i][j]=dp[i-1][j]
      
      tmp=csum|j
      if dp[i][tmp]==-1 or dp[i][tmp]>dp[i][j]+a:
        dp[i][tmp]=dp[i][j]+a
        
print(dp[-1][-1])

### FIXED CODE ###

#import sys
#def input():
#  return sys.stdin.readline()[:-1]

N, M=map(int, input().split())
NN=2**N

dp=[[0]+[-1]*(NN-1) for i in range(M+1)]
for i in range(1, M+1):
  a, b=map(int, input().split())
  c=list(map(int, input().split()))
  csum=sum([2**(c[s]-1) for s in range(b)])
  
  for j in range(NN):
    if dp[i-1][j]>-1:
      if dp[i][j]==-1 or dp[i][j]>dp[i-1][j]:
        dp[i][j]=dp[i-1][j]
      
      tmp=csum|j
      if dp[i][tmp]==-1 or dp[i][tmp]>dp[i][j]+a:
        dp[i][tmp]=dp[i][j]+a
        
print(dp[-1][-1])
### BUGGY CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort()
c = Counter(a)
s = []
m = max(a) + 1
ans = 0
for ai in a:
    if ai in s:
        continue
    if c[ai] == 1:
        ans += 1
    for i in range(ai, m, ai):
        s.insert(0, i)
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort()
c = Counter(a)
m = max(a) + 1
dp = [False]*m
ans = 0
for ai in a:
    if dp[ai]:
        continue
    if c[ai] == 1:
        ans += 1
    for i in range(ai, m, ai):
        dp[i] = True
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
dp = [[0]*(N+1) for _ in range(N+1)]
for i in reversed(range(N)):
    for j in reversed(range(N)):
        if S[i] == S[j]:
            dp[i][j] = dp[i+1][j+1] + 1

print(max(max(min(dp[a][b], a-b) for a in range(b, N)) for b in range(N)))

### FIXED CODE ###

N = int(input())
S = input()
ans = 0
for i in range(N):
    if N-i<ans:
        break
    if S[i+1:].find(S[i-ans:i+1])>=0:
        ans += 1
print(ans)
### BUGGY CODE ###

def readinput():
    n=int(input())
    x=input()
    return n,x

def popcount(n):
    binn=bin(n)
    return binn.count('1')

def f(n):
    #print(n)
    if n==0:
        return 0
    else:
        m=n%popcount(n)
        return f(m)+1

def main(n,x):
    intx=int(x,2)
    ans=[]
    b=1
    for i in range(n):
        y=intx^b
        ans.append(f(y))
        b=b*2
    return reversed(ans)


if __name__=='__main__':
    n,x=readinput()
    ans=main(n,x)
    for a in ans:
        print(a)

### FIXED CODE ###

def readinput():
    n=int(input())
    x=input()
    return n,x

poptbl=[0]*(2*10**5+1)
def popcount(x):
    global poptbl
    if poptbl[x]!=0:
        return poptbl[x]
    
    poptbl[x]=bin(x).count('1')
    return poptbl[x]

ftbl=[0]*(2*10**5+1)
def f(x):
    global ftbl

    if ftbl[x]!=0:
        return ftbl[x]
    
    #print('f(x), x: {}'.format(x))
    if x==0:
        return 0
    else:
        ans=f(x%popcount(x))+1
        #print(ans)
        ftbl[x]=ans
        return ans    

def main():
    n=int(input())
    x=input()
    m=x.count('1')
    #print('m: {}'.format(m))
    xint=int(x,2)
    #print('xint: {}'.format(xint))
    if m!=1:
        xmodm1=xint%(m-1)
    else:
        xmodm1=1
    xmodp1=xint%(m+1)
    pow2mod1=[0]*n
    pow2mod2=[0]*n
    pow2mod1[0]=1
    pow2mod2[0]=1
    for i in range(1,n):
        if m!=1:
            pow2mod1[i]=pow2mod1[i-1]*2 % (m-1)
        pow2mod2[i]=pow2mod2[i-1]*2 % (m+1)

    ans=[]
    #b=2**(n-1)
    for i in range(n):
        if x[i]=='1':
            if m==1:
                a=0
                ans.append(a)
            else:
                xx=( xmodm1 + (m-1) -pow2mod1[n-i-1] )%(m-1)
                #ans.append(f(xx)+1)
                a=f(xx)+1
                ans.append(a)
        else:
            xx=( xmodp1 + pow2mod2[n-i-1] )%(m+1)
            #ans.append(f(xx)+1)
            a=f(xx)+1
            ans.append(a)
        #b=b//2
        print(a)
    return ans

if __name__=='__main__':
    #n,x=readinput()
    ans=main()
    #for a in ans:
    #    print(a)
### BUGGY CODE ###

# N 参加人数
# K 開始時のポイント
#
# 0以下で敗退



N, K, Q = map(int, input().split(" "))
persons = list()

for i in range(N):
    persons.append(K)

for i in range(Q):
    a = int(input())
    for j in range(N):
        if a != j:
            persons[j-1] -= 1

for person in persons:
    if person <= 0:
        print("No")
    else:
        print("Yes")


### FIXED CODE ###

N, K, Q = map(int, input().split(" "))
persons = [K-Q] * N

for i in range(Q):
    a = int(input())
    persons[a-1] += 1

for person in persons:
    if person <= 0:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

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

mod = 10**9+7
dp = {}
for i in range(N+1):
    dp[i] = 1
dp[1] = 0 if 1 in l else 1

for i in range(2,N+1):
    if i in l:
        dp[i] = 0
        continue
    else:
        dp[i] = dp[i-1] + dp[i-2]

print(dp[N]%mod)

### FIXED CODE ###

N,M = map(int,input().split(' '))
l = set([int(input()) for i in range(M)])

mod = 10**9+7
dp = {}
for i in range(N+1):
    dp[i] = 1
dp[1] = 0 if 1 in l else 1

for i in range(2,N+1):
    if i in l:
        dp[i] = 0
        continue
    else:
        dp[i] = dp[i-1]%mod + dp[i-2]%mod
        dp[i] = dp[i]%mod

print(dp[N]%mod)
### BUGGY CODE ###

a, b = map(int, input().split())
l = list(map(int, input().split()))
c = a-b+1
vector = [0]*c

for i in range(c):
	for j in range (b):
		vector[i]=vector[i]+l[i+j]
    
print((max(vector)+b)/2)

### FIXED CODE ###

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

for i in range (0, N):
	A[i] = (A[i]+1)/2

sumK = sum(A[0:K])

L = [sumK]

for i in range (0, N-K):
	sumK = sumK + A[K+i] - A[i]
	L.append(sumK)

print(max(L))
### BUGGY CODE ###

from collections import Counter
n = int(input())
A = list(map(int,input().split()))
A = sorted(A)

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

s = set()
for a in A:
  dv = divisors(a)
  for d in dv:
    if d in s:  
      break
  else:
    s.add(a)
      
ans = 0
C = Counter(A)
for si in s:
  if C[si]==1:
    ans += 1
print(ans)          

### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
A = sorted(A)

limit = 10**6 + 2
A += [limit]
dp = [True] * (limit)

ans = 0
for i in range(n):
  a = A[i]
  if dp[a] and a != A[i+1]:
    ans += 1
  
  if dp[a] == False:
    continue
  for t in range(a,limit,a):    
    dp[t] = False
    t += a

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

N,T = [int(x) for x in raw_input().split(" ")]

A = [int(x) for x in raw_input().split(" ")]

mx = -1e10
cnt = 0

for i in range(len(A)-1):
	for j in range(i + 1, len(A)):
		if A[j] - A[i] > mx:
			mx = A[j] - A[i]
			cnt = 1

		elif A[j] - A[i] == mx:
			cnt += 1

print cnt



### FIXED CODE ###

N,T = [int(x) for x in raw_input().split(" ")]

A = [int(x) for x in raw_input().split(" ")]

mx = -1e10
cnt = 0
X = []

for i in range(len(A)):
	mx = max(A[-i-1],mx)
	
	dif = mx - A[-i-1]
	
	X.append(dif)



mxx = max(X)

for i in X:
	if i == mxx:
		cnt += 1

print cnt
### BUGGY CODE ###

from operator import itemgetter
N,M = [int(x) for x in input().split()]
LRC = []
event = []
dists = [float('inf')]*N
dists[0] = 0
cnt_key = 0
for _ in range(M):
    l, r, c = [int(x) for x in input().split()]
    event.append((l-1, c, 1, cnt_key))
    event.append((r-1, c, -1, cnt_key))
    cnt_key += 1

event.sort(key=itemgetter(0))
paths = {}
now_dist = 0
for ev in event:
    x = ev[0]
    for s in paths:
        if(dists[x]<paths[s][1]):
            paths[s][1] = dists[x]
        dists[x] = min(dists[x], paths[s][0]+paths[s][1])

    if(ev[2]==1):
        paths[ev[3]] = [ev[1], dists[ev[0]]]
    else:
        del paths[ev[3]]

if(dists[-1]==float('inf')):
    print(-1)
else:
    print(dists[-1])


### FIXED CODE ###

from operator import itemgetter
from collections import defaultdict
from heapq import heappop, heappush

class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()

class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

N,M = [int(x) for x in input().split()]
graph = Graph()
for n in range(N):
    graph.add_edge(n+1, n, 0)
for _ in range(M):
    l, r, c = [int(x) for x in input().split()]
    graph.add_edge(l-1, r-1, weight=c)

dijkstra = Dijkstra(graph, 0)
ans = dijkstra.shortest_distance(N-1)
if(ans == float('inf')):
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

def calculate(arr):
    length = len(arr)
    s1 = (length // 2) - 1
    s2 = (length // 2)

    if arr[s2] == arr[s1]:
        return 0
    else:
        return arr[s2] - arr[s1]


def rank(arr):
    lastIndex = len(arr) - 1
    while lastIndex > 0:

        for i in range(lastIndex):
            if arr[i + 1] < arr[i]:
                tmp = arr[i + 1]
                arr[i + 1] = arr[i]
                arr[i] = tmp

        lastIndex = lastIndex - 1

    return arr

N = int(input())

if N == 0:
    result = 0
else:
    arr = rank([int(s) for s in  input().split(" ")])
    result = calculate(arr)

print(result)


### FIXED CODE ###

def calculate(arr):
    length = len(arr)
    s1 = (length // 2) - 1
    s2 = (length // 2)

    if arr[s2] == arr[s1]:
        return 0
    else:
        return arr[s2] - arr[s1]

N = int(input())

if N == 0:
    result = 0
else:
    list = list([int(s) for s in  input().split(" ")])
    list.sort()
    result = calculate(list)

print(result)
### BUGGY CODE ###

n,m=input().split()
n=int(n)
m=int(m)
i=0
x=[]
y=[]
a=list(map(int,input().split()))

a=sorted(a)
while i!=m:
    i=i+1
    x=list(map(int,input().split()))
    y.append(x)

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

j=0
while True:
    try:
        t=y[0]
        del y[0]
        i=0
        while i!=t[0]:
            i=i+1
            if t[1]>a[j]:
                a[j]=t[1]
                j=j+1
            else:
                break
                break

    except:
        break
ans=0
i=0
while True:
    try:
        ans=ans+a[i]
        i=i+1
    except:
        break
print(ans)


### FIXED CODE ###

n,m=input().split()
n=int(n)
m=int(m)
i=0
x=[]
y=[]
a=list(map(int,input().split()))

a=sorted(a)
while i!=m:
    i=i+1
    x=list(map(int,input().split()))
    y.append(x)

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

j=0
while True:
    try:
        t=y[0]
        del y[0]
        i=0
        while i!=t[0]:
            i=i+1
            if t[1]>a[j]:
                a[j]=t[1]
                j=j+1
            else:
                break
        if t[1] > a[j]:
            pass
        else:
            break

    except:
        break
ans=0
i=0
while True:
    try:
        ans=ans+a[i]
        i=i+1
    except:
        break
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
CB = []
for _ in range(M):
    b, c = map(int, input().split())
    CB.append((c, b))

for bc in sorted(CB, reverse=True):
    A.sort()
    if A[0] >= bc[0]:
        break
    for i in range(bc[1]):
        if A[i] >= bc[0]:
            break
        A[i] = bc[0]

print(sum(A))


### FIXED CODE ###

from operator import itemgetter

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = []
for _ in range(M):
    BC.append(tuple(map(int, input().split())))

A.sort(reverse=True)
BC.sort(key=itemgetter(1), reverse=True)

n = 0
ans = 0
while True:
    if not BC:
        ans += sum(A[: N - n])
        break
    tgt = BC[0][1]
    a = A[0]
    if a >= tgt:
        ans += A.pop(0)
        n += 1
        if n == N:
            break
    else:
        tgt_n = BC[0][0]
        if n + tgt_n < N:
            ans += tgt * tgt_n
            n += tgt_n
            _ = BC.pop(0)
        else:
            ans += tgt * (N - n)
            break

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

n,k = map(int,input().split())
if k==1:
    print(0)
    exit()
while n > abs(n-k):
    n = abs(n-k)
print(n)

### FIXED CODE ###

n,k = map(int,input().split())
if n%k==0:
    print(0)
else:
    ans_a = n%k
    ans_b = abs(ans_a-k)
    print(min(ans_a,ans_b))
### BUGGY CODE ###

N, W = map(int, raw_input().split())
a = []
for i in range(N):
    a.append(map(int, raw_input().split()))

dp = [0]*(W+1)

for i in range(N):
    w = a[i][0]
    v = a[i][1]
    for j in range(W, w-1, -1):
        x = dp[j-w] + v
        if x > dp[j]:
            dp[j] = x

print dp[-1]

### FIXED CODE ###

def main():

    N, W = map(int, raw_input().split())
    dp = [0]*(W+1)
 
    for i in xrange(N):
        w, v = map(int, raw_input().split())
        for j in xrange(W, w-1, -1):
            x = dp[j-w] + v
            if x > dp[j]:
                dp[j] = x
 
    print dp[-1]

main()
### BUGGY CODE ###

import sys
import numpy as np
def S(): return sys.stdin.readline().rstrip()
def SL(): return map(str,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def IL(): return map(int,sys.stdin.readline().rstrip().split())

def Main():
    n,x,y = IL()
    x -= 1
    y -= 1
    dist = np.zeros(n-1,dtype='int32')
    for i in range(n):
        for j in range(i+1,n):
            tmp = min(abs(j-i),abs(j-x)+abs(x-i),abs(y-j)+abs(x-i)+1)
            dist[tmp-1] += 1
    for rep in dist:
        print(rep)
    return

if __name__=='__main__':
    Main()

### FIXED CODE ###

import sys
def S(): return sys.stdin.readline().rstrip()
def SL(): return map(str,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def IL(): return map(int,sys.stdin.readline().rstrip().split())

def Main():
    n,x,y = IL()
    x -= 1
    y -= 1
    dist = [0]*(n-1)
    for i in range(n):
        for j in range(i+1,n):
            dist[min(abs(j-i),abs(j-x)+abs(x-i),abs(y-j)+abs(x-i)+1)-1] += 1
    for rep in dist:
        print(rep)
    return

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

#!/usr/bin/env python3
import sys
import functools
INF = float("inf")

MOD = 2  # type: int


def power(b, p):
    if p == 0:
        return 1
    elif p == 1:
        return b
    elif p % 2 == 1:
        return b*power(b, p-1)
    else:
        return power(b*b, p//2)


def solve(p: int, a: "List[int]"):
    kaijo = [1]*p
    kaijo_inv = [1]*p

    for i in range(2, p):
        kaijo[i] = (kaijo[i-1]*i) % p
        kaijo_inv[i] = power(kaijo[i], p-2) % p

    def cmb(n, r):
        return (kaijo[n]*kaijo_inv[n-r]*kaijo_inv[r]) % p

    b = [0]*p
    for ai, av in enumerate(a):
        if av == 1:
            for i in range(p):
                b[i] += -cmb(p-1, i) * power(-ai, p-i-1)
                b[i] %= p
            b[0] += 1
            b[0] %= p
    print(*b, sep=" ")
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    p = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(p-1-0+1)]  # type: "List[int]"
    solve(p, a)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import functools
INF = float("inf")


def solve(p: int, a: "List[int]"):
    N = p+1
    MOD = p

    inv = [0]*N
    inv[1] = 1
    for i in range(2, N):
        inv[i] = -inv[MOD % i]*(MOD//i) % MOD

    b = [0]*p
    for ai, av in enumerate(a):
        if av == 0:
            continue

        c = 1
        d = 1
        for i in range(p-1, -1, -1):
            b[i] += - c * d
            b[i] %= p
            c = c * i * inv[p-i] % p
            d = -d*ai % p
        b[0] += 1
        b[0] %= p
    print(*b, sep=" ")
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    p = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(p-1-0+1)]  # type: "List[int]"
    solve(p, a)


if __name__ == '__main__':
    main()
### BUGGY 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 = 0
for i, bit in enumerate(x[::-1]):
    num += int(bit) * pow(2, i)
lbit = bitcount(18)
cnt = x.count('1')

for i in range(n):
    ans = 0
    if x[i] == '0':
        tmp = num + pow(2, n - (i + 1))
        ctmp = cnt + 1
    elif x[i] == '1':
        tmp = num - pow(2, n - (i + 1))
        ctmp = cnt -  1
    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)
### BUGGY CODE ###

l = input()
m = 10**9+7
ans = 0
k = 0
while len(l) > 1:
  c = 1
  for i in range(len(l)):
    ans = (ans+c*pow(2,i+k,m))%m
    c = c*(len(l)-1-i)//(i+1)
  j = 1
  while l[j] == '0':
    j += 1
    if j == len(l):
      j -= 1
      break
  l = l[j:]
  k += 1
ans = (ans+(2*int(l)+1)*pow(2,k,m))%m
print(ans)

### FIXED CODE ###

l = input()
m = 10**9+7
ans = 0
c = 1
while len(l) > 1:
  ans = (ans+c*pow(3,len(l)-1,m))%m
  j = 1
  while l[j] == '0':
    j += 1
    if j == len(l):
      j -= 1
      break
  l = l[j:]
  c = (2*c)%m
ans = (ans+(2*int(l)+1)*c)%m
print(ans)