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

import heapq
N, K = [int(_) for _ in input().split()]
V = [int(_) for _ in input().split()]
ans = 0
for il in range(min([N + 1, K + 1])):
    for ir in range(min([N + 1 - il, K + 1 - il])):
        for dl in range(il + 1):
            for dr in range(ir + 1):
                if il + ir + dl + dr > K:
                    continue
                HL = V[:il]
                HR = V[N - ir:N]
                heapq.heapify(HL)
                heapq.heapify(HR)
                value = 0
                for _ in range(dl):
                    v = heapq.heappop(HL)
                    if v >= 0:
                        value += v
                        break
                value += sum(HL)
                for _ in range(dr):
                    v = heapq.heappop(HR)
                    if v >= 0:
                        value += v
                        break
                value += sum(HR)
                ans = max([ans, value])
print(ans)


### FIXED CODE ###

import heapq
N, K = [int(_) for _ in input().split()]
V = [int(_) for _ in input().split()]
ans = 0
for il in range(K + 1):
    for ir in range(K + 1 - il):
        if il + ir > min([N, K]):
            continue
        H = V[:il] + V[N - ir:N]
        heapq.heapify(H)
        now = 0
        for d in range(1, il + ir):
            if il + ir + d > K:
                break
            v = heapq.heappop(H)
            if v >= 0:
                now += v
                break
        now += sum(H)
        ans = max([ans, now])
print(ans)
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())

A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

res = []
for a in range(X):
    for b in range(Y):
            res.append(A[a] + B[b])
            
res.sort(reverse=True)
result = []
for r in res:
    for c in C:
        result.append(r + c)
        
result.sort(reverse=True)

for i in range(K):
    print(result[i])
        

### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

C.sort(reverse=True)

tmp = []
for x in range(X):
    for y in range(Y):
        tmp.append(A[x] + B[y])
        
tmp.sort(reverse=True)

res = []
for i in range(min(K, X*Y)):
    for z in range(Z):
        res.append(tmp[i] + C[z])
 
res.sort(reverse=True)
for i in range(K):
    print(res[i])
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
C = [list(input()) for i in range(H)]
X = [1,0,-1,0]
Y = [0,-1,0,1]
INF = 10**9

Q = deque()
dist = [[INF]*W for i in range(H)]

for x in range(W):
  for y in range(H):
    if C[y][x] == "#":
      visited = [[0]*W for i in range(H)]
      visited[y][x] = 1
      Q.append((y,x))
      dist[y][x] = 0
      while Q:
        y,x = Q.popleft()
        for i in range(4):
          nx = x + X[i]
          ny = y + Y[i]
          if (0 <= nx < W) and (0 <= ny < H) and (visited[ny][nx] == 0) and (C[ny][nx] != "#"):
            visited[ny][nx] = 1
            dist[ny][nx] = min(dist[y][x] + 1,dist[ny][nx])
            Q.append((ny,nx))
ans = 0
for i in range(H):
  ans = max(ans,max(dist[i]))
print(ans)

### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
A = [input() for i in range(H)]
X = [1,0,-1,0]
Y = [0,-1,0,1]

INF = 99999
dp = [[-1]*W for i in range(H)]
q = deque()
for y, row in enumerate(A):
  for x,c in enumerate(row):
    if c == "#":
      dp[y][x] = 0
      q.append((y,x))
while q:
  y,x = q.popleft()
  d = dp[y][x]
  for i in range(4):
    nx = x + X[i]
    ny = y + Y[i]
    if (0 <= nx < W) and (0 <= ny < H) and (dp[ny][nx] == -1):
      dp[ny][nx] = d + 1
      q.append((ny,nx))
print(max(max(row) for row in dp))
### BUGGY CODE ###

# -*- coding:utf8 -*-

n = int(input())
s = [input() for _ in range(n)]
s = [''.join(sorted(i)) for i in s]
c = [list(range(s.count(i))) for i in set(s)]
t = [sum(i) for i in c if i != 1]
print(sum(t))

### FIXED CODE ###

# -*- coding:utf8 -*-
import collections

n = int(input())
s = [input() for _ in range(n)]
s = [''.join(sorted(i)) for i in s]
c = collections.Counter(s)
t = [range(i) for i in list(c.values()) if i != 1]
a = [sum(i) for i in t]
print(sum(a))
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)
c = sorted(list(map(int, input().split())), reverse=True)

a_b = []
for i in range(x):
    for j in range(y):
        a_b.append(a[i] + b[j])
