Harryxun/stf_run huggingface dataset:
import bisect

n, d, a = map(int, input().split())
xh = []
for i in range(n):
    xh.append(list(map(int, input().split())))
xh.sort()
count = 0
min_x = 0
x = [xh[i][0] for i in range(n)]
sum_h = sum([xh[i][1] for i in range(n)])
while sum_h > 0:
    place = xh[min_x][0] + d
    num = (xh[min_x][1] - 1) // a + 1
    count += num
    edge = bisect.bisect(x, place + d)
    for i in range(min_x, edge):
        new_h = max(0, xh[i][1] - a * num)
        sum_h -= (xh[i][1] - new_h)
        if new_h == 0:
            min_x += 1
        xh[i][1] = new_h
print(count)

### FIXED CODE ###

import bisect

n, d, a = map(int, input().split())
xh = []
for i in range(n):
    xh.append(list(map(int, input().split())))
xh.sort()
x = [xh[i][0] for i in range(n)]
h = [xh[i][1] for i in range(n)]
count = 0
min_x = 0
acm = [0] * (n + 1)
dif = [0] * (n + 1)
while min_x < n:
    place = x[min_x] + d
    num = (h[min_x] - acm[min_x + 1] - 1) // a + 1
    count += num
    dif[min_x] += num
    dif[bisect.bisect(x, place + d)] -= num
    for i in range(min_x, bisect.bisect(x, place + d)):
        acm[i + 1] = acm[i] + dif[i] * a
        if acm[i + 1] >= h[i]:
            min_x += 1
            continue
        else:
            break
print(count)
#ALDS1_3-C Elementary data structures - Doubly Linked List
n=int(input())
cmds={"insert":lambda cmd,L: [cmd[1]]+L,
      "delete":lambda cmd,L: L.remove(cmd[1]),
      "deleteFirst":lambda cmd,L: L.pop(0),
      "deleteLast": lambda cmd,L: L.pop()
     }
L=[]
for i in range(n):
    cmd=input().split()
    L = cmds[cmd[0]](cmd,L)
s=""
for i in L:
    s+=i+" "
print(s[:-1])

### FIXED CODE ###

#ALDS1_3-C Elementary data structures - Doubly Linked List
import collections
import sys
q = collections.deque()
n=int(input())
_input = sys.stdin.readlines()
cmds={"insert":lambda cmd: q.appendleft(cmd[1]),
      "delete":lambda cmd: q.remove(cmd[1]) if (q.count(cmd[1]) > 0) else "none",
      "deleteFirst":lambda cmd: q.popleft(),
      "deleteLast": lambda cmd: q.pop()
     }

for i in range(n):
    cmd=_input[i].split()
    cmds[cmd[0]](cmd)
print(*q)
print(max(0,int(input())-int(input())))

### FIXED CODE ###

a,b=map(int,input().split())
print(max(0,a-b))
k=int(input())
s=input()
n=len(s)
if s<=k:
  print(s)
else:
  print(s[:k]+'...')

### FIXED CODE ###

k=int(input())
s=input()
n=len(s)
if n<=k:
  print(s)
else:
  print(s[:k]+'...')
import math
N,M =map(int,input().split())
if N!=1:
    N1=(math.factorial(N))//(math.factorial(N-2)*2)

else:
    N1=0
    
if M !=1:
    M1=(math.factorial(M))//(math.factorial(M-2)*2)
else:
    M1=0
    
print(str(N1+M1))

### FIXED CODE ###

import math
N,M =map(int,input().split())
if N==1 :
    N1=0
elif N==0:
    N1=0
else:
    N1=(math.factorial(N))//(math.factorial(N-2)*2)
    
if M==1:    
    M1=0
    
elif M ==0:
    M1=0
else:
    M1=(math.factorial(M))//(math.factorial(M-2)*2)
    
print(str(N1+M1))
N = int(input())
A = np.array(list(map(int,input().split(" "))))
Q = int(input())
B = [list(map(int,input().split(" "))) for i in range(0,Q)]

