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

import heapq as hq
def main():
  N, Q = list(map(int, input().split()))
  STX = [list(map(int, input().split())) for _ in range(N)]
  D = [int(input()) for _ in range(Q)]

  L = []
  for s, t, x in STX:
    L.append([x, s - x, t - x])

  L.sort(key = lambda x: x[1])
  q = []
  push = hq.heappush
  pop = hq.heappop
  cnt = 0
  for i in range(Q):
    while cnt < len(L) and D[i] >= L[cnt][1]:
      push(q, L[cnt])
      cnt += 1
    while True:
      if q == []:
        print(-1)
        break
      t = pop(q)
      if t[2] > D[i]:
        print(t[0])
        push(q, t)
        break    

main()


### FIXED CODE ###

import heapq
def main():
  N, Q = list(map(int, input().split()))
  STX = tuple(list(map(int, input().split())) for _ in range(N))
  D = tuple([int(input()) for _ in range(Q)])

  L = []
  for s, t, x in STX:
    L.append((x, s - x, t - x))

  L.sort(key = lambda x: x[1])
  q = []
  cnt = 0
  push = heapq.heappush
  pop = heapq.heappop
  t = []
  for i in range(Q):
    while cnt < len(L) and D[i] >= L[cnt][1]:
      if t != []:
        push(q, t)
        t = []
      push(q, L[cnt])
      cnt += 1
    if t != [] and t[2] > D[i]:
      print(t[0])
    else:
      while q != []:
        t = pop(q)
        if t[2] > D[i]:
          print(t[0])
          break
      else:
        t = []
        print(-1)

main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
read = sys.stdin.read

import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

n, m, s, t = map(int, input().split())
U, V, A, B = np.array(read().split(), dtype=np.int64).reshape(m, 4).T
csr_yen = csr_matrix((A, (U, V)), shape=(n+1, n+1))
csr_snuuk = csr_matrix((B, (U, V)), shape=(n+1, n+1))
G_yen = dijkstra(csr_yen, directed=False, indices=s)
G_snuuk = dijkstra(csr_snuuk, directed=False, indices=t)
L = []
U = 10**15
now = U
for i in range(n, 0, -1):
  now = min(now, int(G_yen[i]+G_snuuk[i]))
  L.append(U-now)
print(*L[::-1], sep="\n")

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
import heapq

def dijkstra(n, start, edge):
    dist = [float("inf")]*n
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, v = heapq.heappop(que)
        if dist[v] < d:
            continue
        for nv, nd in edge[v]:
            if dist[nv] > d + nd:
                dist[nv] = d + nd
                heapq.heappush(que, (dist[nv], nv))
    return dist
    
