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

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():
    N = in_n()
    X = int(in_s(), 2)

    for i in range(N):
        # X[i] = str(int(not int(X[i])))
        a = X ^ (1 << N - i - 1)
        a = bin(a)[2:]
        # print(a)
        count = 0
        while int(a, 2):
            a = bin(int(a, 2) % a.count('1'))[2:]
            count += 1
        print(count)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def main():
    N = int(readline())
    X = readline().rstrip().decode('utf-8')
    nx = int(X, 2)

    ans = [0] * N

    oc = X.count('1')

    if oc - 1 != 0:
        mx = nx % (oc - 1)
        f = True
    else:
        f = False

    px = nx % (oc + 1)

    for i in range(N):

        if X[i] == '0':
            a = (px + pow(2, N - i - 1, oc + 1)) % (oc + 1)
        elif f:
            a = (mx - pow(2, N - i - 1, oc - 1)) % (oc - 1)
        else:
            ans[i] = 0
            continue

        count = 1
        while a:
            a = a % bin(a).count('1')
            count += 1

        ans[i] = count

    print('\n'.join(map(str, ans)))


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

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

for i in range(n):
    l=i
    r=i
    s=0
    while r<n:
        if s ^ a[r]== s+a[r]:
            s+=a[r]
            r+=1
            ans+=1
        else:
            break
print(ans)

### FIXED CODE ###

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

l=r=s=0
while l<n:
    if s^a[r]==s+a[r]:
        s+=a[r]
        if r!=n-1:
            r+=1
        else:
            break
    else:
        ans+=r-l
        s-=a[l]
        l+=1

ans+=(r-l+1)*(r-l+2)//2

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

import sys
import os
import itertools
import numpy as np
from collections import deque

def main():
    if os.getenv("ENV")=='LOCAL':
        sys.stdin = open(os.path.dirname(__file__)+'/input.txt', 'r')

    N=int(input())

    divisors=sieve(N)

    # print(divisors)
    sum=0
    for i,n in enumerate(divisors):
        sum+=i*n

    print(sum)

def sieve(n):
    is_prime = [1 for _ in range(n+1)]

    for i in range(2, n+1):
        # print(is_prime)
        is_prime[i] += 1
        j = 2 * i
        while j <= n:
            is_prime[j] += 1
            j += i

    return is_prime


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import os
import itertools
import numpy as np
from collections import deque

def main():
    if os.getenv("ENV")=='LOCAL':
        sys.stdin = open(os.path.dirname(__file__)+'/input.txt', 'r')

    N=int(input())

    # divisors=sieve(N)
    #
    # # print(divisors)
    # sum=0
    # for i,n in enumerate(divisors):
    #     sum+=i*n

    # print(5*(2+5-1)//2)
    print(sieve(N))

def sieve(n):
    # is_prime = [i for i in range(n+1)]
    sum=n*(2+n-1)//2
    # sum=0

    for i in range(2, n+1):
        # print(is_prime)
        d=n//i
        # print(d)
        sum+=d*((d+1)*i)//2
        # sum += i
        # j = 2 * i
        # while j <= n:
        #     sum += j
        #     j += i

    return sum


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

n, m = list(map(int, input().split()))
a = [input() for i in range(m)]
total_act = 0
total_act2 = 1
total = 1
for i in range(n + 1):
    if str(i) in a:
        total = (total_act * total) % 1000000007
        total_act = 0
        total_act2 = 1
    else:
        total_act3 = total_act2 + total_act
        total_act2 = total_act
        total_act = total_act3
total = (total_act * total) % 1000000007
print(total)


### FIXED CODE ###

n, m = list(map(int, input().split()))
a = [input() for i in range(m)]
b = []
c = []
total_act = 0
total_act2 = 1
total = 1
if m == 0:
    for i in range(n + 1):
        if str(i) in a:
            total *= total_act
            total_act = 0
            total_act2 = 1
        else:
            total_act3 = total_act2 + total_act
            total_act2 = total_act
            total_act = total_act3
    total *= total_act
    print(total % 1000000007)