for i in range(0,Q):
    index = [j for j, x in enumerate(A) if x == B[i][0]]
    A[index] = B[i][1]
    print(np.sum(A))
#print("\n".join(list(map(str,A.tolist()))))

### FIXED CODE ###

import collections
N = int(input())
A = list(map(int,input().split(" ")))
Q = int(input())
B = [list(map(int,input().split(" "))) for i in range(0,Q)]
ans = sum(A)
num = collections.Counter(A)
for i in range(0,Q):
    before, after = B[i][0], B[i][1]
    ans += num[before] * (after - before)
    num[after] += num[before]
    num[before] = 0
    print(ans)
# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd, log10
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement, chain
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop, heapify
from copy import copy, deepcopy
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


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

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


n, m = LI()
graph = [[] for _ in range(m)]
v = [False for _ in range(n)]


def dfs(n, depth):
    if v[n - 1] == True:
        return 0
    if depth == m-1:
        return 1
    ans = 0
    v[n - 1] = True
    for node in graph[n - 1]:
        ans += dfs(node, depth+1)

    v[n - 1] = False  # ここが大事.上で探索の一つが終わるからリセットしている.

    return ans


for i in range(m):
    a, b = LI()
    graph[a - 1].append(b)
    graph[b - 1].append(a)

print(dfs(1, 0))

# https://qiita.com/greenteabiscuit/items/31c46ab3ceac07e749d2


### FIXED CODE ###

#Nはノード数、Mはエッジ数
N, M = map(int, input().split())

path_matrix = []

#無向行列の初期化
for n in range(N):
    path_matrix.append([False] * N)

#まず無向グラフを表す行列を作る
for m in range(M):
    line = map(int, input().split())
    paths = [x - 1 for x in line]
    path_matrix[paths[0]][paths[1]] = True
    path_matrix[paths[1]][paths[0]] = True

#最初はvisited、つまり訪問したことのあるノードはひとつもないので、Falseにする
visited = [False] * N


#再帰関数、ここが難しいかもしれない。
def dfs(now, depth):
    if visited[now]:
        return 0
    if depth == N - 1:
        return 1

    visited[now] = True
    total_paths = 0
    for i in range(0, N):
        if path_matrix[now][i]:
            total_paths += dfs(i, depth + 1)

    visited[now] = False

    return total_paths

print(dfs(0, 0))
n = int(input())
a = list(map(int, input().split(' ')))
counter = 0
def merge(a, left, mid, right):
    global counter
    L = []
    R = []
    L = a[left:mid] + [500001]
    R = a[mid:right] + [500001]
    i=0
    j=0
    for k in range(left, right):
        counter += 1
        if(L[i] <= R[j]):
            a[k] = L[i]
            i += 1
        else:
            a[k] = R[j]
            j += 1

def mergeSort(a, left, right):
    if(left+1 < right):
        mid = (left + right) // 2
        mergeSort(a, left, mid)
        mergeSort(a, mid, right)
        merge(a, left, mid, right)

mergeSort(a, 0, n)
#print(" ".join([str(i) for i in a]))
print(*a)
print(counter)



### FIXED CODE ###

import math
sentinel = 1e9 + 1
counter = 0
def merge(a, left, mid, right):
    global counter
    L = a[left:mid] + [sentinel]
    R = a[mid:right] + [sentinel]
    i,j = 0,0
    for k in range(left, right):
        if(L[i] <= R[j]):
            a[k] = L[i]
            i += 1
        else:
            a[k] = R[j]
            j += 1
    counter += right - left
def mergeSort(a, left, right):
    if left+1 < right:
        mid = (left + right) // 2
        mergeSort(a, left, mid)
        mergeSort(a, mid, right)
        merge(a, left, mid, right)


n = int(input())
a = list(map(int, input().split()))
mergeSort(a, 0, n)
print(*a)
print(counter)
import itertools as it

N,M,X=map(int,input().split())
book = [[int(_) for _ in input().split()] for i in range(N)]

