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

def SME():
    A = [[x,i] for i,x in enumerate(Whole)]
    A.sort()
    i = 1
    while i < len(A) - 1:
        if A[i+1][1]-A[i-1][1] < L :
            if A[i+1][0]==A[i-1][0] :
                del A[i]
                continue
        i += 1
    C = set([i for i in range(N)])
    D = set([])
    parameter = 0.997
    count = 0
    ANS = [None] * N
    for j in range(N) :
        a = A[j]
        for i,x in enumerate(ANS[a[1]:a[1]+L]):
            if x : continue
            else :
                ANS[a[1]+i] = a[0]
                D.add(a[1]+i)
                count += 1
        if count > N * parameter : break
    for i in C.difference(D):
        if i < L : ANS[i] = min(Whole[:i+1])
        else : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
if N != 10 ** 5 :
    ANS = SME()
    for i in ANS[L-1:-1]:print(i, end=" ")
    print(ANS[-1])
else :
    if max(Whole) < 10 ** 4 :
        ANS = SME()
        for i in ANS[L-1:-1]:print(i, end=" ")
        print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

s = input()
n = len(s)
mod = 10**9+7
dp = [[0]*13 for i in range(n+5)]#dp[i][j] :=先頭i文字を見たとき、その数字を13で割ったあまりがｊであるような場合の数
dp[0][0] = 1#先頭０文字は”０”　で、１３で割ったあまりは０だから　dp[0][0] = 1
for i in range(n):
    for j in range(13):
        if s[i] == "?":
            for d in range(10):
                dp[i+1][(j*10+d)%13] += dp[i][j]
                dp[i+1][(j*10+d)%13] %= mod
                
        else:
            dp[i+1][(j*10+int(s[i]))%13] += dp[i][j]
            dp[i+1][(j*10+int(s[i]))%13] %= mod
ans = dp[n][5]
print(ans)

### FIXED CODE ###

s = input()
n = len(s)
mod = 10**9+7
dp = [[0]*13 for i in range(n+5)]#dp[i][j] :=先頭i文字を見たとき、その数字を13で割ったあまりがｊであるような場合の数
dp[0][0] = 1#先頭０文字は”０”　で、１３で割ったあまりは０だから　dp[0][0] = 1
for i in range(n):
    for j in range(13):
        if s[i] == "?":
            for d in range(10):
                dp[i+1][(j*10+d)%13] += dp[i][j]
                dp[i+1][(j*10+d)%13] %= mod
                
        else:
            dp[i+1][(j*10+int(s[i]))%13] += dp[i][j]
            dp[i+1][(j*10+int(s[i]))%13] %= mod
ans = dp[n][5]
print(ans)
### BUGGY CODE ###

import collections
n = int(input())
s = [input() for _ in range(n)]
ans = 0
c = []
cnt = []

for i in range(n):
    tmp = collections.Counter(s[i])
    if tmp not in c:
        c.append(tmp)
    else:
        ans += cnt.count(tmp)
    cnt.append(tmp)

print(ans)

### FIXED CODE ###

n = int(input())
S = [input() for _ in range(n)]
ans = 0
c = {}

for s in S:
    s = "".join(sorted(s))
    if s not in c.keys():
        c[s] = 1
    else:
        ans += c[s]
        c[s] += 1


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

h, w, a, b = map(int, input().split())
MOD = 1000000007

dp = [[0 for _ in range(w)] for _ in range(h)]
block = [[True for _ in range(w)] for _ in range(h)]

for y in range(h-1, h-a-1, -1):
    for x in range(b):
        block[y][x] = False

dp[0][0] = 1

for i in range(1, h):
    if block[i][0]:
        dp[i][0] = dp[i-1][0]
for i in range(1, w):
    if block[0][i]:
        dp[0][i] = dp[0][i-1]

for y in range(1, h):
    for x in range(1, w):
        if block[y][x]:
            dp[y][x] = (dp[y-1][x] + dp[y][x-1]) % MOD

#print(block, dp)
print(dp[h-1][w-1])


### FIXED CODE ###

from math import factorial

h, w, a, b = map(int, input().split())
MOD = 10**9+7

fact = [1]

# 累積乗を作る
for i in range(1, h+w-1):
    fact.append(fact[-1] * i % MOD)

