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

# https://atcoder.jp/contests/dp/tasks/dp_b
# B - Frog 2

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


dp = [0] * N

for i in range(1, N):
    MIN = None
    for j in range(1, K + 1):
        if i - j < 0:
            continue
        if MIN == None:
            MIN = dp[i - j] + abs(H[i] - H[i - j])
        else:
            MIN = min(dp[i - j] + abs(H[i] - H[i - j]), MIN)
    dp[i] = MIN

print(dp[-1])


### FIXED CODE ###

N,K=list(map(int,input().strip().split(" ")))
H=list(map(int,input().strip().split(" ")))
dp=[0]+[10**10]*(N-1)
for i in range(1,N):
    temp=0
    for j in range(i-K,i):
        if j>=0:
            dp[i]=min(dp[i],dp[j]+abs(H[i]-H[j]))
print(dp[-1])
### BUGGY CODE ###

N, K = map(int,input().split())
A = list(map(int, input().split()))
dic = {1:0}
now = 1
flag = 0
T = 0
log = [1]
for i in range(K):
  now = A[now-1]
  if now in log:
    flag=1
    T=i+1-dic[now]
    break
  dic[now] = i+1
  log.append(now)
if flag!=1:
  print(now)
else:
  print(log[(K-dic[now])%T+dic[now]])

### FIXED CODE ###

N, K = map(int,input().split())
A = list(map(int, input().split()))
dic = {1:0}
now = 1
flag = 0
T = 0
log = [1]
for i in range(K):
  now = A[now-1]
  #print(i+1,now)
  if now in dic:
    flag=1
    T=i+1-dic[now]
    log = log[dic[now]:]
    break
  dic[now] = i+1
  log.append(now)
if flag!=1:
  print(now)
else:
  print(log[(K-dic[now])%T])
### BUGGY CODE ###

from bisect import *
A,B,Q=map(int,input().split())
S=[int(input()) for i in range(A)]
T=[int(input()) for i in range(B)]
for zzz in range(Q):
    x=int(input())
    value=2*(10**10)
    s1=bisect_left(S,x)
    for s in [s1-1,s1]:
        if 0<= s < A:
            t1=bisect_left(T,S[s])
            for t in [t1-1,t1]:
                if 0<= t < B:
                    value=min(max(x,S[s])-min(x,S[s]) + max(S[s],T[t])-min(S[s],T[t]),value)
    t1=bisect_left(T,x)
    for t in [t1-1,t1]:
        if 0<= t < B:
            s1=bisect_left(S,T[t])
            for s in [s1-1,s1]:
                if 0<= s < A:
                    value=min(max(x,T[t])-min(x,T[t]) + max(S[s],T[t])-min(S[s],T[t]),value)

    print(value)


### FIXED CODE ###

from bisect import *
A,B,Q=map(int,input().split())
S=[int(input()) for i in range(A)]
T=[int(input()) for i in range(B)]
X=[int(input()) for i in range(Q)]
value1=2*(10**10)
for x in X:
    value=value1
    s1=bisect_left(S,x)
    for s in [s1-1,s1]:
        if -1< s < A:
            t1=bisect_left(T,S[s])
            for t in [t1-1,t1]:
                a=0
                if -1< t < B:
                    if x>S[s]:
                        a+=x-S[s]
                    else:
                        a+=S[s]-x
                    if S[s]>T[t]:
                        a+=S[s]-T[t]
                    else:
                        a+=T[t]-S[s]
                    if value>a:
                        value=a
    t1=bisect_left(T,x)
    for t in [t1-1,t1]:
        if -1< t < B:
            s1=bisect_left(S,T[t])
            for s in [s1-1,s1]:
                a=0
                if -1< s < A:
                    if x>T[t]:
                        a+=x-T[t]
                    else:
                        a+=T[t]-x
                    if S[s]>T[t]:
                        a+=S[s]-T[t]
                    else:
                        a+=T[t]-S[s]
                    if value>a:
                        value=a

    print(value)
### BUGGY CODE ###