combs = it.product([0, 1], repeat=N)
prices = []
for comb in combs:
	bag = [0] * M
	for i in range(N):
		if comb[i] == 0:
			continue
		else:
			for j in range(M):
				bag[j]+=book[i][j]
	if min(bag[1:]) < X:
		continue
	else:
		prices.append(bag[0])

if len(prices) == 0:
	print(-1)
else:
	print(min(prices))

### FIXED CODE ###

import itertools as it

N,M,X=map(int,input().split())
book = [[int(_) for _ in input().split()] for i in range(N)]

combs = it.product([0, 1], repeat=N)
prices = []
for comb in combs:
	bag = [0] * (M+1)
	for i in range(N):
		if comb[i] == 0:
			continue
		else:
			for j in range(M+1):
				bag[j]+=book[i][j]
	if min(bag[1:]) < X:
		continue
	else:
		prices.append(bag[0])

if len(prices) == 0:
	print(-1)
else:
	print(min(prices))
def inpl(): return [int(i) for i in input().split()]

s = input().split('T')
x, y = inpl()
xi = [len(s[i]) for i in s if i%2 == 0]
yi = [len(s[i]) for i in s if i%2 == 1]

X = (sum(xi)-x)//2
x0 = xi.pop(0) 
Hx = {0: True}
for i in xi:
    for j in Hx.copy().keys():
        Hx[j+i] = True
Y = (sum(yi)-y)//2
Hy = {0: True}
for i in yi:
    for j in Hy.copy().keys():
        Hy[j+i] = True
  
ans = 'Yes'      
if (x0+sum(xi)-x)%2 != 0 or (sum(yi)-y)%2 != 0:
    ans = 'No'
if not Hx.get(X, False) or not Hy.get(Y, False):
    ans = 'No'
print(ans)

### FIXED CODE ###

s = input() + 'T'
x, y = [int(i) for i in input().split()]

dire = True
xi = []
yi = []
ctr = 0
for i in range(len(s)):
    if s[i] == 'F':
        ctr += 1
        continue
    if dire:
        xi.append(ctr)
    else:
        yi.append(ctr)
    ctr = 0
    dire = not dire
ans = 'Yes'
X = (sum(xi)-x)//2
x0 = xi.pop(0)
Hx = {0: True}
for i in xi:
    for j in Hx.copy().keys():
        Hx[j+i] = True
Y = (sum(yi)-y)//2
Hy = {0: True}
for i in yi:
    for j in Hy.copy().keys():
        Hy[j+i] = True
        
if (x0+sum(xi)-x)%2 != 0 or (sum(yi)-y)%2 != 0:
    ans = 'No'
if not Hx.get(X, False) or not Hy.get(Y, False):
    ans = 'No'
print(ans)
X,N=map(int,input().split())
if N==0:
    print(X)
    exit()

P_ori=list(map(int,input().split()))
if P_ori.count(X)==0:
    print(X)
    exit()

P1=sorted(P_ori)
N=list(range(1,101))
PZ=[]
for i in range(len(N)):
    if P1.count(N[i])==0:
        PZ.append(N[i])

PZ.append(X)
P2=sorted(PZ)
t=P2.index(X)

dist1=abs(P2[t-1]-P2[t])
dist2=abs(P2[t]-P2[t+1])
if dist1<=dist2:
    print(P2[t-1])
else:
    print(P2[t+1])

### FIXED CODE ###

X,N=map(int,input().split())
if N==0:
    print(X)
    exit()

P_ori=list(map(int,input().split()))
if P_ori.count(X)==0:
    print(X)
    exit()


P1=sorted(P_ori)
N=list(range(0,102))
PZ=[]
for i in range(len(N)):
    if P1.count(N[i])==0:
        PZ.append(N[i])

PZ.append(X)
P2=sorted(PZ)
t=P2.index(X)
if P2[t]==P2[0]:
    print(P2[1])
    exit()
elif P2[t]==P2[-1]:
    print(P2[-2])
    exit()