# 累積乗の逆元
inv_fact = [pow(fact[-1], MOD-2, MOD)] # x^(-1) = x^(10^9+5) % (10^9+7), フェルマーの小定理
for i in range(h+w-2, 0, -1): # xが最大の場合を求め、後ろ向きに計算していく
    inv_fact.append(inv_fact[-1] * i % MOD)
inv = list(reversed(inv_fact)) # 逆順に取得

#print(fact, inv_fact, inv)
def comb(x, y):
    return (fact[x] * inv[y] * inv[x-y])

ans = 0
for x in range(b, w):
    ans += ((comb((h-a-1 + x), x)) * (comb((a-1 + w-x-1), a-1)) % MOD)
    ans %= MOD

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

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

li = []

for i in a:
    for j in b:
        li.append(i + j)
        
li.sort(reverse = True)
li = li[:min(k,x*y)]

box = []

for i in li:
    for j in c:
        box.append(i + j)

box.sort(reverse = True)

for i in range(k):
    print(box[i])

### FIXED CODE ###

x,y,z,k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort(reverse = True)
b.sort(reverse = True)
c.sort(reverse = True)
li = []
box = []
for i in a:
    for j in b:
        li.append(i + j) 
li.sort(reverse = True)
li = li[:min(k,x*y)]
for i in c:
    for j in li:
        box.append(i + j)
box.sort(reverse = True)
for i in range(k):
    print(box[i])
### BUGGY CODE ###

MOD = 1000000007
tmp = list(map(int, input().split()))
n = tmp[0]
k = tmp[1]

for i in range(1, k+1):
  co = 1
  for j in range(i):
    co *= (n-k+1-j)
#    co %= MOD
  for j in range(i):
    co //= (j+1)
#    co %= MOD
  ci = 1
  for j in range(i-1):
    ci *= (k-1-j)
#    ci %= MOD
  for j in range(i-1):
    ci //= (j+1)
#    ci %= MOD
  print (int(co * ci) % MOD)

### FIXED CODE ###

MOD = 1000000007
tmp = list(map(int, input().split()))
n = tmp[0]
k = tmp[1]

co = 1
ci = 1
for i in range(k):
  co *= (n-k+1-i)
  co //= (i+1)
  if i == 0:
    ci *= 1
  else:
    ci *= (k-i)
    ci //= (i)
#  print (str(ci)+' '+str(co)+' '+str(int(co * ci) % MOD))
  print (int(co * ci) % MOD)
### BUGGY CODE ###

from math import ceil
N,K = list(map(int, input().split()))
A = list(map(int, input().split()))
F = list(map(int, input().split()))

A.sort(reverse=True)
F.sort()
wk = 0
for i in range(N):
  wk += A[i] * F[i]
#print(wk)

def is_ok(arg):
  # 条件を満たすかどうか？問題ごとに定義
  cnt = 0
  for i in range(N):
    a,f = A[i], F[i]   
    if a*f <= arg:
      continue
    else:
      #(a-k) * f <= arg
      # a - arg/f <= k
      cnt += ceil(a-arg/f)
  return cnt <= K

def meguru_bisect(ng, ok):
  '''
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
  while (abs(ok - ng) > 1):
    mid = (ok + ng) // 2
    if is_ok(mid):
      ok = mid
    else:
      ng = mid
  return ok

ng = -1
ok = 10**12 + 10
ans = meguru_bisect(ng,ok)

print(ans)

### FIXED CODE ###

from math import ceil
N,K = list(map(int, input().split()))
A = list(map(int, input().split()))
F = list(map(int, input().split()))

A.sort(reverse=True)
F.sort()
wk = 0
for i in range(N):
  wk += A[i] * F[i]
#print(wk)

def is_ok(arg):
  # 条件を満たすかどうか？問題ごとに定義
  cnt = 0
  for i in range(N):
    a,f = A[i], F[i]   
    if a*f <= arg:
      continue
    else:
      #(a-k) * f <= arg
      # a - arg/f <= k
      cnt += ceil(a-arg/f)
  return cnt <= K

def meguru_bisect(ng, ok):
  '''
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
  while (abs(ok - ng) > 1):
    mid = (ok + ng) // 2
    if is_ok(mid):
      ok = mid
    else:
      ng = mid
  return ok