import queue
N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
Q=int(input())
v=[0 for i in range(Q)]
d=[0 for i in range(Q)]
c=[0 for i in range(Q)]
for i in range(Q):
    v[-i-1],d[-i-1],c[-i-1]=map(int,input().split());v[-i-1]-=1
q=queue.Queue()
color=[0 for i in range(N)]
dp=[-1 for i in range(N)]
for t in range(Q):
    if dp[v[t]]>=d[t]:
        continue
    dp[v[t]]=d[t]
    q.put((v[t],d[t]))
    while(not(q.empty())):
        vv,dd=q.get()
        if color[vv]==0:
            color[vv]=c[t]
        dd-=1
        for y in G[vv]:
            if dp[y]>=dd:
                continue
            dp[y]=dd
            q.put((y,dd))
for line in color:
    print(line)


### FIXED CODE ###

from collections import deque
N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
Q=int(input())
v=[0 for i in range(Q)]
d=[0 for i in range(Q)]
c=[0 for i in range(Q)]
for i in range(Q):
    v[-i-1],d[-i-1],c[-i-1]=map(int,input().split());v[-i-1]-=1
q=deque()
color=[0 for i in range(N)]
dp=[-1 for i in range(N)]
for t in range(Q):
    if dp[v[t]]>=d[t]:
        continue
    dp[v[t]]=d[t]
    q.append((v[t],d[t]))
    while(q):
        vv,dd=q.popleft()
        if color[vv]==0:
            color[vv]=c[t]
        dd-=1
        for y in G[vv]:
            if dp[y]>=dd:
                continue
            dp[y]=dd
            q.append((y,dd))
for line in color:
    print(line)
### BUGGY CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    INF = float('inf')
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,M,L = LI()
    road = [[] for _ in range(N)]
    for _ in range(M):
        a,b,c = LI()
        if c <= L:
            road[a-1].append((b-1,c))
            road[b-1].append((a-1,c))

    town = [[[-1,0] for _ in range(N)] for _ in range(N)]

    for s in range(N):

        q = [(0,-L,s)]
        heapq.heapify(q)
        while q:
            n,w,u = heapq.heappop(q)
            for v,c in road[u]:
                nn = n
                nw = w + c
                if nw > 0:
                    nw = c - L
                    nn += 1

                if town[s][v][0] < 0 or town[s][v][0] > nn or \
                        town[s][v][0] == nn and town[s][v][1] > nw:
                    town[s][v][0] = nn
                    town[s][v][1] = nw
                    heapq.heappush(q,(nn,nw,v))

    Q = NI()
    for _ in range(Q):
        s,t = LI()
        print(town[s-1][t-1][0])


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq


def wf(d,n):
    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

