Harryxun/stf_run huggingface dataset:
import sys;input=sys.stdin.readline
from bisect import*

n,q=map(int,input().split())
event=[]
stopped={-1}

def doevent(l):
    global stopped
    if l[1]==1:
        if stopped=={-1}:
            stopped=set()
        stopped.add(l[2])
    elif l[1]==-1:
        stopped.remove(l[2])
        if len(stopped)==0:
            stopped={-1}
            
for i in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x,1,x))
    event.append((t-x,-1,x))
event.append((-float("inf"),"x","x"))
event.append((float("inf"),"x","x"))
event.sort(key=lambda x:x[0])
eventtime=[i[0]for i in event]
#print(eventtime)
query=[bisect_right(eventtime,int(input()))-1 for i in range(q)]
#print(query)
c=0
#print(event)
for i in range(2*n):
    doevent(event[i])
    while i==query[c]:
        print(min(stopped))
        c+=1
        if c==q:
            break
for i in range(query.count(2*n)):
    print(-1)


### FIXED CODE ###

import sys;input=sys.stdin.readline

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))
    
event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop
        
print('\n'.join(map(str, ans)))
import sys
h,w=map(int,input().split())
dr=[input()+'.' for _ in range(h)]

if h==1 and w==1:
  print('Yes')
  sys.exit()

if dr[0][0]=='#':
  if dr[1][0]!='#' and dr[0][1]!='#':
    print('No')
    print(dr[1][0])
    sys.exit()
for j in range(1,w-1):
  if dr[0][j]=='#':
    if dr[0][j+1]!='#' and dr[1][j]!='#' and dr[0][j-1]!='#':
      print('No')
      sys.exit()
if dr[0][w-1]=='#':
  if dr[1][w-1]!='#' and dr[0][w-2]!='#':
    print('No')
    sys.exit()
for i in range(1,h-2):
  if dr[i][0]=='#':
    if dr[i+1][0]!='#' and dr[i][1]!='#' and dr[i-1][0]!='#':
      print('No')
      sys.exit()
  for i in range(1,w-1):
    if dr[i][j]=='#':
      if dr[i][j+1]!='#' and dr[i+1][j]!='#' and dr[i-1][j]!='#' and dr[i][j-1]!='#':
        print('No')
        sys.exit()
  if dr[i][w-1]=='#':
    if dr[i+1][w-1]!='#' and dr[i-1][w-1]!='#' and dr[i][w-2]!='#':
      print('N0')
      sys.exit()
if dr[h-1][0]=='#':
  if dr[h-1][1]!='#' and dr[h-2][0]!='#':
    print('N0')
    sys.exit()
for j in range(1,w-1):
  if dr[h-1][j]=='#':
    if dr[h-1][j+1]!='#' and dr[h-1][j-1]!='#' and dr[h-2][j]!='#':
      print('No')
      sys.exit()
if dr[h-1][w-1]=='#':
  if dr[h-1][w-2]!='#' and dr[h-2][w-1]!='#':
    print('N0')
    sys.exit()
print('Yes')

### FIXED CODE ###

h,w=map(int,input().split())
a=['.'*(w+2)]+['.'+input()+'.' for _ in range(h)]+['.'*(w+2)]
for i in range(h):
  for j in range(w):
    if a[i][j]=='#':
      if not(a[i+1][j]=='#' or a[i-1][j]=='#' or a[i][j+1]=='#' or a[i][j-1]=='#'):
        print('No')
        exit()
print('Yes')
N = int(input())
l = []

def main(n):
  global l
  i = 1
  while True:
    tmp = i*(i+1)//2
    if tmp >= n:
      l.append(i)
      if n-i == 0:
        return l
      else:
        return main(n-i)
    i += 1
        
li = main(N)
for n in li:
  print(n)

### FIXED CODE ###

import sys
N = int(input())
l = []