ng = -1
ok = 10**12 + 10
ans = meguru_bisect(ng,ok)

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

import math

dp = [0 for _ in range(2*10**5+1)]
f = math.factorial
def fact(n):
    if n == 0:
        return 1
    if dp[n] != 0:
        return dp[n]
    else:
        fn = f(n)
        dp[n] = fn
        return fn

def nCr(n,r):
    return fact(n) // fact(r) // fact(n-r)

def distancesum(arr, n): 
      
    # sorting the array. 
    arr.sort() 
      
    # for each point, finding  
    # the distance. 
    res = 0
    sum = 0
    for i in range(n): 
        res += (arr[i] * i - sum) 
        sum += arr[i] 
      
    return res 

flatten = lambda x: [z for y in x for z in (flatten(y) if hasattr(y, '__iter__') and not isinstance(y, str) else (y,))]

div = 10**9 + 7

N, M, K = map(int, input().split())
repeat = nCr(N*M-2, K-2)
f_row = flatten([[i for _ in range(M)] for i in range(N)])
f_col = flatten([[i for i in range(M)] for _ in range(N)])

manhsum = distancesum(f_row, len(f_row)) + distancesum(f_col, len(f_col))
print(((repeat % div) * (manhsum % div))%div)


### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
# 10 ** 7 might cause MLE
fac = [-1] * (10**6+1)
inv = [-1] * (10**6+1)
finv = [-1] * (10**6+1)

fac[0] = fac[1] = 1
inv[1] = 1
finv[0] = finv[1] = 1