else:
    dist1=abs(P2[t-1]-P2[t])
    dist2=abs(P2[t]-P2[t+1])
    if dist1<=dist2:
        print(P2[t-1])
        exit()
    else:
        print(P2[t+1])
        exit()
print(0)
H,W = map(int,input().split())
List=[input() for i in range(H)]
A =[[1]*(W) for i in range(H)]
B =[[1]*(H) for i in range(W)]
for i in range(H):
    k = 0
    a = 0
    while k < W:
        if List[i][k]==".":
            a += 1
            k = k+1
        else:
            for j in range(a):
                A[i][k-j-1]=a
            A[i][k]=a
            a = 0
            k = k+1
    for j in range(a):
                A[i][k-j-1]=a
for i in range(W):
    k = 0
    a = 0
    while k < H:
        if List[k][i]==".":
            a += 1
            k = k+1
        else:
            for j in range(a):
                B[i][k-j-1]=a
            B[i][k] = 0
            a = 0
            k = k+1
    for j in range(a):
                B[i][k-j-1]= a
max = 0
for i in range(H):
    for j in range(W):
        if max < A[i][j] + B[j][i]:
            max = A[i][j] + B[j][i]
print(max-1)
        


### FIXED CODE ###

a,b,c=map(int,input().split())
s = max(a,b,c)
print(a+b+c-s)
o = list(input())
e = list(input())

ans = []
for i in range(len(o)):
  ans.append(o[i])
  if e[i]:
    ans.append(e[i])
    
print("".join(ans))

### FIXED CODE ###

o = list(input())
e = list(input())

ans = []
for i in range(len(o)):
  ans.append(o[i])
  if i < len(o)-1:
    ans.append(e[i])
  else:
    if len(e) == len(o):
      ans.append(e[i])
    
print("".join(ans))
l=list(map(int,input().split()))
for i in range(3):
  if l[i]==1:
    l[i]=9
  else:
    l[i]=1
print(l)

### FIXED CODE ###

l=list(input())
for i in range(3):
  if l[i]=='1':
    l[i]='9'
  else:
    l[i]='1'
l="".join(l)
print(l)
H, W, D=map(int, input().split())
pos={}
for i in range(H):
    A=list(map(int, input().split()))
    for j in range(W):
        pos[A[j]]=(i, j)
Q=int(input())
p=[0]*(H*W)
for i in range(D+1,H*W):
    p[i]=p[i-D]+abs(pos[i][0]-pos[i-D][0])+abs(pos[i][1]-pos[i-D][1])
for i in range(Q):
    L, R=map(int, input().split())
    print(p[R]-p[L])


### FIXED CODE ###

H, W, D=map(int, input().split())
pos={}
for i in range(H):
    A=list(map(int, input().split()))
    for j in range(W):
        pos[A[j]]=(i, j)
p=[0]*(H*W+1)
for i in range(D+1,H*W+1):
    p[i]=p[i-D]+abs(pos[i][0]-pos[i-D][0])+abs(pos[i][1]-pos[i-D][1])
Q=int(input())
for _ in range(Q):
    L, R=map(int, input().split())
    print(p[R]-p[L])
h = int(input())
ans = 0
c = 0
while h >0:
    ans += 2**c
    h //= 2
    c+= 1
print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
h= list(map(int,input().split()))
h.sort(reverse=True)
print(sum(h[k:]))
A, B, C = map(int, input().split())
if A[-1] == B[0] and B[-1] == C[0]:
  print("YES")
else :
  print("NO")

### FIXED CODE ###

A, B, C = input().split()
if A[-1] == B[0] and B[-1] == C[0]:
  print("YES")
else :
  print("NO")
import fractions

mod = 1e9 + 7;

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

l = A[0]
for i in range(1, N):
  l = l * A[i] // fractions.gcd(l, A[i])

sum = 0
for i in A:
  sum += l / i
  sum %= mod

print(int(sum))

### FIXED CODE ###

import fractions