def main(n):
  global l
  i = 1
  while True:
    tmp = i*(i+1)//2
    if tmp >= n:
      l.append(i)
      if n-i == 0:
        return l
      else:
        return main(n-i)
    i += 1
    
sys.setrecursionlimit(10000)
li = main(N)
for n in li:
  print(n)
n=int(input())

table=[0]*100000

for i in range(n):
    a=int(input())
    table[a-1]+=1

ans=0

for j in range(100000):
    if table[j]%2==1:
        ans+=1

print(ans)

### FIXED CODE ###

n=int(input())

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

dic={}

for i in range(n):
    if a[i] not in dic:
        dic[a[i]]=1
    else:
        dic[a[i]]+=1

ans=0

for val in dic.values():
    if val%2==1:
        ans+=1

print(ans)
x = int(input(3))
x ** 3 = y
print 


### FIXED CODE ###

x = int(input())
print (x ** 3)
input()
s = input()
k = int(input())
print(''.join(c if c == s[k] else '*' for c in s))

### FIXED CODE ###

input()
s = input()
k = int(input())
print(''.join(c if c == s[k-1] else '*' for c in s))
# coding:utf-8                                                                  

alls = raw_input()
tarx, tary = map(int, raw_input().split())

ss = alls.split("T")

xs = []
ys = []
posx = set()
posy = set()
posy.add(0)
for i, s in enumerate(ss):
    if i == 0:
        posx.add(len(s))
    elif i % 2 == 0:
        xs.add(len(s))
    else:
        ys.add(len(s))

for x in xs:
    tmpx = set()
    for px in posx:
        tmpx.add(px+x)
        tmpx.add(px-x)
    posx = tmpx

for y in ys:
    tmpy = set()
    for py in posy:
        tmpy.add(py+y)
        tmpy.add(py-y)
    posy = tmpy

if tarx in posx and tary in posy:
    print "Yes"
else:
    print "No"

### FIXED CODE ###

# coding:utf-8                                                                  

alls = raw_input()
tarx, tary = map(int, raw_input().split())

ss = alls.split("T")

xs = []
ys = []
posx = set()
posy = set()
posy.add(0)
for i, s in enumerate(ss):
    if i == 0:
        posx.add(len(s))
    elif i % 2 == 0:
        xs.append(len(s))
    else:
        ys.append(len(s))

for x in xs:
    tmpx = set()
    for px in posx:
        tmpx.add(px+x)
        tmpx.add(px-x)
    posx = tmpx

for y in ys:
    tmpy = set()
    for py in posy:
        tmpy.add(py+y)
        tmpy.add(py-y)
    posy = tmpy

if tarx in posx and tary in posy:
    print "Yes"
else:
    print "No"
def sol(inp=input):
    import math
    a,b,c,d=map(int,inp().split())
    def fix_min(b):
        c_=b//c
        d_=b//d
        cd_=b//(c*d//math.gcd(c,d))
        return b-c_-d_+cd_
    return fix_min(b)-fix_min(a-1)
print(sol())

### FIXED CODE ###

def sol(inp=input):
    a,b,c,d=map(int,inp().split())
    def gcd(x,y):
        while y>0:
            x,y=y,x%y
        return x
    def fix_min(b):
        c_=b//c
        d_=b//d
        cd_=b//(c*d//gcd(c,d))
        return b-c_-d_+cd_
    return fix_min(b)-fix_min(a-1)
print(sol())
while True:
  a,op,b = raw_input().split
  a,b = map(int,[a,b])

  if op == "?":
     break

  if op == "+":
     print (a+b)
  elif op == "-":
     print (a-b)
  elif op == "*":
     print (a*b)
  elif op == "/":
     print (a/b)

### FIXED CODE ###

while True:
  a,op,b = raw_input().split()
  a,b = map(int,[a,b])

  if op == "?":
     break

  if op == "+":
     print (a+b)
  elif op == "-":
     print (a-b)
  elif op == "*":
     print (a*b)
  elif op == "/":
     print (a/b)
