Harryxun/stf_run huggingface dataset:
#!/usr/bin/env python3
import sys

def dfs(idx, con, visited):
    visited[idx] = True
    max_depth = 0
    max_len = 0
    depths = []
    if idx >= len(con):
        return max_depth, max_len
    for v in con[idx]:
        if v < len(visited) and not visited[v]:
            max_d, max_l = dfs(v, con, visited)
            max_len = max(max_len, max_l)
            depths.append(max_d + 1)
    if len(depths) > 0:
        depths.sort(reverse=True)
        max_depth = depths[0]
        if len(depths) > 1:
            max_len = max(max_len, depths[0] + depths[1])
        else:
            max_len = max(max_len, depths[0])
    visited[idx] = False
    return max_depth, max_len


def solve(N: int, A: "List[int]", B: "List[int]"):
    con = [[] for _ in range(N)]
    for i in range(len(A)):
        a = A[i] - 1
        b = B[i] - 1
        con[a].append(b)
        con[b].append(a)
    #print(con)
    visited = [False] * N
    max_depth, max_len = dfs(0, con, visited)
    #print(max_len)
    if (max_len + 1) % 3 == 2:
        ret = 'Second'
    else:
        ret = 'First'
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N-1)  # type: "List[int]" 
    b = [int()] * (N-1)  # type: "List[int]" 
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)

def dfs(idx, con, visited):
    visited[idx] = True
    max_depth = 0
    max_len = 0
    depths = []
    if idx >= len(con):
        return max_depth, max_len
    for v in con[idx]:
        if v < len(visited) and not visited[v]:
            max_d, max_l = dfs(v, con, visited)
            max_len = max(max_len, max_l)
            depths.append(max_d + 1)
    if len(depths) > 0:
        depths.sort(reverse=True)
        max_depth = depths[0]
        if len(depths) > 1:
            max_len = max(max_len, depths[0] + depths[1])
        else:
            max_len = max(max_len, depths[0])
    visited[idx] = False
    return max_depth, max_len


def solve(N: int, A: "List[int]", B: "List[int]"):
    con = [[] for _ in range(N)]
    for i in range(len(A)):
        a = A[i] - 1
        b = B[i] - 1
        con[a].append(b)
        con[b].append(a)
    #print(con)
    visited = [False] * N
    max_depth, max_len = dfs(0, con, visited)
    #print(max_len)
    if (max_len + 1) % 3 == 2:
        ret = 'Second'
    else:
        ret = 'First'
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N-1)  # type: "List[int]" 
    b = [int()] * (N-1)  # type: "List[int]" 
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)

if __name__ == '__main__':
    main()
S = input()
ls = len(S)

def dfs(i):
    if i == ls:
        return True
    elif S[i: i+5] == "dream" or S[i: i+5] == "erase" or S[i: i+6] == "eraser" or S[i: i+7] == "dreamer":
        return dfs(i+5) or dfs(i+6) or dfs(i+7)

    return False

if dfs(0):
    print("YES")
else:
    print("NO")

### FIXED CODE ###

S = input()[::-1]
i = 0
ls = len(S)
accept = True

while ls > i:
    if S[i: i+5] == "maerd" or S[i: i+5] == "esare":
        i += 5
    elif S[i: i+6] == "resare":
        i += 6
    elif S[i: i+7] == "remaerd":
        i += 7
    else:
        accept = False
        break

if accept:
    print("YES")
else:
    print("NO")
n=int(input())
if n<105:
    print(0)
elif 105<=n and n<135:
    print(1)
elif 135=n and n<175:
    print(2)
elif 175<=n and n<189:
    print(3)
else:
    print(4)

    

### FIXED CODE ###

n=int(input())
ans=0
for i in range(1,n+1,2):
    cnt=0
    for j in range(1,n+1):
        if i%j==0:
            cnt+=1
    if cnt==8:
        ans+=1
print(ans)
import sys
sys.setrecursionlimit(10000)

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

A = []
B = []

for i in range(M):
    a, b = [int(x) for x in input().split()]
    A.append(a)
    B.append(b)

A.reverse()
B.reverse()


# ----- Union Find -----------
PARENT = list(range( N + 1 ))
SIZE = [1] * (N + 1 )

def root(n):
    if PARENT[n] == n:
        return n
    else:
        ret = root(PARENT[n])
        PARENT[n] = ret
        return ret

def same(n1, n2):
    return root(n1) == root(n2)