else:
    b.append(int(a[0]))
    for i in range(len(a) - 1):
        b.append(int(a[i + 1]) - int(a[i]) - 1)
        if int(a[i + 1]) - int(a[i]) - 1 == 0:
            print(0)
            exit()
    b.append(n - int(a[-1]))

    for i in range(max(b)):
        total_act3 = total_act2 + total_act
        total_act2 = total_act
        total_act = total_act3
        c.append(total_act)

    for i in b:
        total *= c[i - 1]
    print(total % 1000000007)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
from bisect import bisect_left

# 区間の和を高速に求めたいので累積和
S = [0]*N
S[0] = A[0]
for i in range(1,N):
    S[i] = S[i-1]+A[i]

Ans = 10**15
D = [0,1]
# 真ん中の分割位置を全探索
for i in range(2,N-1):
    # 前半と後半に分離
    A,B = S[:i],S[i:]
    sumA,sumB = S[i-1],S[N-1]-S[i-1]
    canA,canB = [],[]
    # 前半部分,後半部分をそれぞれできるだけ均等になるように分割
    ai = bisect_left(A,sumA/2)
    bi = bisect_left(B,sumB/2+A[-1])
    # 2分探索で分割位置を求め、その次の要素を含める・含めないの2通り考慮する
    for d in D:
        a1 = A[ai-d]
        a2 = A[i-1]
        canA.append((a1,a2))
    for d in D:
        b1 = B[bi-d]
        b2 = B[-1]
        canB.append((b1,b2))
    # 考慮した組み合わせで最小のものを記録
    for a in canA:
        for b in canB:
            x1,x2,x3,x4 = a[0],a[1],b[0],b[1]
            Ans = min(Ans,max(x1,x2-x1,x3-x2,x4-x3)-min(x1,x2-x1,x3-x2,x4-x3))

print(Ans)

### FIXED CODE ###

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

# 区間の和を高速に求めたいので累積和
S = [0]*N
S[0] = A[0]
for i in range(1,N):
    S[i] = S[i-1]+A[i]

Ans = 10**15
# 真ん中の分割位置を全探索
for i in range(2,N-1):
    # 前半部分,後半部分をそれぞれできるだけ均等になるように分割
    ax = S[i-1]/2
    ai = bisect(S,ax)
    if abs(S[ai-1]-ax) < abs(S[ai]-ax):
        ai -= 1
    bx = (S[N-1]+S[i-1])/2
    bi = bisect(S,bx)
    if abs(S[bi-1]-bx) < abs(S[bi]-bx):
        bi -= 1
    x1,x2,x3,x4 = S[ai],S[i-1]-S[ai],S[bi]-S[i-1],S[N-1]-S[bi]
    # 考慮した組み合わせで最小のものを記録
    Ans = min(Ans,max(x1,x2,x3,x4)-min(x1,x2,x3,x4))

print(Ans)
### BUGGY CODE ###

import numpy as np
N, M = map(int, input().split())
A = []
B = []
for _ in range(N):
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)
cnt = 0
ans = 0
while cnt < M:
  ind = np.argmin(A)
  m = min(M - cnt, B.pop(ind))
  ans += A.pop(ind) * m
  cnt += m
print(ans)  

### FIXED CODE ###

import numpy as np
N, M = map(int, input().split())
A = []
B = []
for _ in range(N):
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)
cnt = 0
ans = 0
ind = np.argsort(A)
for i in range(N):
  m = min(M - cnt, B[ind[i]])
  ans += A[ind[i]] * m
  cnt += m
  if cnt >= M:
    break
print(ans)
### BUGGY CODE ###

a,b,k=map(int,input().split());r=range(a,b+1)
for i in r:
  if i not in set(r[k:-k]):
    print(i)