n=int(input())
rowdata=[int(i) for i in input().split()]
rowdata.sort()

if n%2==0:
    check=[]
    for i in range(1,n,2):
        check.append(i)
        check.append(i)
    if check==rowdata:
        print(int(2**(n/2)))
    else:
        print(0)
else:
    check=[]
    if n==1:
        check=[0]
    else:
        for i in range(0,n,2):
            if i==0:
                check.append(i)
            else:
                check.append(i)
                check.append(i)
    if check==rowdata:
        print(int(2**((n-1)/2)))
    else:
        print(0)

### FIXED CODE ###

n=int(input())

#データを並び替える
rowdata=[int(i) for i in input().split()]
rowdata.sort()

#nが偶数の時
if n%2==0:
    check=[]
    a=1
    for i in range(1,n,2):
        check.append(i)
        check.append(i)
    if check==rowdata:
        for i in range(int(n/2)):
            a*=2
            a=a%1000000007
        print(a)
    else:
        print(0)
        
#nが奇数の時
else:
    check=[]
    a=1
    if n==1:
        check=[0]
    else:
        for i in range(0,n,2):
            if i==0:
                check.append(i)
            else:
                check.append(i)
                check.append(i)
    if check==rowdata:
        for i in range(int((n-1)/2)):
            a*=2
            a=a%1000000007
        print(a)
    else:
        print(0)