def unite(n1, n2):
    n1 = root(n1)
    n2 = root(n2)
    if n1 == n2:
        return
    PARENT[n1] = n2
    global g
    g = g + SIZE[n2] * SIZE[n1]
    SIZE[n2] += SIZE[n1]
    SIZE[n1] = 0

Z = N * (N - 1) // 2

ans = []
for i in range(M):
    a, b = A[i], B[i]
    unite(a, b)
    # print(PARENT[1:])
    # print(SIZE[1:])
    # print(g)
    # print(Z - g)
    ans.append(Z - g)
    # print("----")

ans.reverse()
del ans[0]
for a in ans:
    print(a)
print(Z)


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

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

A = []
B = []

for i in range(M):
    a, b = [int(x) for x in input().split()]
    A.append(a)
    B.append(b)

A.reverse()
B.reverse()


# ----- Union Find -----------
PARENT = list(range( N + 1 ))
SIZE = [1] * (N + 1 )

def root(n):
    if PARENT[n] == n:
        return n
    else:
        ret = root(PARENT[n])
        PARENT[n] = ret
        return ret

def same(n1, n2):
    return root(n1) == root(n2)


def unite(n1, n2):
    n1 = root(n1)
    n2 = root(n2)
    if n1 == n2:
        return
    PARENT[n1] = n2
    global g
    g = g + SIZE[n2] * SIZE[n1]
    SIZE[n2] += SIZE[n1]
    SIZE[n1] = 0

Z = N * (N - 1) // 2

ans = []
for i in range(M):
    a, b = A[i], B[i]
    unite(a, b)
    # print(PARENT[1:])
    # print(SIZE[1:])
    # print(g)
    # print(Z - g)
    ans.append(Z - g)
    # print("----")

ans.reverse()
del ans[0]
for a in ans:
    print(a)
print(Z)
from heapq import heappop, heapify, heappush


def main():
    n, m = map(int, input().split())
    work = [[] for _ in range(10 ** 4 + 1)]
    for _ in range(n):
        a, b = map(int, input().split())
        work[a].append(b)
    ans = 0
    q = []
    heapify(q)
    for i in range(1, m + 1):
        for w in work[i]:
            heappush(q, -w)
        if len(q) == 0:
            continue
        print(q)
        ans += heappop(q)
    ans *= -1
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from heapq import heappop, heapify, heappush


def main():
    n, m = map(int, input().split())
    work = [[] for _ in range(10 ** 5 + 1)]
    for _ in range(n):
        a, b = map(int, input().split())
        work[a].append(b)
    ans = 0
    q = []
    heapify(q)
    for i in range(1, m + 1):
        for w in work[i]:
            heappush(q, -w)
        if len(q) == 0:
            continue
        ans += heappop(q)
    ans *= -1
    print(ans)


if __name__ == '__main__':
    main()
while True:
    (n, x) = [int(i) for i in input().split()]
    if n == x == 0:
        break

    count = 0 
    for a int range(1, n + 1 - 2): 
        for b in range(a + 1, n + 1 - 1 ):
            for c in range(b + 1, n + 1): 
                if (a + b + c) == x:
                    count += 1
    print(count)

### FIXED CODE ###

while True:
    (n, x) =  [int(i) for i in input().split()]
    if n == x == 0:
        break
 
    count = 0
    for a in range(1, n+1):
        for b in range(a+1, n+1):
            for c in range(b+1, n+1):
                if (a + b + c) == x:
                    count += 1
                elif (a + b + c) > x:
                    break
    print(count)
n, k, q = map(int, input().split())
a = [int(input()) for _ in range(q)]
sc = {i : k for i in range(1, n+1)}
sc[0] = 0

for s in a:
  for i in range(1, n+1):
    if i == s:
      continue
    
    sc[i] -= 1

del sc[0]
for s in sc.values():
  print("Yes" if s > 0 else "No")

### FIXED CODE ###

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

h.reverse()
ans = 0
temp = 0
for i in range(n-1):
    if h[i+1] >= h[i]:
        temp += 1
    else:
        ans = max(temp, ans)
        temp = 0

ans = max(temp, ans)
print(ans)
N, M = map(int, input().split()) 