def main():
    INF = 10**18
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,M,L = LI()
    road = [[INF] * N for _ in range(N)]
    for _ in range(M):
        a,b,c = LI()
        if c <= L:
            road[a-1][b-1] = c
            road[b-1][a-1] = c

    road = wf(road,N)


    gas = [[INF] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if road[i][j] <= L:
                gas[i][j] = 1

    gas = wf(gas,N)

    Q = NI()
    for _ in range(Q):
        s,t = LI()
        if gas[s-1][t-1] == INF:
            print(-1)
        else:
            print(gas[s-1][t-1]-1)


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

import sys
input=sys.stdin.readline

n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[0]*40
p=[1]*40
for i in range(39):
    p[i+1]=p[i]*2
for i in a:
    for j in range(40):
        if i&p[j]>0:
            b[j]+=1
ans=0
for i in range(k+1):
    kai=0
    for j in range(40):
        if i&p[j]==0:
            kai+=b[j]*p[j]
        else:
            kai+=(n-b[j])*p[j]
    ans=max(ans,kai)
print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
l=list(map(int,input().split()))
a=[0]*42
for i in range(n):
    p=l[i]
    j=0
    while p>0:
        a[j]+=p%2
        p=p//2
        j+=1
ans=0
for i in range(41,-1,-1):
    if a[i]<n-a[i]:
        if k>=2**i:
            k-=2**i
            ans+=(2**i)*(n-a[i])
        else:
            ans+=(2**i)*a[i]
    else:
        ans+=(2**i)*a[i]
print(ans)
### BUGGY CODE ###

import math

def Show(n):
	s = str(n)
	m = len(s)
	for i in range(6 - m):
		print("0",end = "")
	print("{0}".format(n),end = "")

class city:
	year = 0
	p = 0
	x = 0
	number = 0
	def __init__(self,y,pi,n):
		self.year = y
		self.p = pi
		self.number = n

s = input().split()
n = int(s[0])
m = int(s[1])
cities = []
for i in range(m):
	s = input().split()
	p = int(s[0])
	y = int(s[1])
	cities.append(city(y,p,i))
x = [[] for i in range(n)]
for i in range(m):
	x[cities[i].p - 1].append(cities[i])
for i in range(n):
	x[i].sort(key = lambda x : x.year)
ans = []
for i in range(m):
	ans.append([0,0])
for i in range(n):
	for j in range(len(x[i])):
		x[i][j].x = j + 1
for i in range(n):
	for j in range(len(x[i])):
		ans[x[i][j].number][0] = x[i][j].p
		ans[x[i][j].number][1] = x[i][j].x
for i in range(m):
	Show(ans[i][0])
	Show(ans[i][1])
	print()

### FIXED CODE ###

import math

def Show(n):
	s = str(n)
	m = len(s)
	for i in range(6 - m):
		print("0",end = "")
	print("{0}".format(n),end = "")

class city:
	year = 0
	p = 0
	number = 0
	def __init__(self,y,pi,n):
		self.year = y
		self.p = pi
		self.number = n

s = input().split()
n = int(s[0])
m = int(s[1])
cities = []
for i in range(m):
	s = input().split()
	p = int(s[0])
	y = int(s[1])
	cities.append(city(y,p,i))
x = [[] for i in range(n)]
for i in range(m):
	x[cities[i].p - 1].append(cities[i])
for i in range(n):
	x[i].sort(key = lambda x : x.year)
ans = []
for i in range(m):
	ans.append([0,0])
for i in range(n):
	for j in range(len(x[i])):
		ans[x[i][j].number][0] = x[i][j].p
		ans[x[i][j].number][1] = j + 1
for i in range(m):
	Show(ans[i][0])
	Show(ans[i][1])
	print()
### BUGGY CODE ###

def main():
  import sys
  from heapq import heappush, heappop, heapify
  n = int(input())
  a = [int(e) for e in input().split()]
  b = [int(e) for e in input().split()]
  result = 0
  finished = 0
  hq = [(-b[i], i) for i in range(n)]
  heapify(hq)
  while True:
    _, i = heappop(hq)
    if a[i] == b[i]:
      finished += 1
      continue
    if i == 0:
      b[i] -= b[n - 1] + b[1]
    elif i == n - 1:
      b[i] -= b[n - 2] + b[0]
    else:
      b[i] -= b[i - 1] + b[i + 1]
    if a[i] > b[i]:
      print(-1)
      sys.exit()
    result += 1
    if a[i] == b[i]:
      finished += 1
      if finished == n:
        print(result)
        sys.exit()
    else:
      heappush(hq, (-b[i], i))
main()

### FIXED CODE ###

def main():
  import sys
  _int = int
  n = _int(input())
  a = [_int(e) for e in input().split()]
  b = [_int(e) for e in input().split()]
  result = 0
  q = [i for i in range(n) if b[i] != a[i]]
  while len(q) != 0:
    nq = []
    c = 0
    for i in q:
      if i == 0 or i == n - 1:
        j = b[(n + i - 1) % n] + b[(n + i + 1) % n]
      else:
        j = b[i - 1] + b[i + 1]
      if j > b[i] - a[i]:
        nq.append(i)
        continue
      c += 1
      k = (b[i] - a[i]) // j
      result += k
      b[i] -= j * k
      if a[i] != b[i]:
        nq.append(i)
    if c == 0 and len(nq) != 0:
      print(-1)
      sys.exit()
    q = nq
  print(result)
main()
### BUGGY CODE ###

# Using BFS
import queue
from collections import defaultdict


def push(v, d, dist, q, INF=1e10):
    if dist[v] != INF:
        return
    dist[v] = d
    q.put(v)


def main():
    n, x, y = map(int, input().split())
    # modify the values of x, y so that they start from zero
    x, y = x - 1, y - 1
    INF = 1e10
    ans = defaultdict(int)
    for i in range(n):
        # dist[idx]: distance between i and idx.
        dist = [INF] * n
        q = queue.Queue()
        push(i, 0, dist, q)
        while not q.empty():
            v = q.get()
            d = dist[v]
            if v - 1 >= 0:
                push(v-1, d+1, dist, q)
            if v + 1 < n:
                push(v+1, d+1, dist, q)
            if v == x:
                push(y, d+1, dist, q)
            if v == y:
                push(x, d+1, dist, q)

            ans[dist[v]] += 1

    for i in range(n):
        if i != 0:
            print(ans[i] // 2)


if __name__ == "__main__":
    main()


### FIXED CODE ###

# Using BFS
from collections import defaultdict, deque
import sys


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


def push(v, d, dist, q, INF=1e10):
    if dist[v] != INF:
        return
    dist[v] = d
    q.append(v)


def main():
    n, x, y = map(int, input().split())
    # modify the values of x, y so that they start from zero
    x, y = x - 1, y - 1
    INF = 1e10
    ans = defaultdict(int)
    for i in range(n):
        # dist[idx]: distance between i and idx.
        dist = [INF] * n
        q = deque()
        push(i, 0, dist, q)
        while len(q) != 0:
            v = q.popleft()
            d = dist[v]
            if v - 1 >= 0:
                push(v-1, d+1, dist, q)
            if v + 1 < n:
                push(v+1, d+1, dist, q)
            if v == x:
                push(y, d+1, dist, q)
            if v == y:
                push(x, d+1, dist, q)

            ans[dist[v]] += 1

    for i in range(n):
        if i != 0:
            print(ans[i] // 2)


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

n = int(input())
s = []
for i in range(n):
    a = int(input())
    if a in s:
        del s[s.index(a)]
    else:
        s.append(a)

print(len(s))


### FIXED CODE ###

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

a.sort()
a.append(0)
erased = 0
ans = 0
for i in range(1,n+1):
    if a[i-1] == a[i]:
        erased = (erased+1)%2
    else:
        if erased == 0:
            ans += 1
        erased = 0
print(ans)
### BUGGY CODE ###

N = int(input())
cards = list(map(int, input().split()))
x, y = 0, 0
ans = float("inf")
for i in range(1, N):
    x = sum(cards[:i])
    y = sum(cards[i:])
    if(abs(x-y) < ans):
        ans = abs(x-y)
print(ans)


### FIXED CODE ###

N = int(input())
cards = list(map(int, input().split()))
ans = float("inf")
y = sum(cards)
x = 0
L = []

for card in cards:
    x += card
    y -= card
    L.append(abs(x-y))
    
del L[N-1]

print(min(L))
### BUGGY CODE ###

N = int(input())
S = input()

ans = 0
flag = False

for i in range(N):
    for j in range(i+1, N):
        if S[i:j] in S[j:]:
            flag = True
            if len(S[i:j]) > ans:
                ans = len(S[i:j])

print(ans)

### FIXED CODE ###

N = int(input())
S = input()

l1 = l2 = length = 0

while l2 + length < N:
    if S[l1:l2] in S[l2:]:
        length = l2 - l1
        l2 += 1
    else:
        l1 += 1
        l2 = l1 + length + 1
        
print(length)
### BUGGY CODE ###

n,x,y = map(int,input().split())
dic = [[0 for i in range(n)]for j in range(n)]
ans = [0 for i in range(n)]
for i in range(n):
    for j in range(i,n):
        dic[i][j] = min(abs(i-j),(abs(i-(x-1))+1+abs(y-1-j)),(abs(i-(x-1))+1+abs(y-1-j)))
        ans[dic[i][j]] += 1
for i in range(1,n):
    print(ans[i])


### FIXED CODE ###

n,x,y = map(int,input().split())
ans = [0]*n
for i in range(n):
    for j in range(i,n):
        ans[min(j-i,(abs(i-(x-1))+1+abs(y-1-j)),(abs(i-(x-1))+1+abs(y-1-j)))] += 1
for i in range(1,n):
    print(ans[i])
### BUGGY CODE ###

from sys import setrecursionlimit

setrecursionlimit(10 ** 6)

s = input() + "T"
x, y = map(int, input().split())

stepx = []
stepy = []

headx = True
step = 0
for c in s:
    if c == "F":
        step += 1
    else:
        if headx:
            stepx.append(step)
        else:
            stepy.append(step)
        headx = not headx
        step = 0

x -= stepx[0]
stepx = stepx[1:]


class Reachable:
    def __init__(self, steps):
        self.steps = steps

        self.maxs = sum(steps)
        self.r = [{} for _ in range(len(steps))]

    def __call__(self, i, s):
        if i == -1:
            return s == 0
        elif not -self.maxs <= s <= self.maxs:
            return False
        elif self.r[i].get(s, None) is not None:
            return self.r[i][s]
        else:
            step = self.steps[i]
            r = self(i - 1, s - step) or self(i - 1, s + step)
            self.r[i][s] = r
            return r


answer = Reachable(stepx)(len(stepx) - 1, x) and Reachable(stepy)(len(stepy) - 1, y)

if answer:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

from sys import setrecursionlimit

setrecursionlimit(10 ** 6)

s = input() + "T"
x, y = map(int, input().split())

stepx = []
stepy = []

headx = True
step = 0
for c in s:
    if c == "F":
        step += 1
    else:
        if headx:
            stepx.append(step)
        else:
            stepy.append(step)
        headx = not headx
        step = 0

x -= stepx[0]
stepx = stepx[1:]


class Reachable:
    def __init__(self, steps):
        self.steps = steps

        self.maxs = sum(steps)
        self.r = [{} for _ in range(len(steps))]

    def __call__(self, i, s):
        if i == -1:
            return s == 0
        elif not -self.maxs <= s <= self.maxs:
            return False
        elif self.r[i].get(s, None) is not None:
            return self.r[i][s]
        else:
            step = self.steps[i]
            r = self(i - 1, s - step) or self(i - 1, s + step)
            self.r[i][s] = r
            return r


answer = Reachable(stepx)(len(stepx) - 1, x) and Reachable(stepy)(len(stepy) - 1, y)

if answer:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

city,dnum,qnum=map(int,input().split())

data,querry=[],[]

for i in range(dnum):
	data.append(list(map(int,input().split())))

for i in range(qnum):
	querry.append(list(map(int,input().split())))
	
def solve(start,end):
	res=0
	for j in range(dnum):
		if start<=data[j][0] and data[j][1]<=end:
			res+=1
	return res
	
for i in range(qnum):
	print(solve(querry[i][0],querry[i][1]))

### FIXED CODE ###

def main():
    n, m, Q = map(int, input().split())
    Train= [[0 for _ in range(n)] for _ in range(n)]
    
    for i in range(m):
        l, r = map(int, input().split())
        l, r = l - 1, r - 1
        Train[l][r] += 1
    
    P_Train = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        tmp = 0
        for j in range(n):
            tmp += Train[i][j]
            P_Train[i][j] = tmp

    for i in range(Q):
        p, q = map(int, input().split())
        p, q = p - 1, q - 1
        ans = solve(P_Train, n, p, q)
        print(ans)

def solve(P_Train, n, p, q):
    ans = 0
    for i in range(p, q + 1):
        if  p - 1 < 0:
            ans += P_Train[i][q]
        else:
            ans += P_Train[i][q] - P_Train[i][p - 1]
    return ans


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

base = input().split()
n = int(base[0])
k = int(base[1])
ans = []
def fnk(a):
  if a>=0:
    return a
  else:
    return a*(-1)
if n%k==0:
  print(0)
else:
  while fnk(n-k) not in ans:
    ans.append(fnk(n-k))
    n = fnk(n-k)
  print(min(ans))


### FIXED CODE ###

base = input().split()
n = int(base[0])
k = int(base[1])
s = n%k
t = k-s
if s>t:
  print(t)
else:
  print(s)
### BUGGY CODE ###

import numpy as np

N, M = map(int, input().split())
a_l = []
for _ in range(M):
    a_in = int(input())
    a_l.append(a_in)
a = np.array(a_l)

step0 = 1

if 1 in a:
    step1 = 0
else:
    step1 = 1

ans = [step0, step1]
for i in range(2, N+1):
    if i in a:
        now = 0
    else:
        now = ans[-1] + ans[-2]
    ans.append(now)
print(ans[-1] % 1000000007)

### FIXED CODE ###

import numpy as np

N, M = map(int, input().split())
A = [1]*(N+1)
for _ in range(M):
    A[int(input())] = 0

step0 = 1
step1 = A[1]

ans = [step0, step1]
for i in range(2, N+1):
    now = (ans[-1] + ans[-2]) * A[i]
    ans.append(now)
print(ans[-1] % 1000000007)
### BUGGY CODE ###

#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))

from random import randrange
from itertools import accumulate
from bisect import bisect_left
import time
#%%code

def calc(LIST):
    ans=0
    last=[0]*26
    for i in range(len(LIST)):
        a=i+1 #day a0
        x=LIST[i]-1
        #increase
        ans+=S[i][x]
        #decrease
        last[x]=a#update
        temp=0
        for j in range(26):
            temp+=C[j]*(a-last[j])
        #print(ans,temp,"deb")
        ans-=temp
        #print(ans)

    return ans

def answerer(c):
    """
    #方針その2
    最初にですが乱択をします。ただし、CとDの積に応じてあたりやすさをでかくします
    """
    acc=list(accumulate(c))
    ret=[]
    for d in range(D):
        acc=list(accumulate(c))
        miru=[]
        for i in range(len(c)):
            miru.append(acc[i]*S[d][i])
        temp=randrange(miru[-1])
        s=bisect_left(miru,temp)
        if s<1:s+=1
        elif s>=len(miru):s=len(miru)
        ret.append(s+1)
        
        #print(s+1)
    return ret

def resolve():
    global D,C,S
    #input of prob.A
    D,=pin()
    C=[*pin()]#0-indexed
    S=[[*pin()]for i in range(D)]
    answerer(C)

    
    ##print(acc)
    start=time.time()
    king=[1]*365
    max_score=calc(king)
    #print(max_score)
    
    while(time.time()-start<1.9):
        temp=answerer(C)
        challenge=calc(temp)
        if challenge>max_score:
            max_score=challenge
            king=temp[:]
        ##print(king,max_score)
    
    #assert len(king)==D
    print(*king,sep="\n")
    #print(max_score)
#%%submit!
resolve()

### FIXED CODE ###

print(*[(i%26)+1 for i in range(365)],sep="\n")
### BUGGY CODE ###

#AIsing2020 d

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

def main():
    N = int(input())
    X = input()
    X10 = int(X,2)
    X10_num1 = X.count('1')
    X10_pulse = X10%(X10_num1+1)
    X10_ninus = X10%(X10_num1-1) if X10_num1 >1 else 0


    for i in range(N,0,-1):
        j = N-i
        if (X[j] == '1') and X10_num1 >1:
            amari = (X10_ninus - (2**(i-1))%(X10_num1-1))%(X10_num1-1)
        elif (X[j] == '1') and X10_num1 ==1:
            print(0)
            continue
        else:
            amari = (X10_pulse + (2**(i-1))%(X10_num1+1))%(X10_num1+1)

        print(1+f(amari))


main()


### FIXED CODE ###

#AIsing2020 d

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

def main():
    N = int(input())
    X = input()
    X10 = int(X,2)
    X10_num1 = X.count('1')
    X10_pulse = X10%(X10_num1+1)
    X10_ninus = X10%(X10_num1-1) if X10_num1 >1 else 0


    for i in range(N,0,-1):
        j = N-i
        if (X[j] == '1') and X10_num1 >1:
            mod = X10_num1-1
            amari = (X10_ninus - pow(2,i-1,mod))%(mod) 
        elif (X[j] == '1') and X10_num1 ==1:
            print(0)
            continue
        else:
            mod = X10_num1+1
            amari = (X10_pulse + pow(2,i-1,mod))%(mod)

        print(1+f(amari))


main()