a_b.sort(reverse=True)
ans = []
for i in range(min(k, len(a_b))):
    for j in range(min(k, z)):
        ans.append(a_b[i] + c[j])

ans.sort(reverse=True)
for i in range(k):
    print(ans[i])

### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)
c = sorted(list(map(int, input().split())), reverse=True)

ans = []
for i in range(x):
    for j in range(y):
        for l in range(z):
            if (i+1) * (j+1) * (l+1) <= k:
                ans.append(a[i] + b[j] + c[l])
            else:
                break

ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

S = list(map(int,input()))[::-1] #逆順

counter = 0
amari = [0]*2019
amari[0] = 1

s,d = 0,1

for i in S:
    s += i *d
    amari[s%2019] += 1
    d *= 10


for i in range(2019):
    counter += amari[i] * (amari[i]-1) / 2


print(int(counter))

### FIXED CODE ###

S = list(map(int,input()))[::-1] #逆順

counter = 0
amari = [0]*2019
amari[0] = 1

s,d = 0,1

for i in S:
    s += i *d
    amari[s%2019] += 1
    d *= 10
    d %= 2019


for i in range(2019):
    counter += amari[i] * (amari[i]-1) / 2


print(int(counter))
### BUGGY CODE ###

import math
N = int(input())
X = []
Y = []
for i in range(N):
  x, y = map(int, input().split())
  X += [x]
  Y += [y]
  
ans = 0
for i in range(1<<N):
  curr_x = 0
  curr_y = 0
  for j in range(N):
    if (1<<j)&i:
      curr_x += X[j]
      curr_y += Y[j]
  ans = max(ans, curr_x**2+curr_y**2)
  
print(math.sqrt(ans))

### FIXED CODE ###

import math
N = int(input())
xy = []
for i in range(N):
  x, y = map(int, input().split())
  xy += [(x, y, math.atan2(y,x))]
xy.sort(key=lambda val:val[2])
x_accum = [0]
y_accum = [0]
for i in range(N):
  x_accum += [x_accum[-1] + xy[i][0]]
  y_accum += [y_accum[-1] + xy[i][1]]
  
ans = 0
for i in range(N+1):
  for j in range(i,N+1):
    ans = max(ans,  math.hypot(x_accum[j]-x_accum[i] ,y_accum[j]-y_accum[i]))
    ans = max(ans,  math.hypot(x_accum[-1] -x_accum[j]+x_accum[i] ,y_accum[-1]-y_accum[j]+y_accum[i]))
print(ans)
### BUGGY CODE ###

# D - Sum of Divisors
N = int(input())

# 1と自分自身はかならず約数になるので、計算から除外
f = [2] * (N + 1)