### FIXED CODE ###

a,b,k=map(int,input().split())
s=list((range(a,b+1)[:k]))
t=list(range(a,b+1)[-k:])
for r in sorted(set([s,s+t][b>k])):print(r)
### BUGGY CODE ###

length=int(input())
list=list(map(int,input().split()))
list.sort()
max=list[-1]
dp=[True]*(max+1)
ret=0
for num in list:
    if dp[num]:
        for i in range(max//num+1):
            dp[num*i]=False
        if list.count(num)==1:
            ret=ret+1
print(ret)

### FIXED CODE ###

import numpy as np
from collections import Counter

length=int(input())
list=list(map(int,input().split()))
list.sort()

max=list[-1]
dp=[0]*(max+1)
dp=np.array(dp,int)

for num in list:
    dp[num]=1

for num in list:
    if dp[num]==1:
        dp[2*num::num]=0

count=Counter(list)

for num,cnt in count.items():
    if cnt>1:
        dp[num]=0

print(dp.sum())
### BUGGY CODE ###

#累積和のリストを作らない
N=int(input())
A=sorted(map(int,input().split()))
c=0
for n in range(N-1):
  if sum(A[:n+1])*2 >= A[n+1]:
    c+=1
  else:
    c=0
print(c+1)

### FIXED CODE ###

#累積和で毎回sumしない
N=int(input())
A=sorted(map(int,input().split()))
b=0
c=0
for n in range(N-1):
  b += A[n]
  if b*2 >= A[n+1]:
    c+=1
  else:
    c=0
print(c+1)
### BUGGY CODE ###

import sys

def max_heapify(A, i):
  l = i * 2
  r = l + 1
  largest = i
  H = len(A) -1
  if l <= H and A[l] > A[i]:
      largest = l
  if r <= H and A[r] > A[largest]:
      largest = r
  if largest != i:
    A[i], A[largest] = A[largest], A[i]
    max_heapify(A, largest)

#@profile
def build_max_heap(A):
    for i in range(len(A)-1 // 2, 0, -1):
        max_heapify(A, i)

#@profile
def extract(A):
    out = A[1]
    A[1] = A[-1]
    del A[-1]
    max_heapify(A, 1)
    return out

_input = sys.stdin.readlines()
A = [0]
out=[]

#@profile
def main():
    for l in _input:
        if l[0] == "i":
            #insert k
            A.append(int(l.split()[1]))
            build_max_heap(A)
        #print(A)
        elif l[1] == "n":
            #end
            print(*out, sep = "\n")
            return
        else:
            #build_max_heap(A)
            #print(A)
            out.append(extract(A))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

#@profile
def max_heapify(A, i):
    j = i
    largest = i
    H = len(A) -1
    while True:
        l = j * 2
        r = l + 1
        if l <= H and A[l] > A[j]:
            largest = l
        if r <= H and A[r] > A[largest]:
            largest = r
        if largest != j:
            A[j], A[largest] = A[largest], A[j]
            #max_heapify(A, largest)
            j = largest
            
        else:
            break
        

#@profile
def build_max_heap(A):
    i = len(A)-1
    last = A[i]
    parent = i//2
    while  parent > 0 and A[parent] < last:
        A[i] = A[parent]
        i = parent
        parent = i //2
    A[i] = last

#@profile
def extract(A):
    print(A[1])
    A[1] = A[-1]
    del A[-1]
    max_heapify(A, 1)
    
A = [0]

#@profile
def main():
    out = ""
    for l in sys.stdin.readlines():
        if l[0] == "i":
            #insert k
            A.append(int(l[7:]))
            build_max_heap(A)
        #print(A)
        elif l[1] == "n":
            #end
            print(out, end = "")
            return
        else:
            if len(A) <= 1:
                pass
            elif len(A) == 2:
                out += str(A.pop()) + "\n"
                #print(A.pop())
            #extract(A)
            else:
                out += str(A[1]) + "\n"
                A[1] = A.pop()
                max_heapify(A, 1)
                
if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

rXL = []
for i, j in XL:
    rXL.append([i - j, i + j])
rXL = sorted(rXL, key = lambda x: x[1])
TF = [True for _ in range(N)]

for i in range(1, N):
    for j in range(i):
        if rXL[i][0] < rXL[j][1] and rXL[i][1] > rXL[j][0] and TF[j]:
            TF[i] = False

print(sum(TF))

### FIXED CODE ###

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

rXL = []
for i, j in XL:
    rXL.append([i - j, i + j])
rXL = sorted(rXL, key = lambda x: x[1])
TF = [True for _ in range(N)]

maxr = rXL[0][1]
for i in range(1, N):
    if maxr <= rXL[i][0]:
        maxr = rXL[i][1]
    else:
        TF[i] = False

print(sum(TF))
### BUGGY CODE ###

H = int(input())
count = 0
P = [H]
while H > 0:
  H //= 2
  P.pop(0)
  P.append(H)
  P.append(H)
  H = P[0]
  count += 1
print(count)

### FIXED CODE ###

H = int(input())
enemy = 1
count = 0
while H >= 1:
  count += enemy
  enemy *= 2
  H //= 2
print(count)
### BUGGY CODE ###

H,W = map(int, input().split())
grid = [0]*(H*W)
black = []
for i in range(H):
  A_i = input()
  for j in range(W):
    grid[W*i + j] = 0 if A_i[j] == '#' else -1
    if A_i[j] == '#':
      black.append(W*i + j)

ans = 0
while True:
  black_new = []
  for i in black:
    if i - W >= 0:
      if grid[i - W] == -1:
        grid[i - W] = ans + 1
        black_new.append(i-W)
    if i - 1 >= 0 and i%W != 0:
      if grid[i - 1] == -1:
        grid[i - 1] = ans + 1
        black_new.append(i-1)
    if i + 1 <= H*W-1 and i%W != W-1:
      if grid[i + 1] == -1:
        grid[i + 1] = ans + 1
        black_new.append(i+1)
    if i + W <= H*W-1:
      if grid[i + W] == -1:
        grid[i + W] = ans + 1
        black_new.append(i+W)
  black = black_new
  if len(black) == 0:
    print(ans)
    break
  ans += 1

### FIXED CODE ###

import collections

H,W = map(int, input().split())
grid = [0]*(H*W)
black = collections.deque()
for i in range(H):
  A_i = input()
  for j in range(W):
    grid[W*i + j] = 0 if A_i[j] == '#' else -1
    if A_i[j] == '#':
      black.append(W*i + j)

ans = 0
while True:
  black_new = collections.deque()
  while len(black) > 0:
    i = black.pop()
    if i - W >= 0:
      if grid[i - W] == -1:
        grid[i - W] = ans + 1
        black_new.append(i-W)
    if i - 1 >= 0 and i%W != 0:
      if grid[i - 1] == -1:
        grid[i - 1] = ans + 1
        black_new.append(i-1)
    if i + 1 <= H*W-1 and i%W != W-1:
      if grid[i + 1] == -1:
        grid[i + 1] = ans + 1
        black_new.append(i+1)
    if i + W <= H*W-1:
      if grid[i + W] == -1:
        grid[i + W] = ans + 1
        black_new.append(i+W)
  black = black_new
  if len(black) == 0:
    print(ans)
    break
  ans += 1
### BUGGY CODE ###

import heapq

n,m=map(int,input().split())
works={}
for i in range(n):
    day,pay=map(int,input().split())
    works.setdefault(day,[]).append(pay)
sorted_works=sorted(works.items(), key=lambda x:x[0])

heapls=[]
heapq.heapify(heapls)
ans=0
for i in range(m):
    day=i+1
    if sorted_works!=[] and sorted_works[0][0]==day:
        jobs_for_day=sorted_works.pop(0)
        for j in jobs_for_day[1]:
            heapq.heappush(heapls,(-j,j),)
    if heapls!=[]:
        tmp=heapq.heappop(heapls)
        ans+=tmp[1]
print(ans)

### FIXED CODE ###

import heapq

n,m=map(int,input().split())
works=[[] for i in range(m+1)]
for i in range(n):
    day,pay=map(int,input().split())
    try:
        works[day].append(pay)
    except IndexError:
        pass
#print(works)

heapls=[]
day=1
ans=0

for i in range(m):
    day=i+1
    for j in works[day]:
        heapq.heappush(heapls,-j)
    if heapls!=[]:
        tmp=heapq.heappop(heapls)
        ans=ans+tmp
print(-ans)
### BUGGY CODE ###

N, K = map(int, input().split())
h = [int(input()) for _ in [0]*N]

h = sorted(h)
ans = []

for i in range(len(h)-K+1):
  a = h[i:i+K]
  ans.append(max(a)-min(a))
  if ans[-1] == 0:
    print(0)
    exit()

print(min(ans))

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(input()) for _ in [0]*N]

h = sorted(h)
ans = []

for i in range(len(h)-K+1):
  ans.append(h[i+K-1]-h[i])
  if ans[-1] == 0:
    print(0)
    exit()

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

X = input()
lenX = len(X)
cnt = 0
for i in range(lenX // 2):
    if 'ST' in X:
        idx = X.index('ST')
        X = X[: idx] + X[idx + 2 :]
        cnt += 2
print(lenX - cnt)

### FIXED CODE ###

from collections import deque
X = input()
Q = deque()
for i in range(len(X)):
    if X[i] == 'T':
        if len(Q) > 0 and Q[-1] == 'S':
            Q.pop()
        else:
            Q.append('T')
    else:
        Q.append('S')
print(len(Q))
### BUGGY CODE ###

n,q = map(int,input().split())
s = list(input())
l = []
p = []
for i in range(n-1):
        if s[i] == "A" and s[i+1] == "C":
                l.append(i+1)
for j in range(q):
        k,t = map(int,input().split())
        b = len([1 for x in l if x >= k and x < t])
        p.append(b)
for i in range(len(p)):
        print(p[i])

### FIXED CODE ###

n,q = map(int,input().split())
s = list(input())
l = [0]*(n)
for i in range(n-1):
        if s[i] == "A" and s[i+1] == "C":
                l[i+1] = l[i] + 1
        else:
                l[i+1] = l[i]  
for j in range(q):
        k,t = map(int,input().split())
        print(l[t-1] - l[k-1])
### BUGGY CODE ###

def main():
    A = list(map(int,input().split()))
    N = A[0]
    X = A[1]
    Y = A[2]
    list1 = [[0 for i in range(N)] for j in range(N)]
    ans = [0 for i in range(N-1)]

    for i in range(N):
        for j in range(i+1,N):
            list1[i][j] = min(j-i,abs(X-1-i)+1+abs(j-Y+1), abs(Y-1-i)+1+abs(j-X+1))
            ans[list1[i][j]-1] += 1

    for i in ans:
        print(i)


main()

### FIXED CODE ###

def main():
    A = list(map(int,input().split()))
    N = A[0]
    X = A[1]
    Y = A[2]
    list1 = [[0 for i in range(N)] for j in range(N)]
    ans = [0 for i in range(N-1)]

    for i in range(N):
        for j in range(i+1,N):
            list1[i][j] = min(j-i,abs(X-1-i)+1+abs(j-Y+1), abs(Y-1-i)+1+abs(j-X+1))
            ans[list1[i][j]-1] += 1

    for i in ans:
        print(i)


main()
### BUGGY CODE ###

def abc070_d():
    import sys
    read = sys.stdin.buffer.read
    inp = iter(map(int, read().split()))

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

    n = next(inp)
    adjmtx = lil_matrix((n, n), dtype=np.int32)
    for _ in range(n-1):
        a = next(inp) - 1
        b = next(inp) - 1
        c = next(inp)
        adjmtx[a, b] = c
        adjmtx[b, a] = c

    q = next(inp)
    k = next(inp) - 1

    dist = dijkstra(csgraph=adjmtx, indices=k)
    eps = 1e-6

    for _ in range(q):
        x = next(inp) - 1
        y = next(inp) - 1
        ans = int(dist[x] + dist[y] + eps)
        print(ans)

if __name__ == '__main__':
    abc070_d()

### FIXED CODE ###

def abc070_d():
    import sys
    sys.setrecursionlimit(10010010)
    read = sys.stdin.buffer.read
    inp = iter(map(int, read().split()))

    n = next(inp)
    adjlist = [[] for _ in range(n)]
    for _ in range(n-1):
        a = next(inp) - 1
        b = next(inp) - 1
        c = next(inp)
        adjlist[a].append((b, c))
        adjlist[b].append((a, c))

    q = next(inp)
    k = next(inp) - 1

    dist = [-1] * n

    def dfs(x:int, d:int):
        dist[x] = d
        for nx, nd in adjlist[x]:
            if dist[nx] != -1: continue
            dfs(nx, d + nd)

    dfs(k, 0)

    for _ in range(q):
        x = next(inp) - 1
        y = next(inp) - 1
        ans = dist[x] + dist[y]
        print(ans)

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

H,W = map(int, input().split())
fields =  [list(input()) for i in range(H)]
# print(fields)

from collections import deque
cnts = [[1000] * W for i in range(H)]
q = deque()
q.append((0,0))
cnts[0][0] = 0
str_s = "."
mv = [(1,0),(0,1)]
while len(q) > 0:
    h,w = q.popleft()
    # mark = fields[h][w]
    for dh, dw in mv:
        if h + dh < H and w + dw < W:
            # print("upd",h,w,h+dh,w+dw,H,W)
            if fields[h][w] == fields[h+dh][w+dw]:
                upd = cnts[h][w] 
            else:
                if fields[h][w] == ".":
                    upd = cnts[h][w] + 1
                else:
                    upd = cnts[h][w]
            cnts[h+dh][w+dw] = min(cnts[h+dh][w+dw],upd)
            q.append((h+dh,w+dw))

# print(cnts)

ans = cnts[H-1][W-1]
if fields[0][0] == "#":ans += 1
print(ans)



### FIXED CODE ###

H,W = map(int, input().split())
fields =  [list(input()) for i in range(H)]
# print(fields)

from collections import deque
cnts = [[1000] * W for i in range(H)]
q = deque()
q.append((0,0))
cnts[0][0] = 0
str_s = "."
mv = [(1,0),(0,1)]
while len(q) > 0:
    h,w = q.popleft()
    # mark = fields[h][w]
    for dh, dw in mv:
        if h + dh < H and w + dw < W:
            # print("upd",h,w,h+dh,w+dw,H,W)
            if fields[h][w] == fields[h+dh][w+dw]:
                upd = cnts[h][w] 
            else:
                if fields[h][w] == ".":
                    upd = cnts[h][w] + 1
                else:
                    upd = cnts[h][w]
            if cnts[h+dh][w+dw] > upd:
                cnts[h+dh][w+dw] = min(cnts[h+dh][w+dw],upd)
                q.append((h+dh,w+dw))

# print(cnts)

ans = cnts[H-1][W-1]
if fields[0][0] == "#":ans += 1
print(ans)
### BUGGY CODE ###

def load_input():
    n, k = list(map(int, input().split()))
    s = list(input())
    return n, k, s


def main():
    n, k, s = load_input()

    starts = [0]
    ends = []
    for i in range(n):
        if 0 < i and s[i - 1] == '1' and s[i] == '0':
            ends.append(i)

        if 0 < i and s[i - 1] == '0' and s[i] == '1':
            starts.append(i)
    ends.append(n)

    ml = 0
    for start in starts:
        order = k
        if start == 0 and s[0] == '0':
            order -= 1
        for end in ends:
            if start < end:
                if order == 0:
                    if ml < end - start:
                        ml = end - start
                    break
                order -= 1
        if ml < end - start:
            ml = end - start
    print(ml)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def binarySearch(alist, item):
    first = 0
    last = len(alist) - 1

    while first <= last:
        midpoint = (first + last)//2
        if item < alist[midpoint] and alist[midpoint - 1] < item or midpoint == 0 and item < alist[midpoint]:
            return midpoint
        else:
            if item < alist[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint + 1
    return -1


def load_input():
    n, k = list(map(int, input().split()))
    s = list(input())
    return n, k, s


def main():
    n, k, s = load_input()

    starts = [0]
    ends = []
    for i in range(n):
        if 0 < i and s[i - 1] == '1' and s[i] == '0':
            ends.append(i)

        if 0 < i and s[i - 1] == '0' and s[i] == '1':
            starts.append(i)
    ends.append(n)

    ml = 0
    for start in starts:
        order = k
        if start == 0 and s[0] == '0':
            order -= 1
        i = binarySearch(ends, start)
        if i + order < len(ends):
            end = ends[i + order]
        else:
            end = ends[-1]
        if ml < end - start:
            ml = end - start
    print(ml)


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

import bisect
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
#aaa = list(map(int, input().split()))
aaa = [int(a) for a in input().split()]
aaa.sort()

for i in range(m):
  a = aaa.pop(-1) // 2
  insert_index = bisect.bisect_right(aaa, a)
  aaa.insert(insert_index, a)
  
print(sum(aaa))

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
aaa = [-1 * int(a) for a in input().split()]
heapq.heapify(aaa)

for i in range(m):
  a = -heapq.heappop(aaa) // 2
  heapq.heappush(aaa, -a)
  
print(-sum(aaa))
### BUGGY CODE ###

MOD=10**9+7
def facinv(N):
    fac,finv,inv=[0]*(N+1),[0]*(N+1),[0]*(N+1)
    fac[0]=1;fac[1]=1;finv[0]=1;finv[1]=1;inv[1]=1
    for i in range(2,N+1):
        fac[i]=fac[i-1]*i%MOD
        inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
        finv[i]=finv[i-1]*inv[i]%MOD
    return fac,finv,inv

def COM(n,r):
    if n<r or r<0:
        return 0
    else:
        return ((fac[n]*finv[r])%MOD*finv[n-r])%MOD
        
r1,c1,r2,c2=map(int,input().split())

fac,finv,inv=facinv(r2+c2+1)

ans=0

for i in range(r1,r2+1):
    ans=(ans+COM(c2+i+1,i+1)-COM(c1+i,i+1)+MOD)%MOD
print(ans)

### FIXED CODE ###

MOD=10**9+7
def facinv(N):
    fac,finv,inv=[0]*(N+1),[0]*(N+1),[0]*(N+1)
    fac[0]=1;fac[1]=1;finv[0]=1;finv[1]=1;inv[1]=1
    for i in range(2,N+1):
        fac[i]=fac[i-1]*i%MOD
        inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
        finv[i]=finv[i-1]*inv[i]%MOD
    return fac,finv,inv

def COM(n,r):
    if n<r or r<0:
        return 0
    else:
        return ((fac[n]*finv[r])%MOD*finv[n-r])%MOD
        
r1,c1,r2,c2=map(int,input().split())

fac,finv,inv=facinv(r2+c2+1)

ans=0

for i in range(r1,r2+1):
    ans=(ans+COM(c2+i+1,i+1)-COM(c1+i,i+1)+MOD)%MOD
print(ans)