mod = 10**9 + 7;

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

l = 1
for i in A:
  l = l * i // fractions.gcd(l, i)

sum = 0
for i in A:
  sum += l // i

print(sum % mod)
n,l=map(int,input().split())
words=[]
for i in range(n):
  words.append(input())
for i in range(n-1,0,-1):
  words.sort(key=lambda x:ord(x[i]))
ans=""
for i in range(n):
  ans+=words[i]
print(ans)

### FIXED CODE ###

n,l=map(int,input().split())
words=[]
for i in range(n):
  words.append(input())
for i in range(l-1,-1,-1):
  words.sort(key=lambda x:ord(x[i]))
ans=""
for i in range(n):
  ans+=words[i]
print(ans)
a, b = map(int, input())

print(a * b - a - b + 1)

### FIXED CODE ###

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

print(a * b - a - b + 1)
n = int(input())
r = []
for i in range(n):
    s,p = input().split()
    p = int(p)
    r.append([s,p,i])
a = sorted(r)
for i in range(n):
    print(a[i][3]+1)

### FIXED CODE ###

n = int(input())
r = []
for i in range(n):
    s,p = input().split()
    p = -int(p)
    r.append([s,p,i])
a = sorted(r)
for i in range(n):
    print(a[i][2]+1)
import sys
import numpy as np
input = sys.stdin.readline


def main():
    N = int(input())
    A = np.array([int(input()) for _ in range(N)])

    for j in range(N):
        if j != A.index(max(A)):
            print(np.max(A))
        else:
            ans = [x for i, x in enumerate(A) if i != j]
            print(np.max(ans))


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())
    As = [int(input()) for _ in range(n)]

    As_sort = sorted(As)
    second, first = As_sort[-2:]
    for i in range(n):
        if As[i] == first:
            print(second)
        else:
            print(first)


if __name__ == "__main__":
    main()
n = int(raw_input())
p = [0 for i in range(0, 101)]
m = [0 for i in range(0, 101)] for j in range(0, 101)

for i in range(1, n+1):
    p[n-1],p[n] = map(int, raw_input.split())

for k in range(2, n+1):
    for i in range(1, n-k+2):
       j = i+k-1
       m[i][j] = float("inf")
       for l in range(i,j):
          m[i][j] =  min(m[i][j], m[i][l]+m[l+1][j]+p[i-1]*p[l]*p[j])

print m[1][n]

### FIXED CODE ###

n = int(raw_input())
p = [0 for i in range(0, 101)]
m = [[0 for i in range(0, 101)] for j in range(0, 101)]

for i in range(1, n+1):
   p[i-1], p[i] = map(int, raw_input().split())
     
for k in range(2, n+1):
   for i in range(1, n-k+2):
      j = i+k-1
      m[i][j] = float("inf")
      for l in range(i, j):
         m[i][j] = min(m[i][j], m[i][l] + m[l+1][j] + p[i-1]*p[l]*p[j])
 