for i in range(2, N//2 + 1):
	j = 2
	
	while True:
		if i * j <= N:
			f[i*j] += 1
			j += 1
		else:
			break

ans = 1

for i in range(2, N + 1):
	ans += f[i] * i

print(ans)

### FIXED CODE ###

# D - Sum of Divisors
N = int(input())
ans = (1 + N) * N

for i in range(2, N//2 + 1):
	j = 2
	
	while True:
		if i * j <= N:
			
			ans += i * j
			j += 1
		else:
			break

print(ans - 1)
### BUGGY CODE ###

N, M = map(int, input().split())
H = list(map(int, input().split()))
l = []
for i in range(M):
    A, B = map(int, input().split())
    if(H[A-1]>H[B-1]):l.append(B-1)
    elif(H[A-1]==H[B-1]):
      l.append(A-1)
      l.append(B-1)
    else:l.append(A-1)
l = list(set(l))
dellist = lambda items, indexes: [item for index, item in enumerate(items) if index not in indexes]
print(len(dellist(H,l)))

### FIXED CODE ###

N, M = map(int, input().split())
H = list(map(int, input().split()))
l = []
for i in range(M):
    A, B = map(int, input().split())
    if(H[A-1]>H[B-1]):l.append(B-1)
    elif(H[A-1]==H[B-1]):
      l.append(A-1)
      l.append(B-1)
    else:l.append(A-1)
l = list(set(l))
print(len(H)-len(l))
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
total = sum(a)
divisor = []
for i in range(int(total ** 0.5)):
    if total % (i + 1) == 0:
        divisor.append(i + 1)
        divisor.append(total // (i + 1))
divisor.sort(reverse = True)
i = 0
while True:
    num = divisor[i]
    a2 = [a[j] % num for j in range(n)]
    count = 0
    res = 0
    while a2:
        test = min(a2)
        a2.remove(test)
        count += test
        res += test
        while res:
            test2 = max(a2)
            if res >= num - test2:
                res -= num - test2
                a2.remove(test2)
            else:
                a2[a2.index(test2)] += res
                res = 0
    if count <= k:
        break
    else:
        i += 1
print(num)

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
total = sum(a)
divisor = []
for i in range(int(total ** 0.5)):
    if total % (i + 1) == 0:
        divisor.append(i + 1)
        divisor.append(total // (i + 1))
divisor.sort(reverse = True)
i = 0
while True:
    num = divisor[i]
    a2 = [a[j] % num for j in range(n)]
    count = 0
    res = 0
    while a2:
        test = min(a2)
        a2.remove(test)
        count += test
        res += test
        while res:
            test2 = max(a2)
            if res >= num - test2:
                res -= num - test2
                a2.remove(test2)
            else:
                a2[a2.index(test2)] += res
                res = 0
    if count <= k:
        break
    else:
        i += 1
print(num)
### BUGGY CODE ###

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

n1 = X.count("1")
Xn = int(X, 2)

Xms = (Xn % (n1 - 1)) if n1 > 1 else 0
Xml = Xn % (n1 + 1)

p2s = [1]
p2l = [1]
s2 = 1
l2 = 1
for i in range(N - 1):
    s2 = (s2 * 2) % (n1 - 1) if n1 > 1 else 0
    l2 = (l2 * 2) % (n1 + 1)
    p2s.append(s2)
    p2l.append(l2)


def f(n):
    if n == 0:
        return 0
    return f(n % bin(n).count("1")) + 1


for i in range(N):
    cnt = 0
    p2 = 2 ** (N - i - 1)
    Xim = 0

    if X[i] == "1" and n1 == 1:
        print(cnt)
        continue
    elif X[i] == "1":
        Xim = (
            Xms - p2s[-i - 1]
            if Xms - p2s[-i - 1] >= 0
            else ((n1 - 1) + (Xms - p2s[-i - 1]))
        )
    else:
        Xim = (
            Xml + p2l[-i - 1]
            if Xml + p2l[-i - 1] < (n1 + 1)
            else (Xml + p2l[-i - 1] - (n1 + 1))
        )
    print(f(Xim) + 1)



### FIXED CODE ###

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

n1 = X.count("1")
Xn = int(X, 2)

Xms = (Xn % (n1 - 1)) if n1 > 1 else 0
Xml = Xn % (n1 + 1)

p2s = [1]
p2l = [1]
s2 = 1
l2 = 1
for i in range(N - 1):
    s2 = (s2 * 2) % (n1 - 1) if n1 > 1 else 0
    l2 = (l2 * 2) % (n1 + 1)
    p2s.append(s2)
    p2l.append(l2)

for i in range(N):
    cnt = 0
    p2 = 2 ** (N - i - 1)
    Xim = 0

    if X[i] == "1" and n1 == 1:
        print(cnt)
        continue
    elif X[i] == "1":
        Xim = (
            Xms - p2s[-i - 1]
            if Xms - p2s[-i - 1] >= 0
            else ((n1 - 1) + (Xms - p2s[-i - 1]))
        )
    else:
        Xim = (
            Xml + p2l[-i - 1]
            if Xml + p2l[-i - 1] < (n1 + 1)
            else (Xml + p2l[-i - 1] - (n1 + 1))
        )

    cnt += 1
    while Xim > 0:
        Xim %= bin(Xim).count("1")
        cnt += 1
    print(cnt)
### BUGGY CODE ###

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

res = 1
for v in a:
    res *= v

if res <= 10 ** 18:
    print(res)
else:
    print(-1)

### FIXED CODE ###

import sys

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

if 0 in a:
    print(0)
    sys.exit()

res = 1
for v in a:
    res *= v
    if res > 10 ** 18:
        print(-1)
        sys.exit()

print(res)
### BUGGY CODE ###

n = int(input())
a = [int(x) for x in input().split()]

mp = 1
EvenOdd = ""
for i in range(len(a)):
    mp *= a[i]
    if mp < 0:
        EvenOdd = "Odd"
    else:
        EvenOdd = "Even"

sm = 0
for i in range(len(a)):
    sm += abs(a[i])
if EvenOdd == "Even":
    print(sm)
else:
    min_a = min(abs(a[i]) for i in range(len(a)))
    print(sm - min_a*2)

### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]

abs_a = list(map(abs, a))
sm_abs_a = sum(abs_a)
min_a = min(abs(a[i]) for i in range(len(a)))

cnt = 0
for i in range(len(a)):
    if a[i] < 0:
        cnt += 1

if cnt%2 == 0:
    print(sm_abs_a)
else:
    print(sm_abs_a - min_a*2)
### BUGGY CODE ###

[N,X,Y] = [int(s) for s in input().rstrip().split(' ')]
L = [] #L[i][j]はi,j間の最短距離(i<=j)
for i in range(N):
  L.append([10**4 for j in range(N-i)])
for i in range(N):
  L[i][0] = 0
  if i < N-1:
    L[i][1] = 1
L[X-1][Y-X] = 1
for k in range(1,N):
  a = 0
  for i in range(N):
    for j in range(N-i):
      if L[i][j] == k:
        a += 1
      elif L[i][j] > k:
        for p in range(N):
          if p < i:
            if L[p][i-p] + L[p][i+j-p] < L[i][j]:
              L[i][j] = L[p][i-p] + L[p][i+j-p]
          elif p < i+j:
            if L[i][p-i] + L[p][i+j-p] < L[i][j]:
              L[i][j] = L[i][p-i] + L[p][i+j-p]
          else:
            if L[i][p-i] + L[i+j][p-i-j] < L[i][j]:
              L[i][j] = L[i][p-i] + L[i+j][p-i-j]
  print(a)

### FIXED CODE ###

[N,X,Y] = [int(s) for s in input().rstrip().split(' ')]
L = [0 for n in range(N)]
for i in range(N):
  for j in range(N-i):
    L[min(j,abs(X-1-i)+abs(Y-1-i-j)+1,abs(X-1-j-i)+abs(Y-1-i)+1)]+=1
for k in range(1,N):
  print(L[k])
### BUGGY CODE ###

from bisect import bisect_left
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
for i in range(M):
    B, C = map(int, input().split())
    b = bisect_left(A,C)
    if B>=b:
        A[:b] = [C for _ in range(b)]
    else:
        A[:B] = [C for _ in range(B)]
    A.sort()
print(sum(A))


### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int,input().split())) for _ in range(M)]
BC = sorted(BC,key= lambda x: x[1],reverse=True)
A.sort()
n = 0
i = 0
m = 0
while A[i]<BC[n][1]:
    A[i] = BC[n][1]
    m = m+1
    if m >=BC[n][0]:
        m = 0
        n = n+1
    i += 1
    if n==M:
      break
    if i == N:
      break
print(sum(A))
### BUGGY CODE ###

# cook your dish here
# from math import * 
#for _ in range(int(input().strip())):

s = input()
k = int(input())
var = 0
sub = set()

for var in range(97,123):
    if len(sub)>k:
        break
    for i in range(len(s)):
        if s[i]==chr(var):
            for j in range(i,len(s)):
                sub.add(s[i:(j+1)])
l = list(sub)
l.sort()
print(l[k-1])

### FIXED CODE ###

# cook your dish here
# from math import * 
#for _ in range(int(input().strip())):

s = input()
k = int(input())
var = 0
sub = set()
size = 0
for var in range(97,123):
    if len(sub)>k:
        break
    for i in range(len(s)):
        size=0
        if s[i]==chr(var):
            for j in range(i,len(s)):
                if size>=k:
                    break
                sub.add(s[i:(j+1)])
                size+=1 
l = list(sub)
l.sort()
print(l[k-1])
### BUGGY CODE ###

n,m=map(int,input().split())
ls=[int(input()) for i in range(m)]
ls=set(ls)

def dp(n,ls):
    dp_table=[[0 for i in range(n+1)]]
    dp_table[0][0]=1
    sum=0
    count=1
    edge=0
    while True:
        row=[0]*count
        previous=dp_table[-1]
        for i in range(count,n+1):
            if i in ls:
                row.append(0)
            elif i==0:
                row.append(0)
            elif i==1:
                row.append(previous[0])
            else:
                row.append(previous[i-1]+previous[i-2])
            if i==edge+2:
                edge=i
                row=row+([0]*(n-edge))
                break
        sum+=row[-1]
        if row.count(0)==n+1:
            return sum
        dp_table.append(row)
        count+=1
 
print(dp(n,ls)%1000000007)

### FIXED CODE ###

n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
a = set(a)
mod = 10**9+7
dp = [0]*(n+1)
dp[0] = 1
if 1 not in a:
    dp[1] = 1
for i in range(2,n+1):
    if i not in a:
        dp[i] = dp[i-1]+dp[i-2]
print(dp[-1]%mod)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
import itertools 
def findsubsets(s, n): 
    return list(itertools.combinations(s, n))
s = set(range(0, n))
com = findsubsets(s, 3)
c = 0
fin = []
for i in com:
    tem = list(i)
    tem.sort()
    fin.append(tem)
l.sort()
for i in fin:
    if l[i[0]] + l[i[1]] > l[i[2]]: c += 1
print(c)

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
  n = int(input())
  l = list(map(int, input().split()))
  l.sort()
  l.append(99999999)
  c = 0
  for i in range(n - 2):
      t = i + 2
      for j in range(i + 1, n - 1):
          for k in range(t, n + 1):
              if l[i] + l[j] <= l[k]:
                  t = k
                  break
          if t > j: c += t - j - 1
          if j + 1 == t: t += 1
  print(c)
if __name__ == "__main__":
  main()
### BUGGY CODE ###

N,C = map(int,input().split())
STC = []
for _ in range(N):
  s,t,c = map(int,input().split())
  STC.append([s,t,c])
STC.sort()

rs = [[STC[0][1],STC[0][2]]]
for i in range(1,N):
  len_rs = len(rs)
  
  min_idx = None
  for j in range(len_rs):
    if rs[j][1] != STC[i][2]: tmp_stc_r = STC[i][0] - 0.5
    else: tmp_stc_r = STC[i][0]
 
    if rs[j][0] <= tmp_stc_r:
      if min_idx is None: min_idx = j
      else:
        if rs[j][0] < rs[min_idx][0]: min_idx = j

  if min_idx is None: rs.append([STC[i][1], STC[i][2]])
  else: rs[min_idx] = [STC[i][1], STC[i][2]]
  
  rs.sort()
print(len(rs))

### FIXED CODE ###

import sys

N,C = map(int,input().split())
STC = []
for _ in range(N):
  s,t,c = map(int,sys.stdin.readline().split())
  STC.append([s,t,c])
STC.sort()

rs = [[STC[0][1],STC[0][2]]]
for i in range(1,N):
  len_rs = len(rs)
  
  min_idx = None
  for j in range(len_rs):
    if rs[j][1] != STC[i][2]: tmp_stc_r = STC[i][0] - 0.5
    else: tmp_stc_r = STC[i][0]
 
    if rs[j][0] <= tmp_stc_r:
      if min_idx is None: min_idx = j
      else:
        if rs[j][0] < rs[min_idx][0]: min_idx = j

  if min_idx is None: rs.append([STC[i][1], STC[i][2]])
  else: rs[min_idx] = [STC[i][1], STC[i][2]]
  
print(len(rs))
### BUGGY CODE ###

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

### FIXED CODE ###

from collections import defaultdict
d = defaultdict(int)
N = int(input())
arr = list(map(int, input().split()))
ans = 0
for i in range(N):
    ans += d[(i+1)-arr[i]]
    d[(i+1)+arr[i]] += 1
print(ans)
### BUGGY CODE ###

s = input()
n = len(s)
x = int(s)

a = [0]*2019
count = 0
val = 10
for i in range(n):
    tmp = (x % val) % 2019
    count = count + a[tmp]
    a[tmp] = a[tmp] + 1
    if(tmp == 0):
        count = count + 1
    val = val * 10

print(count)

### FIXED CODE ###

s = input()[::-1]
n = len(s)

a = [0]*2019
a[0] = 1
count = 0
val = 1
current = 0
for c in s:
    current = (current + val * int(c)) % 2019
    count += a[current%2019]
    a[current%2019] += 1
    val = val * 10 % 2019

print(count)
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline
N,M,L = map(int,input().split())
load = [[]for i in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    if c > L:
        continue
    load[a-1].append([b-1,c])
    load[b-1].append([a-1,c])
cost =[[float('inf')]*N for i in range(N)]
for i in range(N):
    queue = deque([i])
    cost[i][i] = 0
    while(queue):
        q = queue.popleft()
        gas = cost[i][q]
        for t,c in load[q]:
            if gas//L < (gas+c-1)//L :
                if (gas//L+1)*L+c < cost[i][t]:
                    cost[i][t] = (gas//L+1)*L+c
                    queue.append(t)
            else:
                if gas+c < cost[i][t]:
                    cost[i][t] = gas+c
                    queue.append(t)
Q = int(input())
for _ in range(Q):
    s,t = map(int,input().split())
    ans = cost[s-1][t-1]
    if ans == float('inf'):
        print(-1)
    else:
        print((ans-1)//L)
     


### FIXED CODE ###

import sys
imput = sys.stdin.readline
def func(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])
    return d
N,M,L = map(int,input().split())
road = [[10**10]*N for i in range(N)]
for i in range(N):
    road[i][i] = 0
for i in range(M):
    a,b,c = map(int,input().split())
    road[a-1][b-1] = c
    road[b-1][a-1] = c
road = func(road)
ans = [[10**5]*N for i in range(N)]
for i in range(N):
    for j in range(N):
        if road[i][j] <= L:
            ans[i][j] = 1
ans = func(ans)
for i in range(int(input())):
    a,b = map(int,input().split())
    o = ans[a-1][b-1]
    if o == 10**5:
        print(-1)
    else:
        print(o-1)
### BUGGY CODE ###

N = int(input())
X_bin = input()

X_int = int(X_bin, 2)  # bin => int


def calc_bin_cnt(next_int):
    if next_int == 0:
        return 0
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    if next_int == 0:
        return 0
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    return ans


#X_cnt = calc_bin_cnt(X_int)
X_cnt = X_bin.count('1')
for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1)), X_cnt-1))
    else:
        print(calc_ans(X_int + (2**(N-i-1)), X_cnt+1))


### FIXED CODE ###

N = int(input())
X_bin = input()
#N = 10**5
#X_bin = '1' * N

X_int = int(X_bin, 2)  # bin => int


def calc_bin_cnt(next_int):
    if next_int == 0:
        return 0
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    if next_cnt == 0:
        return 0
    if next_int == 0:
        return 1
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    return ans


X_cnt = calc_bin_cnt(X_int)
f_p = X_int % (X_cnt+1)
if X_cnt-1 == 0:
    f_m = 0
else:
    f_m = X_int % (X_cnt-1)
for i in range(N):
    if X_bin[i] == '1':
        next_cnt = X_cnt - 1
        if next_cnt == 0:
            next_int = 0
        else:
            next_int = f_m - pow(2, (N-i-1), next_cnt)  # マイナスでも正しく求まる？
    else:
        next_cnt = X_cnt + 1
        next_int = f_p + pow(2, (N-i-1), next_cnt)
    print(calc_ans(next_int, next_cnt))
    #calc_ans(next_cnt, next_cnt)
### BUGGY CODE ###

import math , sys

N = int( input() )
A = list( map( int, input().split() ))
A.sort()
Cs = [0 for _ in range(10**6+1)]

#print(A)

for e in A:
    if A.count(e)==1:
        Cs[e] = 1
#print(Cs[:30])
for e in A:
    i = 2
    while e*i < 10**6+1:
        Cs[e*i] = 0
        i+=1
ans = sum(Cs)
print(ans)


### FIXED CODE ###

import math , sys

N = int( input() )
A = list( map( int, input().split() ))
A.sort()
Cs = [0 for _ in range(10**6+1)]
M = A[-1]
#print(A)
i=0
M = max(A)
for i in range(N):
    e = A[i]
    if Cs[e]==1:
        Cs[e]=2
    elif Cs[e]==0:
        Cs[e]=1

for i in range(len(Cs)):
    Cs[i] = Cs[i]%2

for e in A:
    i = 2
    while e*i <= M:
        Cs[e*i] = 0
        i+=1
ans = sum(Cs)
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
from fractions import gcd
def lcm(x,y):
  return x*y // gcd(x, y)
q = a[0]//2
for i in range(n):
  a[i] = a[i]//2
  q = lcm(q,a[i])

cnt = 0
flag = 1
while flag:
  for i in range(n):
    if a[i] % 2 == 1:
      cnt += 1
    else:
      a[i]//1
    if cnt != 0:
      flag = 0
ans = (m//q) - (m//(2*q))
if cnt == n:
  print(ans)
else:
  print(0)

### FIXED CODE ###

from math import gcd
def lcm(x,y):
    return x*y//gcd(x,y)
def cnt(x):
    i = 0
    while x%2 == 0:
        x = x//2
        i += 1
    return i 
n,m = map(int,input().split())
a = list(map(int,input().split()))
memo = cnt(a[0])
for i in range(n):
    if cnt(a[i]) != memo:
        print(0)
        quit()
    a[i] = a[i]//2

t = 1
for i in range(n):
    t = lcm(t,a[i])
print(m//t-m//(2*t))