ans = []
if M % 2 != 0:
    for i in range((M+1)//2):
        ans.append((1 + i,M - i))
        
    for j in range((M - 1)//2):
        ans.append((M + 1 + j, 2*M + 1 - j))
else:
    for i in range(M//2):
        ans.append((1 + i, M + 1 - i))
        ans.append((M + 2 + j, 2*M + 1 - j))
              
for i in range(M):
    print(*ans[i])

### FIXED CODE ###

N, M = map(int, input().split()) 
ans = []
if M % 2 != 0:
    for i in range((M + 1)//2):
        ans.append((1 + i, M + 1 - i))
        
    for j in range((M - 1)//2):
        ans.append((M + 2 + j, 2*M + 1 - j))
else:
    for i in range(M//2):
        ans.append((1 + i, M + 1 - i))
        ans.append((M + 2 + i, 2*M + 1 - i))
              
for i in range(M):
    print(*ans[i])
n = input()
data = []
for i in ['S', 'H', 'C', 'D']:
    for j in map(str , xrange(1, 14)):
        data.append(i + j)   
for i in xrange(n):
    data.remove(raw_input())
for i in xrange(len(data)):
    print data[i]

### FIXED CODE ###

n = input()
data = []
space = []
for i in ['S ', 'H ', 'C ', 'D ']:
    for j in map( str , xrange(1, 14)):
        data.append(i + j)   
for i in xrange(n):
    data.remove(raw_input())
for i in xrange(len(data)):
    print data[i]
n = int(input())
As = list(map(int, input().split()))

# four = sum([1 for a in As if a%4 == 0])
# odd = sum([1 for a in As if a%2 == 1])
# two = sum([1 for a in As if a%2 == 0 and a%4 != 0])
four = 0
odd = 0
two = 0
for a in As:
    if a % 2 == 1:
        odd += 1
    elif a % 4 == 0:
        four += 1
    else:
        two += 1


if four < two%2 + odd - 1:
    print("No")
else:
    print("Yes")


fields @timestamp, @message
| sort @timestamp desc
| filter 
| limit 20

### FIXED CODE ###

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

four = sum([1 for a in As if a%4 == 0])
odd = sum([1 for a in As if a%2 == 1])
two = sum([1 for a in As if a%2 == 0 and a%4 != 0])
if four < two%2 + odd - 1:
    print("No")
else:
    print("Yes")
import math

S = input().split()
A = int(S[0])
B = int(S[1])
C = int(S[2])
D = int(S[3])

E = C * D / math.gcd(C, D)
X = (B//C)-(A//C)
Y = (B//D)-(A//D)
Z = (B//(E))-(A//(E))+1

print(int(B-A-X-Y+Z))


### FIXED CODE ###


def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

 #最小公倍数


def lcm(a, b):
    return a*b//gcd(a, b)


S = input().split()
A = int(S[0])
B = int(S[1])
C = int(S[2])
D = int(S[3])

E = lcm(C, D)

X = int(B//C)-int((A-1)//C)
Y = int(B//D)-int((A-1)//D)
Z = int(B//E)-int((A-1)//E)

print(B-A+1-X-Y+Z)
print((lambda x:x* x-~/2)(int(input())))

### FIXED CODE ###

print(sum([int(i) for i in range(int(input())+1)]))
s = str(input())

if s = "SUM":
  print(7)
elif s = "MON":
  print(6)
elif s = "TUE":
  print(5)
elif s = "WED":
  print(4)
elif s = "THU":
  print(3)
elif s = "FRI":
  print(2)
else s = "SUT":
  print(1)
  

### FIXED CODE ###

s = str(input())
 
if s == "SUN":
  print(7)
elif s == "MON":
  print(6)
elif s == "TUE":
  print(5)
elif s == "WED":
  print(4)
elif s == "THU":
  print(3)
elif s == "FRI":
  print(2)
else:
  print(1)
N=int(input())
n=[input()[0] for _ in range(N)]
m,a,r,c,h=n.count("M"),n.count("A"),n.count("R"),n.count("C"),n.count("H")
print(m*a*(r+c+h)+m*r*(c+h)+m*c*h+a*r*(c+h)+a*c*h+r*c*h)

### FIXED CODE ###

print(int(input())//3)
N = int(input().split())
V = list(map(int, input().split()))
C = list(map(int, input().split()))
P = []
for i in range(N):
    p = V[i]-C[i]
    if p >0:
    	P.append(p)

print(sum(P))

### FIXED CODE ###

N = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))
P = []
for i in range(N):
    p = V[i]-C[i]
    if p >0:
    	P.append(p)

print(sum(P))
If x => 30:
  print(yes)
  
else:
  print(No)

### FIXED CODE ###

x = int(input())
if x >= 30:
  print("Yes")
else:
  print("No")
import numpy as np
import math

A,B,C,D = map(int,input().split())
BA = np.arange(A, B+1)
BA_C = BA % C
BA_D = BA % D
BA_CD = BA % (C * D//math.gcd(C, D))

C_count = np.count_nonzero(BA_C == 0)
D_count = np.count_nonzero(BA_D == 0)
CD_count = np.count_nonzero(BA_CD == 0)

print(len(BA)-(C_count+D_count-CD_count))

### FIXED CODE ###

from fractions import gcd

A, B, C, D = map(int, input().split())
l = C * D // gcd(C, D)
x = (A - 1) - (A - 1) // C - (A - 1) // D + (A - 1) // l
y = B - B // C - B // D + B // l
print(y - x)
n,k,q=map(int,input().split())
a=list(int(input()) for i in range(q))

if k>q:
    for i in range(n):
        print('Yes')
else:
    for i in range(n):
        ans=a.count(i+1)
        if ans+k>q:
            print('Yes')
        else:
            print('No')


### FIXED CODE ###

s=input()
print('Sunny' if s=='Rainy' else 'Cloudy' if s=='Sunny' else'Rainy')
s = [input() for _ in range(int(input()))]
t = [input() for _ in range(int(input()))]

print(max(0,max(s.count(s[i]) - t.count(s[i]) for i in range(len(S)))))

### FIXED CODE ###

s = [input() for _ in range(int(input()))]
t = [input() for _ in range(int(input()))]

print(max(0,max(s.count(s[i]) - t.count(s[i]) for i in range(len(s)))))
n = int(input())
c = 0
for i in range(n):
  x, u = map(int, input().split())
  if u == "BTC":
    x *= 380000
  c += x
print(c)

### FIXED CODE ###

n = int(input())
c = 0
for i in range(n):
  x, u = map(lambda x:float(x) if x.replace(".", "").isdigit() else x, input().split())
  if u == "BTC":
    x *= 380000
  c += x
print(c)
N, K = map(int, input().split())
S = input()

def f1(s, l, r):
  return s[:l] + f2(s[l:r + 1]) + s[r + 1]

def f2(s):
  t = list(s)
  t.reverse()
  return ''.join('R' if c == 'L' else 'L' for c in t)

def f3(s):
  before = s[0]
  result = 0
  for i in range(1, N):
    if s[i] == before:
      result += 1
    else:
       before = s[i]
  return result

def f4(s, c):
  lstart = -1
  llen = 0
  tstart = -1
  for i in range(N):
    if s[i] == c and tstart == -1:
      tstart = i
    if s[i] != c and tstart != -1:
      tlen = i - tstart
      if tlen > llen:
        lstart = tstart
        llen = tlen
  return (lstart, llen)

for _ in range(K):
  lstart, llen = f4(S, 'L')
  rstart, rlen = f4(S, 'R')
  if lstart < rstart:
    S = f2(S, lstart + llen, rstart + rlen - 1)
  else:
    S = f2(S, rstart + rlen, lstart + llen - 1)
  if lstart == -1 or rstart == -1:
    break

print(f3(S))

### FIXED CODE ###

N, K = map(int, input().split())
S = input()
c = 0
for i in range(1, N):
  if S[i] == S[i - 1]:
    c += 1
print(min(N - 1, c + K * 2))
#!/usr/bin/env python
# -*- coding:utf-8 -*-

K = int(input())

def digit(i):
    if i>0:
        return digit(i//10)+[i%10]
    else:
        return []

def Sooo(N):
    return float(N/sum(digit(N)))
base=1
A=[]
for i in range(0,16):
    for j in range(1,151):
        re=base*(j+1)-1
        A.append(int(re))
    base = base*10
A = list(set(A))
A.sort()
l=len(A)
for i in range(0,len(A)):
    for j in range(i+1,len(A)):
        N=Sooo(A[i])
        M=Sooo(A[j])
        if N>M:
            A[i]=0
            break;

A = list(set(A))
A.sort()
for i in range(K):
    print(A[i+1])

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding:utf-8 -*- 
S = list(input())
Ans=0
for i in S:
    if i=="+":
        Ans = Ans+1
    else:
        Ans = Ans-1
print(Ans)
N,M,X = map(int,input().split())
C = []
A = []
success = []

for i in range(N):
    Z = list(map(int,input().split()))
    C.append([Z[0],i])
    A.append(Z[1:])

C.sort()
n = len(C)
items = []
for i in range(2 ** n):
    item = []
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            item.append(C[j])  # フラグが立っていたら bag に果物を詰める
    items.append(item)

print(items)
for i in range(1,len(items)):
    sum = 0
    a1 = 0
    a2 = 0
    a3 = 0
    for j in range(len(items[i])):
        index = items[i][j][1]
        a1 += A[index][0]
        a2 += A[index][1]
        a3 += A[index][2]
        sum += items[i][j][0]
    if a1 >= X and a2 >= X and a3 >= X:
        success.append(sum)
if len(success) == 0:
    print(-1)
else:
    print(min(success))

### FIXED CODE ###

from itertools import  product
N,M,X = map(int,input().split())
ca = [list(map(int,input().split())) for _ in range(N)]
for i in range(1,M+1):
    count=0
    for j in range(N):
        count+=ca[j][i]
    if count<X:
        print(-1)
        exit()

ans = 10**9
for z in product((0, 1), repeat=N):#bit全探索のくみあわせを勝手に作ってくれるので使うとよい
    count=0
    count2=[0]*M
    for i in range(N):
        if z[i]==1:
            count+=ca[i][0]
            for j in range(1,M+1):
                count2[j-1]+=ca[i][j]
    
    for i in range(M):
        if count2[i]<X:
            break
    else:
        ans=min(count,ans)
print(ans)
def dfs(G,s):
    for nv in G[s]:
        Count[nv]+=Count[s]
        dfs(G,nv)
    
N,Q=map(int,input().split())
Count=[0]*N
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
for i in range(Q):
    p,x=map(int,input().split())
    Count[p-1]+=x
dfs(G,0)
print(*Count)

### FIXED CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)
def dfs(G,s,p):
    for nv in G[s]:
        if(nv==p):
            continue
        Count[nv]+=Count[s]
        dfs(G,nv,s)
    
N,Q=map(int,input().split())
Count=[0]*N
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
for i in range(Q):
    p,x=map(int,input().split())
    Count[p-1]+=x
dfs(G,0,-1)
print(*Count)
import numpy as np

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def gcd_mul(numbers):
    s = gcd(numbers[0], numbers[1])
    for i in range(2, len(numbers)) :
        s = gcd(s, numbers[i])
    return(s)

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

ans = 0
for i in range(N) :
    B = A[np.arange(len(A))!=i]
    g = gcd_mul(B)
    if g > ans :
        ans = g
print(ans)





### FIXED CODE ###

import fractions # for python 3.4.3

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

gcd_l = [0]
gcd_r = [0]
for i in range(N):
    gcd_l.append(fractions.gcd(gcd_l[i], A[i]))
    gcd_r.append(fractions.gcd(gcd_r[i], A[-(i+1)]))
    #print(gcd_l)
    #print(gcd_r)
gcd_r = gcd_r[::-1]

ans = []
for i in range(N):
    ans.append(fractions.gcd(gcd_l[i], gcd_r[i+1]))

print(max(ans))
c = 0

while True:
    x = int(input()) ; c +=1
    
    if x == 0:
        break
   
    print("Case {}: {}).format(c, x))


### FIXED CODE ###

c = 0

while True:
    x = int(input())
    c +=1
    
    if x == 0:
        break
   
    print("Case {}: {}".format(c, x))
S=str(input())
s=list(S)
x1=0
x2=0
y=0
for i in range(len(s)-1):
  if s[i+1]==s[i]:
    print(x1,x2,y,"yes")
    x2=x2+1
  else:
    if s[i]=='>':
      print(i)
      if x2<x1:
        x2=x2-1
      else:
        if x2>x1:
          x1=x1-1
    y+=x1*(x1+1)/2
    print(x1,x2,y,"no")
    x1=x2
    x2=1
print(x1,x2,y)
if s[i+1]=='>':
      print(i)
      if x2<x1:
        x2=x2-1
      else:
        if x2>x1:
          x1=x1-1
y+=x1*(x1+1)/2
y+=x2*(x2+1)/2
print(x1,x2,y)
print(int(y))

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647) 
S=str(input())
s=list(S)
x1=0
x2=1
y=0
len=len(s)-1
for i in range(len):
  if s[i+1]==s[i]:
    x2=x2+1
  else:
    if i==0:
      x2=0
    if s[i]=='>':
      if x2<x1:
        x2=x2-1
      else:
          x1=x1-1
    y+=x1*(x1+1)/2
    x1=x2
    x2=1
if s[len]=='>':
  if x2<x1:
    x2=x2-1
  else:
    x1=x1-1
y+=x1*(x1+1)/2
y+=x2*(x2+1)/2
print(int(y))
def cal_cnt(num):
  cnt = 0
  for bit in format(num, 'b'):
    if bit == '1':
      cnt += 1

  return cnt


def main():
  n = int(input())
  src = input()
  base = int(src, 2)
  base_cnt = src.count('1')

  basep = base % (base_cnt + 1)
  basem = base % (base_cnt - 1)

  memo = tuple(map(cal_cnt, range(n + 1)))

  dp = [None] * (n + 1)
  dp[0] = 0

  def f(num, cnt):
    if num < n and dp[num] is not None:
      return dp[num]

    nxt = num % cnt
    res = 1 + f(nxt, memo[nxt])
    if num < n:
      dp[num] = res

    return res


  for i in range(n - 1, -1, -1):
    num = None

    if src[n - i - 1] == '0':
      mod = base_cnt + 1
      num = ((basep + pow(2, i, mod)) % mod)
    else:
      mod = base_cnt - 1
      num = ((basem - pow(2, i, mod)) % mod)

    print(1 + f(num, memo[num]))


main()


### FIXED CODE ###


def f(n):
  cnt = 0
  while n:
      cnt += 1
      n = n % bin(n).count('1')

  return cnt

def main():
  n = int(input())
  src = input()
  base = int(src, 2)
  base_cnt = src.count('1')

  basep = base % (base_cnt + 1)
  basem = base % (base_cnt - 1) if base_cnt > 1 else 0

  for i, s in enumerate(src):
    i = n - 1 - i
    num = None

    if s == '0':
      mod = base_cnt + 1
      num = (basep + pow(2, i, mod)) % mod
    elif base_cnt > 1:
      mod = base_cnt - 1
      num = (basem - pow(2, i, mod)) % mod
    else:
      print(0)
      continue

    print(1 + f(num))


main()
import numpy as np
N,W = map(int,input().split())

weight = [0]*N
value = [0]*N
dp = np.zeros((N+1,W+1))

for i in range(N):
    value[i], weight[i] = map(int, input().split())

for i in range(N):
    for j in range(W+1):
        if j >= weight[i]: 
            dp[i+1][j] = max(dp[i][j-weight[i]]+value[i], dp[i][j]) 
        else: 
            dp[i+1][j] = dp[i][j]
print(int(dp[N][W]))


### FIXED CODE ###

N, W =map(int,input().split())
 
INF = 10**10
#dp = [[INF]*100000]*(N*100)#余分に
dp = [[0 for i in range(W+1)] for j in range(N+1)]

for i in range (N):
    dp[i][0] =0
for j in range (W+1):
    dp[0][j] =0
    

for i in range (N):
    v, w = map(int,input().split())
    for j in range (W+1):
        if j-w>=0:
            dp[i+1][j] = max(dp[i][j],dp[i][j-w]+v)
        else:
            dp[i+1][j] = dp[i][j]


print(dp[N][W])
import itertools
N,M=map(int,raw_input().split())
data=[map(float,raw_input().split()) for i in range(N)]
maxInt=0
for comb in itertools.permutations(range(N),M):
    dist=0
    for i in range(M-1):
        for j in range(i+1,M):
            t=comb[i]
            s=comb[j]
            dist+=pow(data[t][0]-data[s][0],2)+pow(data[t][1]-data[s][1],2)+pow\
(data[t][2]-data[s][2],2)
    maxInt=max(maxInt,dist)
print maxInt

### FIXED CODE ###

import itertools
N,M=map(int,raw_input().split())
data=[map(float,raw_input().split()) for i in range(N)]
maxV=0.0
for comb in itertools.combinations(range(N),M):
    dist=0.0
    for i in range(M-1):
        for j in range(i+1,M):
            t=comb[i]
            s=comb[j]
            dist+=pow(data[t][0]-data[s][0],2)+pow(data[t][1]-data[s][1],2)+pow\
(data[t][2]-data[s][2],2)
    maxV=max(maxV,dist)
print maxV