def initNCMMod(limit):
    for i in range(2, limit):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i] * (mod // i) % mod
        finv[i] = finv[i-1] * inv[i] % mod

def NCMMod(n, k):
    if n < k:
        return 0
    if (n < 0 or k < 0):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod
initNCMMod(10**6)

def checkf(R, C):
    ans = 0
    for r1 in range(R):
        for c1 in range(C):
            for r2 in range(R):
                for c2 in range(C):
                    ans += abs(r1-r2) + abs(c1-c2)
    return ans


def main():
    R, C, K = LI()
    def f(i):
        return (i * (i+1) // 2) % mod

    ans = 0
    for i in range(C):
        ans += f(C-i-1) * R * R % mod
        ans += f(i) * R * R % mod

    for i in range(R):
        ans += f(R-i-1) * C * C % mod
        ans += f(i) * C * C % mod
    ans *= inv[2]
    ans %= mod
    ans *= NCMMod(R*C-2, K-2)
    ans %= mod

    print(ans)

main()
### BUGGY CODE ###

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

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
ans = A[0]
i = 1
if 0 in A:
    print(0)
else:
    while (i < n) and (ans <= 10**18):
        ans *= A[i]
        i += 1
    if (ans <= 10**18) and i == n:
        print(ans)
    else:
        print(-1)
### BUGGY CODE ###

import fractions  # python3.5以降ではmath


def seekGcd(A, n):
    ans = A[0]
    for i in range(1, n):
        ans = fractions.gcd(ans, A[i])  # python3.5以降ではmath.gcd
    ans_list.append(ans)


n = int(input())
A = list(map(int, input().split()))
ans_list = []

for i in range(n):
    p = A.pop(0)
    seekGcd(A, n-1)
    A.append(p)

print(max(ans_list))


### FIXED CODE ###

import fractions

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

L = [0]
R = [0]
ans_list = []

for i in range(n-1):
    L.append(fractions.gcd(L[i], A[i]))
    R.append(fractions.gcd(R[i], A[n-1-i]))

for j in range(n):
    ans_list.append(fractions.gcd(L[j], R[-j-1]))

print(max(ans_list))
### BUGGY CODE ###

from collections import deque
import math
import sys

N_MAX = 200000 + 5
sys.setrecursionlimit(N_MAX)

H, W, K = map(int, sys.stdin.readline().split())
x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
INF = 10**6 * K

dp = [[INF for _ in range(W+2)] for _ in range(H+2)]

dp[0] = [-1]*(W+2)
dp[H+1] = [-1]*(W+2)
for h in range(1,H+1):
    s = sys.stdin.readline()
    dp[h][0] = -1
    dp[h][W+1] = -1
    for w in range(1,W+1):
        if s[w-1] == "@":
            dp[h][w] = -1

### BFS ###

# ステップ方向
D = [0, 1, 2, 3]  # direction
Y = [1, 0, -1, 0]
X = [0, 1, 0, -1]

def bfs(x1, y1, x2, y2):
    
    q = deque()
    q.append((x1, y1))

    while q:
        # print(q)
        x0, y0 = q.popleft()

        for x, y in zip(X, Y):

            for i in range(1,K+1):

                # print(y0,y,x0,x,d, (y0+y,x0+x,d), end=" : ")
                dp_c = dp[x0][y0]  # 現在のdp値
                n_x, n_y = x0+x*i, y0+y*i

                # print(dp_c, (n_x,n_y), end=" : ")

                if dp[n_x][n_y] == -1:
                    # print("@")
                    break

                if dp[n_x][n_y] == INF:
                    dp[n_x][n_y] = dp_c + 1
                elif dp[n_x][n_y] <= dp_c:
                    break

                if n_x == x2 and n_y == y2:
                    return dp[n_x][n_y]

                q.append((n_x, n_y))

    return -1

# スタート地点を 0 にする
dp[x1][y1] = 0

a = bfs(x1,y1,x2,y2)

print(a)

### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-
 
H, W, K = map(int,input().split())
sth, stw, glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1
 
INF = -1
Gmap = [list(input()) for _ in range(H)]
Seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
 
from collections import deque
 
def bfs(sth, stw, glh, glw):
    next_q = deque([])
    next_q.append((sth,stw,0))
    Seen[sth][stw] = 0
 
    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h, w, c = next_q.popleft()
        for dh, dw in direc:
            for sk in range(1,K+1):
                hs, ws = h + dh*sk, w + dw*sk
                if not (0<=hs<H and 0<=ws<W):
                    break
                if Gmap[hs][ws]=='@':
                    break
                if Seen[hs][ws]==INF:
                    next_q.append((hs,ws,c+1))
                    Seen[hs][ws] = c + 1
                elif Seen[hs][ws]<=c:
                    break
                if hs==glh and ws==glw:
                    return c + 1
    return -1

def main():
    ret = bfs(sth, stw, glh, glw)
    print(ret)

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

if __name__=="__main__":
    n = int(input())
    As = list(map(int,input().split()))
    Non_dup_As = list(set(As))
    As.sort()
    count = 0
    for a in Non_dup_As:
        count+=As.count(a)-1
    if(count % 2 == 0):
        print(len(As) - int(count))
    else:
        print(len(As) - int(count+1))


### FIXED CODE ###

if __name__=="__main__":
    n = int(input())
    As = list(map(int,input().split()))
    Non_dup_As = list(set(As))
    count = len(Non_dup_As)
    if(count % 2 == 0):
        print(count - 1)
    else:
        print(count)
### BUGGY CODE ###

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

if N < K:
    print(abs(H[N-1]-H[0]))
else:
    C = [0] * N
    for i in range(K):
        C[i] = abs(H[i]-H[0])
    for i in range(K, N):
        C[i] = min([C[i-k] + abs(H[i]-H[i-k]) for k in range(K, 0, -1)])
    print(C[N-1])

### FIXED CODE ###

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

if N < K:
    print(abs(H[N-1]-H[0]))
else:
    C = [0] * N
    for i in range(K):
        C[i] = abs(H[i]-H[0])
    for i in range(K, N):
        C[i] = min([C[i-k] + abs(H[i]-H[i-k]) for k in range(K, 0, -1)])
    print(C[N-1])
### BUGGY CODE ###

import copy
n=int(input())
l=[int(input()) for i in range(n)]
for i in list(range(n)):
  r=copy.deepcopy(l)
  del r[i]
  print(max(r))

### FIXED CODE ###

import copy
n=int(input())
l=[int(input()) for i in range(n)]
a=max(l)
ind=l.index(a)
del l[ind]
b=max(l)
for i in list(range(ind)):
  print(a)
print(b)
for s in list(range(n-ind-1)):
  print(a)
### BUGGY CODE ###

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

### FIXED CODE ###

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

def main():
	N, M = [int(x) for x in input().split(" ")]
	route = [[] for i in range(N)]
	for i in range(M):
		A, B = [int(y) for y in input().split(" ")]
		route[A - 1] += [B]
		route[B - 1] += [A]

	checked = [1] + [0] * (N - 1)
	to_check = [{"src" : s, "dst" : 1} for s in route[0]]
	signal = [-1] + [0] * (N - 1)

	while len(to_check) > 0:
		checking = to_check.pop(0)
		src = checking["src"]
		if checked[src - 1] == 0:
			checked[src - 1] = 1
			signal[src - 1] = checking["dst"]
			rooms = route[src - 1]
			for r in rooms:
				if checked[r - 1] == 0:
					to_check.append({"src": r, "dst": src})
	if signal.count(0) > 0:
		print("No")
	else:
		print("Yes")
		print("\n".join([str(q) for q in signal[1:]]))

main()

### FIXED CODE ###

def main():
	N, M = [int(x) for x in input().split(" ")]
	route = [[] for i in range(N)]
	for i in range(M):
		A, B = [int(y) for y in input().split(" ")]
		route[A - 1] += [B]
		route[B - 1] += [A]

	checked = [1] + [0] * (N - 1)
	to_check = [{"src" : s, "dst" : 1} for s in route[0]]
	signal = [-1] + [0] * (N - 1)

	for r in route[0]:
		checked[r - 1] = 1

	while len(to_check) > 0:
		checking = to_check.pop(0)
		src = checking["src"]
		signal[src - 1] = str(checking["dst"])
		rooms = route[src - 1]
		for r in rooms:
			if checked[r - 1] == 0:
				to_check.append({"src": r, "dst": src})
				checked[r - 1] = 1

	if signal.count(0) > 0:
		print("No")
	else:
		print("Yes")
		print("\n".join(signal[1:]))

main()
### BUGGY CODE ###

# coding: utf-8
# Your code here!

def solve(n, m, q, arrays):
    import itertools
    pattern = list(itertools.product(range(1, m+1), repeat=n))

    maxp = 0
    for x in pattern:
        if sorted(x) != list(x):
            continue
        
        get = 0
        for array in arrays:
            if x[array[1]-1] - x[array[0]-1] == array[2]:
                get += array[3]

        maxp = max(maxp, get)

    print(maxp)

n, m, q, *aa = map(int, open(0).read().split())

import numpy as np
arrays = list(np.array_split(aa, q))

solve(n, m, q, arrays)



### FIXED CODE ###

# coding: utf-8
# Your code here!

def solve(n, m, q, arrays):
    from itertools import combinations_with_replacement
    pattern = list(combinations_with_replacement(range(1, m+1), n))

    maxp = 0
    for x in pattern:
        get = 0
        for array in arrays:
            if x[array[1]-1] - x[array[0]-1] == array[2]:
                get += array[3]

        maxp = max(maxp, get)

    print(maxp)

n, m, q, *aa = map(int, open(0).read().split())

arrays = []
loop = 0
array = []
for x in aa:
    array.append(x)
    loop += 1
    if loop % 4 == 0:
        arrays.append(array)
        array = []

solve(n, m, q, arrays)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[a[i]-(i+1) for i in range(n)]
ans=9999999999999999
min_b=min(b)
max_b=max(b)
for i in range(min_b,max_b+1):
    ans=min(ans,sum([abs(b[j]-i) for j in range(n)]))
print(ans)

### FIXED CODE ###

import statistics
n=int(input())
a=list(map(int,input().split()))
b=[a[i]-(i+1) for i in range(n)]
b_median=statistics.median(b)
ans=int(sum([abs(b[i]-b_median) for i in range(n)]))
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

h, w, m = map(int, input().split())
dpcol = [0]*w
dprow = [0]*h
ypos = []
xpos = []
hw = [list(map(lambda x: int(x) - 1, input().split())) for i in range(m)]

for i, j in hw:
    dpcol[j] += 1
    dprow[i] += 1

maxcol = max(dpcol)
maxrow = max(dprow)

for i in range(w): #列の最大値
    if dpcol[i] == maxcol:
        xpos.append(i)

for i in range(h):
    if dprow[i] == maxrow:
        ypos.append(i)

ans = maxcol + maxrow - 1

for i in ypos:
    for j in xpos:
        if [i, j] not in hw:
            ans += 1
            print(ans)
            exit()
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

h, w, m = map(int, input().split())
col = [0]*w
row = [0]*h
ypos = []
xpos = []
bomb = []

for i in range(m):
    H, W = map(lambda x: int(x) - 1, input().split())
    col[W] += 1
    row[H] += 1
    bomb.append((H, W))

maxcol = max(col)
maxrow = max(row)

xpos = [h for h, x in enumerate(col) if x == maxcol]
ypos = [w for w, y in enumerate(row) if y == maxrow]

ans = maxcol + maxrow - 1
bomb = set(bomb)

for i in ypos:
    for j in xpos:
        if (i, j) not in bomb:
            ans += 1
            print(ans)
            exit()
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, W = map(int, input().split())

w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())

def func(N, W):
    dp = [0] * (W+1)
    for i in range(N):
        for j in range(W, w[i]-1, -1):
            a = dp[j-w[i]] + v[i]
            if dp[j] < a:
                dp[j] = a
    return dp[W]

print(func(N, W))

### FIXED CODE ###

N, W = map(int, input().split())

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

print(dp[W])
### BUGGY CODE ###

def sol():
    n=int(input())
    x=input()
    chk=0
    for i,j in enumerate(x[::-1]):
        if j=="1":
            chk+=2**i
    c={}
    d={}
    ans=[]
    for i,j in enumerate(x[::-1]):
        if j=="1":
            t=chk-2**i
        else:
            t=chk+2**i
        s=t
        cnt=0
        while t:
            if t not in c:
                pc=bin(t).count("1")
                c[t]=pc
            else:
                pc=c[t]
            t%=pc
            cnt+=1
            if t in d:
                cnt+=d[t]
                break
        if s not in d:
            d[s]=cnt
        ans.append(cnt)
    for i in ans[::-1]:
        print(i)

if __name__=="__main__":
    sol()


### FIXED CODE ###

n=int(input())
x=input()
chk0=chk1=chk2=0
b=x.count("1")
if b==1 and x=="1":
    print(0)
    exit()
elif b==1:
    for i in range(n):
        if i==n-1: print(2)
        elif x[i]=="0": print(1)
        else: print(0)
    exit()
for i,j in enumerate(x[::-1]):
    if j=="1":
        chk1+=pow(2,i,b+1)
        if b>1: chk2+=pow(2,i,b-1)
        else: chk2=0
l=[]
for i,j in enumerate(x[::-1]):
    if b: a1=pow(2,i,b+1)
    else: a1=1
    if b>1: a2=pow(2,i,b-1)
    else: a2=1
    if j=="0":
        t=chk1+a1
    else:
        if b>1: t=chk2+b-1-a2
        else: t=0
    ans,f=0,1
    while t:
        if f:
            if j=="0": t%=(b+1)
            else: t%=(b-1)
            f=0
        else:
            t%=bin(t).count("1")
        ans+=1
    l.append(ans)
for i in l[::-1]:
    print(i)
### BUGGY CODE ###

from sys import stdin
n, q = map(int, input().split())
cnt = [0]*n
root = [[] for i in range(n)]

for i in range(n-1):
    a, b = map(int, stdin.readline().split())
    root[a-1].append(b-1)

for i in range(q):
    p, x = map(int, stdin.readline().split())

    tmpi = p-1
    tmparr = [tmpi]
    while tmparr:
        tmpi = tmparr.pop()
        cnt[tmpi] += x
        tmparr += root[tmpi]
print(*cnt)

### FIXED CODE ###

from sys import stdin
n, q = map(int, input().split())
cnt = [0]*n
root = [[] for i in range(n)]

for i in range(n-1):
    a, b = map(int, stdin.readline().split())
    root[a-1].append(b-1)

for i in range(q):
    p, x = map(int, stdin.readline().split())
    cnt[p-1] += x

tmparr = [0]
while tmparr:
    tmpi = tmparr.pop()
    for i in root[tmpi]:
        cnt[i] += cnt[tmpi]
    tmparr += root[tmpi]
print(*cnt)