N=int(input())
A=N-1000*(N//1000)
B=((N//1000)+1)*1000-N
if A<=B:
  return A
else:
  return B

### FIXED CODE ###

N=int(input())
A=1000*(N//1000)-N
B=((N//1000)+1)*1000-N
if A<=B and A>=0:
  print(int(A))
else:
  print(int(B))
import string

n=int(raw_input())

for i in range(n):
    print(raw_input().replace("Hoshino", "Hoshina"))

### FIXED CODE ###

import string

n=int(input())

for i in range(n):
    print(input().replace("Hoshino", "Hoshina"))
import sys
input = sys.stdin.readline
from fractions import gcd

N=int(input())
a_list = list(map(int, input().split()))
MOD = 10**9+7


def cal_lcm(a, b):
  return int(a*b/gcd(a,b))


lcm = 1
ans = 0
for i in range(N):
  lcm_ = cal_lcm(lcm, a_list[i])
  ans = ans*int(lcm_/lcm) % MOD
  ans = (ans + int(lcm_/a_list[i])) % MOD
  lcm = lcm_

print(ans)

### FIXED CODE ###

from fractions import gcd
 
N=int(input())
a_list = tuple(int(i) for i in input().split())
MOD = 10**9+7

def cal_lcm(a, b):
  return int(a*b//gcd(a,b))

lcm = 1
for i in range(N):
  lcm = cal_lcm(lcm, a_list[i])
  
ans = 0
for i in range(N):
  ans += lcm//a_list[i]
print(ans%MOD)
A,B=map(int,iput().split())
 
if A+B>=24:
  print(A+B-24)
else:
  print(A+B)

### FIXED CODE ###

A,B=map(int,input().split())
 
if A+B>=24:
  print(A+B-24)
else:
  print(A+B)
from collections import defaultdict
from bisect import bisect_right

s = input()
t = input()
d = defaultdict(list)

for i, x in enumerate(s):
    for j in range(len(t)):
        d[x].append(i + len(s) * j)
for x in d.values(): x.sort()

ans = 0
for x in t:
    if x not in d: print(-1); exit()
    ans = d[x][bisect_right(d[x], ans)]

print(ans+1)


### FIXED CODE ###

from collections import defaultdict
from bisect import bisect_right

s = input()
t = input()
idxs = defaultdict(list)

for i, c in enumerate(s):
    idxs[c].append(i)
for i, c in enumerate(s):
    idxs[c].append(len(s) + i)

ans, cur_i = -1, -1
for c in t:
    if c not in idxs: print(-1); break
    a = idxs[c]
    nxt = a[bisect_right(a, cur_i)]
    ans += nxt - cur_i
    cur_i = nxt % len(s)
else: print(ans+1)
a = int(input())
mozi = input()
b = int(input())

test = mozi[b]

ans = ""

for i in mozi:
    if i == test:



### FIXED CODE ###

s = [int(i) for i in input().split(" ")]
count = 0

if s[0] < s[1]:
    for i in range(s[0], s[1]):
        if i == s[2]:
            print("Yes")
            count = 1
            break

else:
    for i in range(s[1], s[0]):
        if i == s[2]:
            print("Yes")
            count = 1
            break

if count == 0:
    print("No")
N = input()
K = input()
counter = 0
for i in range(int(N))
    if int(input()) >= int(K) :
       counter++
print(counter)


### FIXED CODE ###

N,K = map(int,input().split())
height_list = list(map(int,input().split()))
print(sum([1 for i in height_list if i >= K]))
n=str(N)
if n.find("7")!= -1:
   print('Yes')
else:
   print('No')


### FIXED CODE ###

n=str(input())
if n.find("7")!= -1:
   print("Yes")
else:
   print("No")
ab = input().rstrip().split(" ")
a = ab[0]
b = ab[1]
if a * b % 2 == 0:
  print("Even")
else:
  print("Odd")

### FIXED CODE ###

ab = input().rstrip().split(" ")
a = int(ab[0])
b = int(ab[1])
if a * b % 2 == 0:
  print("Even")
else:
  print("Odd")
N = int(input())
a = list(map(int,input().split())).sort(reverse=True)
answer = 0
for i in range(0,N,2):
  answer += a[i]
for i in range(1,N,2):
  answer -= a[i]
print(answer)

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)
answer = 0
for i in range(0,N,2):
  answer += a[i]
for i in range(1,N,2):
  answer -= a[i]
print(answer)
import sys
sys.setrecursionlimit(1000000)
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
n = I()
n_z = n # n/z
prime_e = [] # 素数**自然数のリスト
p = 2 # 最初の素数
e = 1

def fermat_test(q):
    if q == 2: return True
    elif q < 2 or q & 1 == 0: return False   # q & 1 == 0 偶数の場合のFalseを返す意。 


if n == 1:
    print(0)
    sys.exit()


while p * p <= n: # 素数pの2乗がnより大きいと1回も割れない。
    if n_z % p == 0:
        z = p ** e
        while n_z % z == 0:
            if z not in prime_e:
                n_z = int(n_z / z)
                prime_e.append(z)
            e += 1
            z = p ** e
    p += 1
    e = 1
    while fermat_test(p) == False:
        p += 1
print(len(prime_e)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
from collections import defaultdict
n = I()
def primes(n):
    cnt = defaultdict(int)
    for i in range(2,int(n**0.5)+1): # range(3)だと、0,1,2が出てくる。
        while n % i == 0:
            cnt[i] += 1 # 同じ素数で何回割れるか辞書型で登録しておく
            n //= i # iで割り切った商で更新しておく
    if n > 1: # nの平方根より大きい値があった場合、追加
        cnt[n] += 1
    return cnt
prs = primes(n) #　素数の辞書
ans = 0
for key in prs.keys(): #辞書から素数を抽出して、その素数の指数値をvとして格納する。
    v = prs[key]
    for i in range(100):
        # if (i * (i+1)) // 2 <= v:　これだと何度も足し算してしまう。
        if (i * (i + 1)) // 2 > v: # 指数eを超えた一つ前が目的の計数である。
            ans += (i-1)
            break
print(ans)
import sys

DBG_FLAG = 0

def p_dbg(str):
    if(DBG_FLAG == 1):
        sys.stdout.flush()
        print str

# 1st. get Num

Num = int(raw_input())

p_dbg('Num : ' + str(Num))

square_max = 1

# MEMORY OVER
# for i in range(1, Num):
#     tmp = i * i
#     p_dbg(str(i) + str(square_max))
#     if(tmp <= Num):
#         square_max = tmp
#     else:
#         break

i = 1
tmp = 1
while tmp < Num:
    p_dbg(str(i) + ':' + str(square_max))
    square_max = tmp
    tmp = i*i
    i = i+1

print square_max


### FIXED CODE ###

import sys

DBG_FLAG = 0

def p_dbg(str):
    if(DBG_FLAG == 1):
        sys.stdout.flush()
        print str

def get_row():
    array = []
    txt = raw_input()

    for char in txt:
        array.append(char)

    return array

# defined & initial arrays
cells_top = []
cells_bottom = []

# get cells
cells_top = get_row()
cells_bottom = get_row()

p_dbg(cells_top)
p_dbg(cells_bottom)

# reverse
cells_top.reverse()

p_dbg(cells_top)

# Decision
if(cells_top == cells_bottom):
    print 'YES'
else:
    print 'NO'
#入力取得
N, X = map(int, input().split())
l = tuple(map(int,input().split()))


d = 0
ans = 0

for i in range(N+1):
    if d > X:
        break
    else:
        ans += 1
        d = d + l[i]
print(ans)


### FIXED CODE ###

#入力取得
N, X = map(int, input().split())
l = tuple(map(int,input().split()))


d = 0
ans = 1

for l_e in l:

    d += l_e

    if d > X:
        break
    else:
        ans += 1



print(ans)
s = input()
ans = 0
for i in range((len(s)-1)//2+1):
  if a[i] != a[-1-i]:
    ans += 1
print(ans)

### FIXED CODE ###

s = input()
ans = 0
for i in range((len(s)-1)//2+1):
  if s[i] != s[-1-i]:
    ans += 1
print(ans)
a,b=int(input().split())
print(a*b)

### FIXED CODE ###

a,b= input().split()
a=int(a)
b=int(b)

print(a*b)
import math
import copy

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

if n>2:
    memo = list([])

    for k in range(n):
        t = copy.copy(s_all)
        t.pop(k)

        c = math.gcd(t[0], t[1])

        for i in s:
            c = math.gcd(c,i)

        memo.append(c)

    print(max(memo))

if n==2:
    print(max(s_all))

### FIXED CODE ###

import numpy as np

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

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

l = [0]*n
r = [0]*n

for i in range(1,n):
    l[i]=gcd(l[i-1],s[i-1])

tmp = list(range(0,n-1))
tmp.reverse()
for i in tmp:
    r[i]=gcd(r[i+1],s[i+1])
    
m = list([])

for i in range(n):
    m.append(gcd(l[i],r[i]))

print(max(m))
n int(input())
c = 0
for i in range(1, n+1):
  if len(list(str(i))) % 2 != 0:
    c += 1

print(c)

### FIXED CODE ###

n = int(input())
c = 0
for i in range(1, n+1):
  if len(list(str(i))) % 2 != 0:
    c += 1

print(c)
N = input()
A = input()
if A >= N%500:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

N = int(input())
A = int(input())
if A >= (N % 500):
  print("Yes")
else:
  print("No")
from bisect import bisect_left
from collections import deque
from itertools import islice
N, M = list(map(int, input().split()))
As = list(map(int, input().split()))
cards = {}
for i in range(N):
    cards[As[i]] = cards.get(As[i], 0) + 1
sorted_keys = deque(sorted(cards.keys()))

for i in range(M):
    b, c = list(map(int, input().split()))
    cnt = 0
    for k in islice(sorted_keys,0,bisect_left(sorted_keys, c)):
        for _ in range(cards.get(k,0)):
            cards[k] = cards[k] - 1
            if cards[k] == 0:
                del(cards[k])
                sorted_keys.remove(k)
            cards[c] = cards.get(c, 0) + 1
            if c not in sorted_keys:
                sorted_keys.insert(bisect_left(sorted_keys, c),c )
            cnt += 1
            # print('aaa:   ', b, c, cnt)
            if cnt >= b:
                break
        if cnt >= b:
            break
    # print()
    # print(cards)
    # print()

# print(list(cards.items()))
print(sum([k * cnt for k,cnt in cards.items()]))




### FIXED CODE ###

N, M  = map(int,input().split())
As = sorted(list(map(int,input().split())))
di = {}
for i in range(M):
    b, c = map(int,input().split())
    di[c] = di.get(c, 0) + b

keys = list(sorted(di.keys(), reverse=True))
ichi = 0
for i in range(N):
    try:
        if keys[ichi] > As[i]:
            As[i] = keys[ichi]
            di[keys[ichi]] -= 1
        else:
            break
        if di[keys[ichi]] == 0:
            ichi += 1
    except:
        pass
print(sum(As))
a = input().split(" ")
l = input().split(" ")
x = int(a[1])
y = 0
num = 1
for i in l:
    y += i
    if y <= x:
        num += 1
    else:
        break
print(num)

### FIXED CODE ###

a = input().split(" ")
l = input().split(" ")
x = int(a[1])
y = 0
num = 1
for i in l:
    y += int(i)
    if y <= x:
        num += 1
    else:
        break
print(num)
n, m = (int(_) for _ in input().split())
x = [int(input()) for i in range(m)]
xi = 0

if m == 0:
    x = [999999]

a = [1,1]
if x[xi] == 1:
    xi += 1
    a[1] = 0

for i in range(n-1):
    if x[xi]-2 == i:
        a.append(0)
        xi = min(len(x)-1,xi+1)
    else:
        a.append(a[i+1]+a[i])

print(a[n]%1000000007)

### FIXED CODE ###

n, m = (int(_) for _ in input().split())
x = [int(input()) for i in range(m)]
xi = 0

if m == 0:
    x = [999999]

a = [1,1]
if x[xi] == 1:
    xi = min(len(x)-1,xi+1)
    a[1] = 0

for i in range(n-1):
    if x[xi]-2 == i:
        a.append(0)
        xi = min(len(x)-1,xi+1)
    else:
        a.append(a[i+1]+a[i])

print(a[n]%1000000007)
n = int(input())
last_chosen = -1

max_points = 0
for i in range(n):
    days = list(map(int, input().split()))
    while True:
        act = max(days)
        idx = days.index(act)
        if idx != last_chosen:
            break
        days.pop(idx)
    max_points += days[idx]
    last_chosen = idx
print(max_points)


### FIXED CODE ###

n=int(input())

dp=list(map(int,input().split()))
for day in range(1,n):
    m=[0]*3
    day_points=list(map(int, input().split()))
    for i in range(3):
        for j in range(3):
            if i!=j:
                 m[i]=max(m[i],day_points[i]+dp[j])
    dp=m
print(max(dp))
x,y = map(int, input().split())
list = [x, y]

if x == 0 and y == 0:
    break

print(sorted(list, reverse=True))
       


### FIXED CODE ###

while True:
    x,y = map(int, input().split())

    if x == 0 and y == 0:
        break

    elif x <= y:
        print(str(x) + " " + str(y))
    else:
        print(str(y) + " " + str(x))
N, K = map(int, input())

ans = 0
while True:
    N = N // K
    ans += 1
    if N == 0:
        break

print(ans)

### FIXED CODE ###

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

ans = 0
while True:
    N //= K
    ans += 1
    if N == 0:
        break

print(ans)
a = []
for i in range(5):
    a.append(int(input()))

b = []
for i in range(5):
    b.append(a[i]%10)
  
def kiriage(n):
    if n%10==0:
        return n
    else:
        amari = n%10
        n = n - amari
        return n+10

#non-zero かつ minimum
mini_amari = 9
idx = 9
for i in range(len(b)):
    if b[i]<mini_amari and b[i]!=0:
        mini_amari = b[i]
        idx = i

res = 0
for i in range(len(a)):
    if i != idx:
        res += kiriage(a[i])
res += a[idx]
print(res)

### FIXED CODE ###

#cited by maspy
A = [int(input()) for _ in range(5)]
 
ceiled = [(x+9)//10*10 for x in A]
can_save = [y - x for x,y in zip(A,ceiled)]

answer = sum(ceiled) - max(can_save)
print(answer)
N = int(input())
T, A = (int(i) for i in input().split())
H = [int(i) for i in input().split()]

H_T = [0 for i in range(len(H))]
for i in range(len(H)):
    H_T[i] = float(T) - float(H[i])*0.006

min = 1000
index = 0
for i in range(len(H_T)):
    if(abs(H_T[i] - A) < min):
        index = i
        min = abs(H_T[i] - A)
print(index+1)


### FIXED CODE ###

x, y = (int(i) for i in input().split())

print(int(x+y/2))
for i in range(1,10001):
    line = input()
    if line == "0":
        break
    else:
        print('Case %s: %s', %(i, line))


### FIXED CODE ###

#
# 3b
#

def main():
    i = 1
    while True:
        x = int(input())
        if x == 0:
            break
        print(f"Case {i}: {x}")
        i += 1


if __name__ == '__main__':
    main()
books1= list(map(int, input().split()))
i=0
while(i<len(books)):
  if(books1[i]==0):
    print(i+1)
    break
    i+=1

### FIXED CODE ###

books1= list(map(int, input().split()))
i=0
while(i<len(books1)):
  if(books1[i]==0):
    break
  i+=1
print(i+1)
print n ** 3

### FIXED CODE ###

n = input()

cube = n ** 3

print cube
n, k = [int(x) for x in input().split()]
a = [int(x)-1 for x in input().split()]

visited = [0]
x = 0
T = -1
while T < 0:
  x = a[x]
  if x in visited:
    for j in range(i):
      if visited[j] == x:
        first = j
        break
    T = i - j
  else:
    visited.append(x)
  break
    
mod = (k-first) % T
print(a[first+mod]+1)


### FIXED CODE ###

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

visited = [-1 for i in range(n+1)] # 訪れていたら訪れたときの添字を格納する。
points = []
p = 1
while visited[p] == -1:
  visited[p] = len(points)
  points.append(p)
  p = a[p-1] #添字に直す

T = len(points) - visited[p]
s = visited[p]

if k < s:
  print(points[k])
else:
  mod = (k - s) % T
  print(points[s+mod])
n=int(input())
xs=input()
xk=list(map(int,list(xs)))
xj=xk.count(1)

x=int(xs,2)

def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

for i in range(n-1,-1,-1):
    xi=x^(1<<i)
    pxi=xj
    if xs[i]==0:
        pxi=pxi-1
    if xi==0:
        print(0)
    else:
#    print(xi,popcount(xi),xi%popcount(xi))
        icnt=0
        while xi>0:
            icnt+=1
            xi=xi%popcount(xi)
    print(icnt)


### FIXED CODE ###

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

n=int(input())
xs=input()
xj=xs.count("1")

x=int(xs,2)
xip=x%(xj+1)
if xj!=1:
    xim=x%(xj-1)

for i in range(n-1,-1,-1):
    if xs[n-1-i]=="0":
        pxi=xj+1
        i2=pow(2,i,pxi)
        xi=(xip+i2)%pxi
    elif xj==1:
        print(0)
        continue
    else:
        pxi=xj-1
        i2=pow(2,i,pxi)
        xi=(xim-i2)%pxi
    xi=xi%pxi
    if xi==0:
        print(1)
        continue
    icnt=1
    while xi>0:
#        print("i",i,"xi",xi,"icnt",icnt)
        icnt+=1
        xi=xi%(bin(xi).count("1"))
    print(icnt)