print m[1][n]
def gost(lis,ky,r,l):
    
    lens=l-r+1
    
    if lens <= 5:
        print("key = "+str(ky))
        print(lis)
        if ky in lis[r:l]:
            return True
        else:
            return False
    
    if ky <= lis[(lens//2)-1]:
        return gost(lis,ky,r,r+(lens//2))
    else:
        return gost(lis,ky,l-(lens//2),l)
    

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

q = int(input())
a = input()
t=list(map(int,a.split()))


i = 0
for it in t:
    if gost(s,it):
        i = i+1
print(i)

### FIXED CODE ###

def gost(lis,ky,r,l):
    
    lens=l-r+1
    
    if lens <= 5:
        if ky in lis[r:l+1]:
            return True
        else:
            return False
    
    if ky <= lis[r+(lens//2)-1]:
        return gost(lis,ky,r,r+(lens//2)-1)
    else:
        return gost(lis,ky,r+(lens//2),l)
    

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

q = int(input())
a = input()
t=list(map(int,a.split()))


i = 0
for it in t:
    if gost(s,it,0,n-1):
        i = i+1
print(i)
import math
A, B = input().split(" ")
A = int(A.strip())
B = int(B.strip().replace(".", ""))
print(math.floor(A * B / 100)

### FIXED CODE ###

A, B = input().split(" ")
A = int(A.strip())
B = int(B.strip().replace(".", ""))
print(A * B // 100)
import itertools
x,y,z,t = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
a.sort()
b.sort()
c.sort()
ans = []
for i in range(x):
    for k in range(y):
        ans.append(a[i]+b[k])
ans.sort()
ans.reverse()
if x*y > t:
    ans = ans[0:t]
out = []
for i in range(len(ans)):
    for k in range(z):
        out.append(ans[i]+c[k])
out.sort()
out.reverse()
for i in range(t):
    print(out[i])

### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())
if e-a <= k:
    print("Yay!")
else:
    print(":(")
L ,R = map(int,input().split())

ans =[]
if R - L <= 2019:
    for i in range(L,R+1):
        for j in range(i+1,R+1):
            ans.append(i*j%2019)
            if i*j% == 0 :
                exit()

print(min(ans))


### FIXED CODE ###

L ,R = map(int,input().split())

ans =[]
if R - L <= 2019:
    for i in range(L,R+1):
        for j in range(i+1,R+1):
            ans.append(i*j%2019)

else:
    for i in range(R-L-1010,R-L+1010):
        for j in range(i,R-L+1010):
            ans.append(i*j%2019)

print(min(ans))
import math
A, B, C, D = map(int, input().split())


#     {x | A <= x <= B and x % C != 0 and x % D != 0}
# =             {x | 1 <= x <= B and x % C != 0 and x % D != 0}
#           -   {x | 1 <= x <= A-1 and x % C != 0 and x % D != 0}
# =   {x | 1 <= x <= B} - {x | 1 <= x <= B and x % C = 0} - {x | 1 <= x <= B and x % D = 0} + - {x | 1 <= x <= B and x % C = 0 and x % D = 0}
#     (略)

def func(x,y):
    # print(x,y,math.floor((x/y)))
    return math.floor((x/y))

# print(func(100,10))

lcm = C * D /math.gcd(C, D)
print( (B - (func(B, C) + func(B, D) - func(B, lcm))) -
       (A-1 - (func(A-1, C) + func(A-1, D) - func(A-1, lcm))) )

### FIXED CODE ###

import fractions
A, B, C, D = map(int, input().split())


def func(x,y):
    if(x<0):
        assert()
    if(y<=0):
        assert()
    # print(x,y,int(x/y))
    # return int((x/y))
    # print(x,y,x//y)
    return int((x//y))

# print(func(100,10))


lcm = int((C * D) / int(fractions.gcd(C, D)))
print(int( B - func(B, C) - func(B, D) + func(B, lcm) - A + 1 + func(A-1, C) + func(A-1, D) - func(A-1, lcm)))
from math import factorial
from itertools import accumulate

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

C=0
t=[math.factorial(N-i) for i in range(2,N)]

t=list(itertools.accumulate(t))
t.append(math.factorial(N-1))
t.reverse()
T=list(itertools.accumulate(t))

C=[(x[j]-x[j-1])*T[j-1] for j in range(1,N) ]

print(sum(C)%((10 ** 9)+7))

### FIXED CODE ###

from math import factorial
 
N = int(input())
x = list(map(int, input().split()))
mod = 10**9 + 7
x_dis = [x[i+1] - x[i] for i in range(N-1)]
ans = 0
m = N-1
fac = factorial(m) % mod
tmp = fac
for i in range(m):
    ans += x_dis[i] * tmp
    ans %= mod
    tmp += (fac*pow((i+2),(mod-2), mod))%mod
print(ans)
#!/usr/bin/env python
# coding: utf-8

# In[2]:


H, W = map(int, input().split())
data = [["a"]*(W+2)]
for i in range(H):
    data.append(list("a" + input() + "a"))
data.append([["a"]*(W+2)])
# print(data)


# In[5]:


for h in range(H+1):
#     print(data[h])
    for w in range(W+1):
#         print(data[h][w])
        if data[h][w] == "#":
            if data[h-1][w] != "#" and data[h+1][w] != "#" and data[h][w-1] != "#" and data[h][w+1] != "#":
                print("No")
                exit()

print("Yes")


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[2]:


# H, W = map(int, input().split())
# data = [["a"]*(W+2)]
# for i in range(H):
#     data.append(list("a" + input() + "a"))
# data.append([["a"]*(W+2)])
# # print(data)


# In[5]:


# for h in range(H+1):
# #     print(data[h])
#     for w in range(W+1):
# #         print(data[h][w])
#         if data[h][w] == "#":
#             if data[h-1][w] != "#" and data[h][w-1] != "#" and data[h][w+1] != "#" and data[h+1][w] != "#":
#                 print("No")
#                 exit()

# print("Yes")


# In[ ]:


h, w = map(int, input().split())
s = [["a"]*(w + 2)]
 
for i in range(h):
    s.append(list("a" + input() + "a"))
s.append(["a"]*(w + 2))
 
for i in range(h + 1):
    for j in range(w + 1):
        if s[i][j] == "#":
            if s[i - 1][j] != "#" and s[i][j - 1] != "#" and s[i][j + 1] != "#" and s[i + 1][j] != "#":
                print("No")
                exit()
 
print("Yes")
# -*- coding: utf-8 -*-
# get a integer
a = raw_input()
# output
print(len(a) == 6 and a[2] == a[3] and a[4] == a[5])

### FIXED CODE ###

# -*- coding: utf-8 -*-
# get a integer
a = input()
# output
if len(a) == 6 and a[2] == a[3] and a[4] == a[5]:
    print('Yes')
else:
    print('No')
import math
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

n,x = iim()
xmod = list(map(lambda y:int(y)-x,input().split()))
#print(xmod)
num = xmod[0]
for i in xmod:
    gcd = math.gcd(num,i)

print(gcd)

### FIXED CODE ###

#import math
import fractions
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

n,x = iim()
xmod = list(map(lambda y:abs(int(y)-x),input().split()))
#print(xmod)
gcd = xmod[0]
for i in xmod:
    gcd = fractions.gcd(gcd,i)

print(gcd)
n = int(input())
s = input()[::-1]
cnt = s.count('1')

p1 = sum(pow(2, i, cnt+1) * (s[i] == '1') for i in range(n))
m1 = sum(pow(2, i, cnt-1) * (s[i] == '1') for i in range(n))

def op(n):
    popcnt = bin(n).count('1')
    return n%popcnt

pre = [0]*100000
for i in range(1,100000):
    pre[i] = pre[op(i)] + 1

def solve(i):
    if s[-i] == '0':
        r = (p1 + pow(2, n-i, cnt+1))%(cnt+1)
    else:
        if cnt == 1:
            return 1
        r = (m1 - pow(2, n-i, cnt-1))%(cnt-1)
    return 1 + pre[r]

for i in range(n):
    print(solve(i+1))


### FIXED CODE ###

n = int(input())
s = input()[::-1]
cnt = s.count('1')

p1 = sum(pow(2, i, cnt+1) * (s[i] == '1') for i in range(n))
if cnt > 1:
    m1 = sum(pow(2, i, cnt-1) * (s[i] == '1') for i in range(n))

def op(n):
    popcnt = bin(n).count('1')
    return n%popcnt

pre = [0]*1000000
for i in range(1,1000000):
    pre[i] = pre[op(i)] + 1

def solve(i):
    if s[-i] == '0':
        r = (p1 + pow(2, n-i, cnt+1))%(cnt+1)
    else:
        if cnt == 1:
            return 0
        r = (m1 - pow(2, n-i, cnt-1))%(cnt-1)
    return 1 + pre[r]

for i in range(n):
    print(solve(i+1))