n, m, s, t = map(int, input().split())
G_yen = [[] for _ in range(n+1)]
G_snuuk = [[] for _ in range(n+1)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    G_yen[u].append((v, a))
    G_yen[v].append((u, a))
    G_snuuk[u].append((v, b))
    G_snuuk[v].append((u, b))
dijk_yen = dijkstra(n+1, s, G_yen)
dijk_snuuk = dijkstra(n+1, t, G_snuuk)
L = []
U = 10**15
now = U
for i in range(n, 0, -1):
    now = min(now, dijk_yen[i]+dijk_snuuk[i])
    L.append(U-now)
print(*L[::-1], sep="\n")
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    
    
    def prime_factorize(n):
        r = set()
        while n % 2 == 0:
            r.add(2)
            n //= 2
        f = 3
        while f * f <= n:
            if n % f == 0:
                r.add(f)
                n //= f
            else:
                f += 2
        if n != 1:
            r.add(n)
        return set(r)
    
    
    j = 0
    a1 = set()
    a2 = prime_factorize(A[0])
    for a in A[1:]:
        tmp = prime_factorize(a)
        if a1 & tmp:
            j = 1
        a1 |= tmp
        a2 &= tmp
    if a2:
        print('not coprime')
    elif j:
        print('setwise coprime')
    else:
        print('pairwise coprime')


main()

### FIXED CODE ###

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


def prime_factorize(n):
    r = set()
    while n % 2 == 0:
        r.add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            r.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        r.add(n)
    return r


j = 0
a1 = set()
a2 = prime_factorize(A[0])
for a in A[1:]:
    tmp = prime_factorize(a)
    if a1 & tmp:
        j = 1
    a1 |= tmp
    a2 &= tmp
if a2:
    print('not coprime')
elif j:
    print('setwise coprime')
else:
    print('pairwise coprime')
### BUGGY CODE ###

N,Q = map(int, input().split())
STX = []
for i in range(N):
  *stx, = list(map(int, input().split()))
  STX.append(stx)
D = []
for i in range(Q):
  D.append(int(input()))

STX = sorted(STX, key=lambda x: x[2])

DI = [i for i in range(Q)]
ANS = [-1]*Q
for (s,t,x) in STX:
  s2 = (s - x)
  t2 = (t - x)
  for di in DI[:]:
    if ((s2 <= D[di]) and (D[di] < t2)):
      ANS[di] = x
      DI.remove(di)

print(*ANS, sep='\n')


### FIXED CODE ###

import sys
from bisect import bisect_left
input = sys.stdin.readline

N,Q = map(int, input().split())
STX = [list(map(int, input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]

STX = sorted(STX, key=lambda x: x[2])

MASK = [-1]*Q
ANS = [-1]*Q

for (s,t,x) in STX:
  s2 = (s - x)
  t2 = (t - x)

  start = bisect_left(D, s2)
  end = bisect_left(D, t2, lo=start)

  #print(start, end, DI)
  while (start < end):
    if (-1 == MASK[start]):
      ANS[start] = x
      MASK[start] = end
      start += 1
    else:
      start = MASK[start]


print(*ANS, sep='\n')
### BUGGY CODE ###

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

### FIXED CODE ###

n = int(input())
A = [*map(int,input().split())]
A.sort()
ans = 1
for a in A:
    ans *= a
    if ans > 10**18:
        ans = -1
        break
print(ans)
### BUGGY CODE ###

N = int(input())
cnt = 0
while N > 0:
    cnt += N % 10
    N //= 10
ans = 'Yes' if cnt % 9 == 0 else 'No'
print(ans)


### FIXED CODE ###

N = input()
cnt = 0
for s in N:
    cnt += int(s)
    cnt %= 9
ans = 'Yes' if cnt % 9 == 0 else 'No'
print(ans)
### BUGGY CODE ###

N,K = list(map(int,input().split(" ")))
hs = list(map(int,input().split(" ")))
dp = [9999999999999] * N

dp[0] = 0
for i in range(1,N):

    stepLim = min(K,i)
    temp = 9999999999999999999
    for j in range(1,stepLim + 1):
        c = dp[i-j]+abs(hs[i]-hs[i-j])
        if temp >c:
                temp = c
    dp[i] = temp
print(dp[-1])

### FIXED CODE ###

N,K = list(map(int,input().split(" ")))
hs = list(map(int,input().split(" ")))
dp = [9999999999999] * N

dp[0] = 0
for i in range(1,N):
#ind → i-1 ~ i-stepLim -1   [i-stepLim -1:i]
    stepLim = min(K,i)
    temp = 9999999999999999999
    dp[i] = min([d+abs(hs[i]-h) for d,h in zip(dp[i-stepLim:i],hs[i-stepLim:i])])
print(dp[-1])
### BUGGY CODE ###

n = int(input())
arr = list(map(int,input().split()))
ans = 1
for i in arr:
    ans *= i
print(ans if ans <= 10**18 else -1)

### FIXED CODE ###

n = int(input())
arr = list(map(int,input().split()))
ans = 1
if 0 in arr:
    print(0)
    exit()
for i in arr:
    ans *= i
    if ans > 10**18:
        print(-1)
        exit()
print(ans if ans <= 10**18 else -1)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
from scipy.sparse.csgraph import dijkstra

def main():
    N = int(input())
    INF = float('inf')
    dist = [[INF for _ in range(N)] for _ in range(N)]
    for _ in range(N-1):
        x,y = map(int,input().split())
        dist[x-1][y-1] = 1
        dist[y-1][x-1] = 1
        
    fen = dijkstra(dist,indices = 0)
    snu = dijkstra(dist,indices = N-1)
    fg = sg = 0
    for i in range(N):
        if fen[i] <= snu[i]:
            fg += 1
        else:
            sg += 1
            
    print("Fennec" if fg > sg else "Snuke")
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from collections import deque

def main():
    N = int(input())
    dist = [[] for _ in range(N)]
    for _ in range(N-1):
        a,b = map(int,input().split())
        dist[a-1].append(b-1)
        dist[b-1].append(a-1)

    def root(x):
        go = [False for _ in range(N)]
        d = [0 for _ in range(N)]
        go[x] = True
        q = deque([x])
        while q:
            now = q.pop()
            for fol in dist[now]:
                if go[fol]:
                    continue
                else:
                    d[fol] = d[now] + 1
                    go[fol] = True
                    q.append(fol)
        return d
    
    fen = root(0)
    snu = root(N-1)
    fg = sg = 0
    for i in range(N):
        if fen[i] <= snu[i]:
            fg += 1
        else:
            sg += 1
            
    print("Fennec" if fg > sg else "Snuke")

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

S = list(input())
Q = int(input())
lst = []

for i in range(Q):
    tmp = list(input().split())
    lst.append(tmp)

for i in range(Q):
    if int(lst[i][0]) == 1:
        S.reverse()
    if int(lst[i][0]) == 2:
        if int(lst[i][1]) == 1:
            S.insert(0,lst[i][2])
        else:
            S.append(lst[i][2])

ans = "".join(S)
print(ans)

### FIXED CODE ###

from collections import deque

S = deque(input())
Q = int(input())
lst = deque()

for i in range(Q):
    tmp = list(input().split())
    lst.append(tmp)

reverse = 0
c = 1
for i in range(Q):

    if int(lst[i][0]) == 1:
        reverse += 1
        c += 1
    
    if int(lst[i][0]) == 2:
        if c%2 == 1:
            if int(lst[i][1]) == 1:
                S.appendleft(lst[i][2])
            else:
                S.append(lst[i][2])
        else:
            if int(lst[i][1]) == 2:
                S.appendleft(lst[i][2])
            else:
                S.append(lst[i][2])

if reverse%2 == 1:
    S.reverse()

ans = "".join(S)
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
r, g, b, n = map(int, input().split())

nr_max = n // r
ng_max = n // g
nb_max = n // b

count = 0
for i in range(0, nr_max + 1):
    tmp1 = r * i
    if tmp1 == n:
        count += 1
    if tmp1 >= n:
        break
    for j in range(0, ng_max + 1):
        tmp2 = g * j + tmp1
        if tmp2 == n:
            count += 1
        if tmp2 >= n:
            break
        for k in range(0, nb_max + 1):
            tmp2 += b
            if tmp2 == n:
                count += 1
            if tmp2 >= n:
                break
print(count)

### FIXED CODE ###

# -*- coding: utf-8 -*-
r, g, b, n = map(int, input().split())

nr_max = n // r
ng_max = n // g

count = 0
for i in range(nr_max + 1):
    tmp1 = r * i
    if tmp1 == n:
        count += 1
        break
    res = n - tmp1
    for j in range(res // g + 1):
        tmp2 = g * j + tmp1
        if tmp2 == n:
            count += 1
        if tmp2 >= n:
            break
        if (n - tmp2) % b == 0:
            count += 1

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

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


ans=1
for i in a:
    ans*=i


if ans > 10**18:
    ans = -1


print(ans)

### FIXED CODE ###

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


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

ans=1
for i in a:
    ans*=i

    if ans > 10**18:
        ans = -1
        break


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

def main():
    N, M = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    bcs = [[int(i) for i in input().split()] for _ in range(M)]
    bcs.sort(reverse=True,key=lambda c:c[1])

    ans = 0
    sel = []
    for a in A:
        if a < bcs[0][1]:
            sel.append(a)
        else:
            ans += a
    sel.sort()
    bcs = [[c] * b for b,c in bcs]
    stock = len(sel)
    from itertools import chain,zip_longest
    cnt = 0
    for a,card in zip_longest(sel,chain.from_iterable(bcs),fillvalue=0):
        if cnt == stock:
            break
        if a < card:
            ans += card
        else:
            ans += a
        cnt += 1
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N, M = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    bcs = [[int(i) for i in input().split()] for _ in range(M)]
    bcs.sort(reverse=True,key=lambda c:c[1])

    ans = 0
    sel = []
    for a in A:
        if a < bcs[0][1]:
            sel.append(a)
        else:
            ans += a
    sel.sort()
    stock = len(sel)
    cards = []
    for b,c in bcs:
        cards.extend([c] * b)
        if len(cards) >= stock:
            break
    from itertools import zip_longest
    cnt = 0
    for a,card in zip_longest(sel,cards,fillvalue=0):
        if cnt == stock:
            break
        if a < card:
            ans += card
        else:
            ans += a
        cnt += 1
    print(ans)

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

n = int(input())
a = list(map(int, input().split()))
ans = 1
ng = 0
for i in a:
    ans *= i
    if ans > 10 ** 18:
        ng = 1
    if i == 0:
        print(0)
        exit()
if ng:
    print(-1)
    exit()
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
ng = 0
if 0 in a:
    print(0)
    exit()
for i in a:
    ans *= i
    if ans > 10 ** 18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

n = int(input())
l = list( map(int, input().split())) 
ans = 0

lsorted = sorted(l, reverse=True)

for longest in range(len(l)-2):

    for second in range(longest+1, len(l)):
        if lsorted[longest] - 2*lsorted[second] >= 0:
            break 
        for k in range(second+1, len(l)):
            if lsorted[longest] - lsorted[second] - lsorted[k] >= 0:                
                break
            else:
                ans += 1

print(ans)

### FIXED CODE ###

from bisect import bisect_left

n = int(input())
l = list( map(int, input().split())) 
ans = 0
l.sort()

for i in range(n-2):
    shortest = l[i]
    for j in range(i+1, n-1):
        second = l[j]
        # このスライスしたやつと地味にTLEになる...
        # k = bisect_left(l[j], shortest + second)
        # ans += k

        k = bisect_left(l, shortest + second)
        ans += k - j - 1

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

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

E = []
for p in P:
    e = 0
    for i in range(1, p + 1):
        e += i * (1 / p)
    E.append(e)

ans = 0
for i in range(0, N - K + 1):
    ans = max(ans, sum(E[i:i + K]))

print(ans)


### FIXED CODE ###

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

E = []
for p in P:
    e = ((p * p + p) / 2) * (1 / p)
    E.append(e)

memo = sum(E[:K])
ans = memo
for i in range(0, N - K):
    memo = memo - E[i] + E[i + K]
    ans = max(ans, memo)

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

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

for i in range(1,N+1):
    print(A.count(i))


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
m = [0]*N #0~N-1

for i in A:
    m[i-1] += 1
# print(m)
for i in range(N):
    print(m[i])
### BUGGY CODE ###

h, n = map(int, input().split())
A, B = [], []
for _ in range(n):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

dp = [[10 ** 8 for _ in range(h + max(A) + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, h + max(A) + 1):
        if j <= A[i - 1]:
            dp[i][j] = min(dp[i - 1][j], B[i - 1])
        else:
            dp[i][j] = min(dp[i - 1][j], dp[i][j - A[i - 1]] + B[i - 1])

ans = min([dp[n][i] for i in range(h, h + max(A) + 1)])
print(ans)

### FIXED CODE ###

h, n = map(int, input().split())
a, b = [0], [0]
for _ in range(n):
    s, t = map(int, input().split())
    a.append(s)
    b.append(t)
dp = [[0 for _ in range(h + max(a))] for _ in range(n + 1)]
for i in range(n + 1):
    for j in range(1, h + max(a)):
        if i == 0:
            dp[i][j] = 10 ** 9
        elif a[i] > j:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = min(dp[i - 1][j], dp[i][j - a[i]] + b[i])
ans = 10 ** 9
for i in range(h, h + max(a)):
    if ans > dp[n][i]:
        ans = dp[n][i]
print(ans)
### BUGGY CODE ###

import itertools
n, m, r = map(int, input().split())
R = [int(x) for x in input().split()]
inf = pow(10, 9)+7

roads = [[inf]*n for _ in range(n)]
for i in range(m):
  a, b, c = map(int, input().split())
  roads[a-1][b-1] = c
  roads[b-1][a-1] = c

for k in range(n):
  for i in range(n):
    for j in range(n):
      if roads[i][j] > roads[i][k]+roads[k][j]:
        roads[i][j] = roads[i][k]+roads[k][j]

ans = inf
for value in itertools.permutations(R):
  sub = 0
  for k in range(r-1):
    sub += roads[value[k]-1][value[k+1]-1]
  if ans > sub:
    ans = sub

print(ans)

### FIXED CODE ###

import itertools
n, m, r = map(int, input().split())
R = [int(x) for x in input().split()]
inf = pow(10, 9)+7

roads = [[inf]*n for _ in range(n)]
for i in range(m):
  a, b, c = map(int, input().split())
  roads[a-1][b-1] = c
  roads[b-1][a-1] = c

for k in range(n):
  for i in range(n):
    for j in range(n):
      if roads[i][j] > roads[i][k]+roads[k][j]:
        roads[i][j] = roads[i][k]+roads[k][j]

ans = inf
for value in itertools.permutations(R):
  sub = 0
  for k in range(r-1):
    sub += roads[value[k]-1][value[k+1]-1]
  if ans > sub:
    ans = sub

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

import sys
input = sys.stdin.buffer.readline
N = int(input())
A = list(map(int, input().split()))
MOD = 10**9 + 7

ans = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        v = A[i] * A[j] % MOD
        ans = (ans + v) % MOD
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
MOD = 10**9 + 7

N = int(input())
A = [0] + list(map(int, input().split()))

C = [0]
for i in range(1, len(A)):
    C.append(C[-1] + A[i])

ans = 0
for i in range(1, N):
    ans += A[i] * (C[-1] - C[i])

ans %= MOD
print(ans)
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
I = 0
J = 0
K = 0
for i in range(N):
    if a[i] == 3:
        I += 1
    elif a[i] == 2:
        J += 1
    elif a[i] == 1:
        K += 1

DP = [[[-1 for i in range(N+1)] for i in range(N+1)] for i in range(N+1)]
DP[0][0][0]=0

def cal(i,j,k):
    if DP[i][j][k] != -1:
        return DP[i][j][k]
    else:
        res = 0
        if i != 0:
            res += i*cal(i-1,j+1,k)
        if j != 0:
            res += j*cal(i,j-1,k+1)
        if k != 0:
            res += k*cal(i,j,k-1)
        res += N
        res /= i+j+k
        DP[i][j][k] = res
        return res

print(cal(I,J,K))

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
I = 0
J = 0
K = 0
for i in range(N):
    if a[i] == 1:
        I += 1
    if a[i] == 2:
        J += 1
    if a[i] == 3:
        K += 1

dp = [[[0.0]*(N+2) for _ in range(N+2)] for _ in range(N+2)]
for k in range(K+1):
    for j in range(J+K+1):
        if j+k > N:
            break
        for i in range(N+1):
            S = i+j+k
            if S > N:
                break
            if S == 0:
                continue
            dp[i][j][k] = (i*dp[i-1][j][k]+j*dp[i+1][j-1][k]+k*dp[i][j+1][k-1]+N)/S
print(dp[I][J][K])
### BUGGY CODE ###

print(sum(range(1, int(input()))))


### FIXED CODE ###

N = int(input())
print(((N - 1) * N // 2))
### BUGGY CODE ###

def myfunc(h, w):
    if T[h][w] == '.' or T[h][w] == 'True':
        T[h][w] = c
        for i in [(0,1), (0,-1), (1,0), (-1,0)]:
            myfunc(h+i[0], w+i[1])

H, W= map(int, input().split())
CH, CW= map(int, input().split())
DH, DW= map(int, input().split())
S = ['#'+input()+'#' for _ in range(H)]
S.insert(0,'#'*(W+2))
S.append('#'*(W+2))
T = [[0] * (W+2) for _ in range(H+2)]
for i in range(H+2):
    for j in range(W+2):
        T[i][j] = S[i][j]
c = 0
myfunc(CH, CW)
warp = True
while T[DH][DW] == '.' and warp == True:
    warp = False
    for i in range(H+2):
        for j in range(W+2):
            if T[i][j] == c:
                 for k in range(-2, 3):
                     for l in range(-2, 3):
                         if 0<=i+k and i+k<H+2 and 0<=j+l and j+l<W+2 and T[i+k][j+l] == '.':
                             warp = True
                             T[i+k][j+l] = 'True'
    c += 1
    for i in range(H+2):
        for j in range(W+2):
            if T[i][j] == 'True':
                myfunc(i, j)
if T[DH][DW] == '#' or T[DH][DW] == '.':
    print(-1)
else:
    print(T[DH][DW])


### FIXED CODE ###

from collections import deque
H, W= map(int, input().split())
CH, CW= map(int, input().split())
DH, DW= map(int, input().split())
S = [list(map(str, input())) for _ in range(H)]
q = deque([(CH-1, CW-1, 0)])
while q:
    h, w, c = q.popleft()
    if S[h][w] == '.':
        S[h][w] = c
        for i in range(-2, 3):
            for j in range(-2, 3):
                if 0<=h+i<H and 0<=w+j<W and S[h+i][w+j] == '.':
                    if abs(i)+abs(j) == 1:
                        q.appendleft((h+i, w+j, c))
                    elif abs(i)+abs(j) >= 2:
                        q.append((h+i, w+j, c+1))
if S[DH-1][DW-1] == '.':
    print(-1)
else:
    print(S[DH-1][DW-1])
### BUGGY CODE ###

n, k = map(int, input().split())
pl = list(map(int, input().split()))

ave_pl = []
for i, p in enumerate(pl):
    p_sum = p*(p+1)/2
    ave_pl.append(p_sum/p)

ans = 0
for i in range(n-k+1):
    ans = max(ans, sum(ave_pl[i:i+k]))

print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
pl = list(map(int, input().split()))

ave_pl = []
for i, p in enumerate(pl):
    p_sum = p*(p+1)/2
    if i == 0:
        ave_pl.append(p_sum/p)
    else:
        ave_pl.append(ave_pl[i-1]+(p_sum/p))

ans = 0
if n == k:
    print(ave_pl[-1])
else:
    for i in range(k-1, n):
        if i == 0:
            ans = max(ans, ave_pl[i])
        else:
            ans = max(ans, ave_pl[i]-ave_pl[i-k])
    print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(min(k, 41)):
    b = [0]*n
    for j in range(n):
        for l in range(a[j]+1):
            if j >= l:
                b[j-l] += 1
            if n-1-j >= l:
                b[j+l] += 1
            if l == 0:
                b[j] -= 1
    a = b
print(*a)

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
for _ in range(min(k, 50)):
    b = [0]*(n+1)
    for i in range(n):
        b[max(0, i-a[i])] += 1
        b[min(i+a[i]+1, n)] -= 1
    for i in range(1, n+1):
        b[i] += b[i-1]
    for i in range(n):
        a[i] = b[i]
print(*a)
### BUGGY CODE ###

N = int(input())
S = list(input())
ans = set()

# 真ん中を固定
for i in range(1, N - 1):
    left = set(S[:i])
    right = set(S[i + 1 :])
    for l in left:
        for r in right:
            ans.add(l + S[i] + r)

print(len(ans))


### FIXED CODE ###

import sys


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


def main():
    N = int(input())
    S = list(input())
    ans = 0

    for p in range(1000):
        p = str(p).zfill(3)
        i = 0
        for j in range(N):
            if p[i] == S[j]:
                i += 1
            if i == 3:
                ans += 1
                break

    print(ans)


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

H,W = map(int,input().split())
cnt = 0
for h in range(H):
    for w in range(W):
        if (h+w) % 2 == 0:
            cnt += 1
print(cnt)

### FIXED CODE ###

H,W = map(int,input().split())
if H == 1 or W == 1:
    print(1)
elif (H*W) % 2 == 0:
    print(H*W // 2)
else:
    print(H*W // 2 + 1)
### BUGGY CODE ###

def solve(x):
    cnt = 1
    while x > 0:
        count = 0
        y = x
        while y > 0:
            count += (y%2==1)
            y >>= 1
        x %= count
        cnt += 1
    return cnt

n = int(input())
x = input()
one = x.count('1')
num = int(x, 2)

up = num%(one+1)
if one == 1:
    down = 0
else:
    down = num%(one-1)

for i in range(n):
    if x[i] == '1':
        if one == 1:
            print(0)
            continue
        s = down - (2**(n-i-1))%(one-1)
        if s < 0:
            s += one-1
    else:
        s = (up + (2**(n-i-1))%(one+1))%(one+1)
    print(solve(s))

### FIXED CODE ###

def solve(x):
    cnt = 1
    while x > 0:
        x %= bin(x).count('1')
        cnt += 1
    return cnt

n = int(input())
x = input()
one = sum(map(int, list(x)))
num = int(x, 2)

up = num%(one+1)
if one == 1:
    down = 0
else:
    down = num%(one-1)

for i in range(n):
    if x[i] == '1':
        if one == 1:
            print(0)
            continue
        s = (down - pow(2, n-i-1, one-1))%(one-1)
    else:
        s = (up + pow(2, n-i-1, one+1))%(one+1)
    print(solve(s))