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

s = str(input())
s1 = len(s)
a = len(s)
b = 0

while a != b:
    a = len(s)
    s = s.replace('01','')
    s = s.replace('10','')

    b = len(s)

print(s1-b)


### FIXED CODE ###

s = str(input())

a = s.count('0')
b = s.count('1')

print(len(s) - abs(a-b))
### BUGGY CODE ###

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

t = 1
for i in range(K):# A[0] ~ A[K-1]
  t *= A[i]
  
L = [ 0 for i in range(N)]

L[K-1] = t

for i in range(K, N):
  t = t // A[i-K] * A[i]
  L[i] = t
  
for i in range(K, N):
  if L[i-1] < L[i]:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

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

for i in range(K, N):
  if A[i-K] < A[i]:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

# 2019-11-11 14:35:02(JST)
import sys
from collections import deque
import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 
from copy import deepcopy

def main():
    n, m = (int(x) for x in sys.stdin.readline().split())
    PY = [[int(x) for x in sys.stdin.readline().split()] for _ in range(m)]

    py = deque(sorted(deepcopy(PY)))

    ids = dict((j,dict()) for j in set(py[i][0] for i in range(m)))
    for _ in range(m): # max time of loops
        if py:
            for i in range(len(py)):
                p, y, x = py[i][0], py[i][1], i + 1
                if x >= 2 and not ids[p]:
                    for j in range(i): # deque では del [:i] (slice)が使えない
                        py.popleft()
                    break
                id_i = '0' * (6 - (math.floor(math.log10(p)) + 1)) + str(p) + '0' * (6 - (math.floor(math.log10(x)) + 1)) + str(x)
                ids[p][y] = id_i
        else:
            break
    
    for i in range(m):
        p, y = PY[i][0], PY[i][1]
        print(ids[p][y])


if __name__ == "__main__":
    main()


### FIXED CODE ###

# 2019-11-11 14:35:02(JST)
import sys
# import collections
import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 
from copy import deepcopy

def main():
    n, m = (int(x) for x in sys.stdin.readline().split())
    PY = [[int(x) for x in sys.stdin.readline().split()] for _ in range(m)]
    py = sorted(deepcopy(PY))

    ids = dict()
    for i in range(m):
        p, y = py[i][0], py[i][1]
        if not p in ids:
            ids[p] = dict()
            x = 0
        x += 1
        id_i = '0' * (6 - (math.floor(math.log10(p)) + 1)) + str(p) + '0' * (6 - (math.floor(math.log10(x)) + 1)) + str(x)
        ids[p][y] = id_i
    
    for i in range(m):
        p, y = PY[i][0], PY[i][1]
        print(ids[p][y])


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

n, k = list(map(int, input().split()))
lrs = [0] * k
for i in range(k):
     lr = list(map(int, input().split()))
     lrs[i] = range(lr[0], lr[1]+1)

s = list()
for lr in lrs:
    for d in lr:
        s.append(d)

mod = 998244353
i = 1
dp = [0] * (n+1)
dp[i] = 1
for i in range(n+1):
    if dp[i] == 0:
        continue
    for d in s:
        if i+d <= n:
            dp[i+d] = (dp[i+d] + dp[i]) % mod

print(dp[n] % mod)


### FIXED CODE ###

# DP, 累積和
n, k = list(map(int, input().split()))
s = list()
for i in range(k):
     l, r = list(map(int, input().split()))
     s.append((l, r))

mod = 998244353
i = 1
dp = [0] * (n+1)
dp[1] = 1
dpsum = [0] * (n+1)
dpsum[1] = 1
for i in range(2, n+1):
    for l, r in s:
        li = i-r
        ri = i-l
        if ri < 1: continue
        li = max(li, 1)
        dp[i] = (dp[i] + dpsum[ri] - dpsum[li-1]) % mod
    dpsum[i] = (dpsum[i-1] + dp[i]) % mod
    
print(dp[n])
### BUGGY CODE ###

import heapq

n, k = map(int, input().split())
a_list = [int(i) for i in input().split()]
f_list = [int(i) for i in input().split()]
a_list.sort()
f_list.sort(reverse=True)

heap_list = []
for i in range(n):
    heap_list.append((-a_list[i] * f_list[i], f_list[i]))

heapq.heapify(heap_list)    
for i in range(k):
    max_v, f = heapq.heappop(heap_list)
    if max_v < 0:
        max_v = min(max_v + f, 0)
    heapq.heappush(heap_list, (max_v, f))
max_v, f = heapq.heappop(heap_list)
print(-max_v)

### FIXED CODE ###

n, k = map(int, input().split())
a_list = [int(i) for i in input().split()]
f_list = [int(i) for i in input().split()]
a_list.sort(reverse=True)
f_list.sort()

if k >= sum(a_list):
    print(0)
    exit()

point = []
for i in range(n):
    point.append(a_list[i] * f_list[i])

import math
def binary_search(point, k):
    left = 0
    right = 10 ** 12
    while left + 1< right:
        ans = 0
        center = (left + right) // 2
        for i in range(n):
            if point[i] > center:
                ans += a_list[i] - (center // f_list[i])
        if ans <= k:
            right = center
        else:
            left = center
    return right    
    
value = binary_search(point, k)
print(value)
### BUGGY CODE ###

import sys

def main():
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines

    S = readline().decode().strip()
    Q = int(readline())

    cnt = 0

    #空の文字列にqueryで追加する文字を加えていく
    ss = " "
    for _ in range(Q):
        query = list(input().split())
        if query[0] == "1":
            cnt += 1
        else:
            if (query[1] == "1" and cnt%2==0) or (query[1] == "2" and cnt%2==1):
                ss = "".join([query[2],ss])
            else:
                ss = "".join([ss,query[2]])

    #反転回数が奇数の場合、元の文字列とqueryにより作成した文字列を反転
    if cnt%2 == 1:
        S = S[::-1]
        ss = ss[::-1]

    #スペースに元の文字列を追加
    print(ss.replace(" ", S))

if __name__=="__main__":
    main()

### FIXED CODE ###

s = input()
q = int(input())
list1 = []
list2 = []
flag = 1
for i in range(q):
    in_line = input().split()
    if in_line[0] == "1":
        flag *= -1
    else:
        if in_line[1] == "1":
            if flag == 1:
                list1.append(in_line[2])
            else:
                list2.append(in_line[2])
        else:
            if flag == 1:
                list2.append(in_line[2])
            else:
                list1.append(in_line[2])
if flag == 1:
    print("".join(list1[::-1]) + s + "".join(list2))
else:
    print("".join(list2[::-1]) + s[::-1] + "".join(list1))
### BUGGY CODE ###

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

### FIXED CODE ###

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

X = int(input())
 
flag = 0
A = 0
B = 0
 
for i in range(0, 10000):
  for j in range(0, 10000):
    if i**5 - j**5 == X:
      A = i
      B = j
      break
    elif i**5 + j**5 == X:
      A = i
      B = j
      break
    elif -i**5 - j**5 == X:
      A = -i
      B = j
      break
print(str(A) + ' ' + str(B))

### FIXED CODE ###

X = int(input())
 
flag = 0
A = 0
B = 0
 
for i in range(-120, 120):
  for j in range(-120, 120):
    if i**5 - j**5 == X:
      A = i
      B = j
      break
    elif i**5 + j**5 == X:
      A = i
      B = -j
      break
    elif -i**5 - j**5 == X:
      A = -i
      B = j
      break
print(str(A) + ' ' + str(B))
### BUGGY CODE ###

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

a.sort()

import collections
c = collections.Counter(a)

d=[]
for ck,cv in c.items():
    if cv>=2:
       d.append(ck) 
dset=set(d)
    
aa=[]

while True:
    aa.append(a[0])
    a2=[]
    for i in range(1,len(a)):
        if a[i]%a[0]!=0:
            a2.append(a[i])
#    a=a2.copy()
    if len(a2)==0:
        break

    aa.append(a2[0])
    a=[]
    for i in range(1,len(a2)):
        if a2[i]%a2[0]!=0:
            a.append(a2[i])
#    a=a2.copy()
    if len(a)==0:
        break

aaset=set(aa)
aaset=aaset-dset    
print(len(aaset))

### FIXED CODE ###

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

a.sort()
amax=max(a)
dp=[True]*(amax+1)

import collections
c = collections.Counter(a)

d=[]
for ck,cv in c.items():
    if cv>=2:
       d.append(ck) 
dset=set(d)
    
aa=set()
for ai in a:
    if dp[ai]:
        aa.add(ai)
        for aj in range(ai*2,amax+1,ai):
            dp[aj]=False

aa=aa-dset    
print(len(aa))
### BUGGY CODE ###

from collections import defaultdict
from math import sqrt, floor
N = int(input())
A = list(map(int,input().split()))
M = 10**9+7
def factorize(n):
    fct = defaultdict(int)
    m = floor(sqrt(n))+1
    for b in range(2,m):
        e = 0
        while n%b == 0:
            n = n // b
            e += 1
        if e > 0:
            fct[b] = e
    if n > 1:
        fct[n] = 1
    return fct
dct = defaultdict(int)
dctT = [0]*N
for i,a in enumerate(A):
    dctT[i] = factorize(a)
    for key in dctT[i].keys():
        dct[key] = max(dct[key],dctT[i][key])
ans = 0
for i in range(N):
    t = 1
    for k,v in dct.items():
        t *= pow(k,v-dctT[i][k],M)
    ans += t%M
print(ans%M)

### FIXED CODE ###

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

N = int(input())
A = list(map(int,input().split()))
M = 10**9+7
l = 1
for a in A:
    l = lcm(l,a)
ans = 0
for a in A:
    ans += l//a
print(ans%M)
### BUGGY CODE ###

N,K=map(int,input().split())
L=[int(x) for x in input().split()]
LL=[L[i]*L[i+j] for i in range(0,N) for j in range(1,N-i)]
print(sorted(LL)[K-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
N,K=map(int,input().split())
L=[int(i) for i in input().split()]
Pos = [x for x in L if x > 0]
Zero = [x for x in L if x == 0]
Neg = [x for x in L if x < 0]
Pos.sort()
Neg.sort(reverse=True)

Po = len(Pos)
Ne = len(Neg)
Ze= len(Zero)

ZeN = Ze*(Ze-1)//2 + Ze*(Po+Ne)
NeN = Po*Ne

if NeN<K<=NeN+ZeN:
    print(0)

else:
    def f(x):
        cnt = 0
        if x < 0:
            j = Po - 1
            for i in range(Ne):
                j=min(Po-1,j+1)
                while j >=0:
                    if Neg[i] * Pos[j] <= x:
                        j = j - 1
                    else:
                        break
                cnt = cnt + Po - j - 1
        else:
            j = 0
            for i in range(Po)[::-1]:
                j=max(0,j-1)
                while j < i:
                    if Pos[i]*Pos[j] <= x:
                        j = j+1
                    else:
                        break
                cnt = cnt+j

            j = 0
            for i in range(Ne)[::-1]:
                j = max(0, j - 1)
                while j < i:
                    if Neg[i]*Neg[j] <= x:
                        j = j+1
                    else:
                        break
                cnt = cnt+j

            cnt = cnt + ZeN + NeN
        return(cnt)

    Hi = 10**18
    Lo = -10**18

    while Hi-Lo > 1:
        Mid = (Hi + Lo) // 2
        if f(Mid) >= K:
            Hi = Mid
        else:
            Lo = Mid
    print(Hi)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
f=l[0]
mod=10**9+7
def gcd(s,d):
  return gcd(d,s%d) if d!=0 else s
for i in l:
  f=i*f//gcd(i,f)
ans=0
for iu in l:
  ans+=(f//iu)%mod
  ans%=mod
print(ans)

### FIXED CODE ###

def s():
  from sys import stdin
  read=stdin.buffer.readline
  n=int(read())
  l=list(map(int,read().split()))
  f=l[0]
  mod=10**9+7
  def gcd(s,d):
    s,d=max(s,d),min(s,d)
    while  d:
      s,d=d,s%d
    return s
  for i in l:
    f=i*f//gcd(i,f)
  ans=0
  for iu in l:
    b,u,v=mod,1,0
    while b:
      t=iu//b;iu,b=b,iu%b;u-=t*v;u,v=v,u
    ans+=(f*u%mod)%mod
    ans%=mod
  print(ans)
  
if __name__=="__main__":s()
### BUGGY CODE ###

from collections import deque
N = int(input())
A = [deque(list(map(int, input().split()))) for _ in range(N)]
ans = 0
t = 0
z = 0
Atmp = []
for i in range(10**6):
    for k in range(N):
        if A[k] != deque([]):
            if A[k][0] == 0:
                A[k].popleft()
            else:
                z += 1
        else:
            t += 1
    if t == N:
        break
    if t+z == N and i != 0:
        ans = 0
        break
    z = 0
    t = 0
    for j in range(N):
        if A[j]:
            tmp = A[j][0]
        else:
            continue
        if tmp-1 > j and A[tmp-1][0] -1 == j:
            A[j][0] = 0
            A[tmp-1][0] = 0
    ans += 1
print(ans-1)

### FIXED CODE ###

from collections import deque
import time     #ズルです…
start = time.time()
N = int(input())
A = [deque(list(map(int, input().split()))) for _ in range(N)]
ans = 0
t = 0
z = 0
Atmp = []
for i in range(10**6):
    for k in range(N):
        if A[k] != deque([]):
            if A[k][0] == 0:
                A[k].popleft()
            else:
                z += 1
        else:
            t += 1
    if t == N:
        break
    if t+z == N and i != 0:
        ans = 0
        break
    z = 0
    t = 0
    for j in range(N):
        if A[j]:
            tmp = A[j][0]
        else:
            continue
        if tmp-1 > j and A[tmp-1][0] -1 == j:
            A[j][0] = 0
            A[tmp-1][0] = 0
    ans += 1
    aida = time.time()
    if aida-start > 1.7:
        print(N*(N-1)//2)       #ズル
        exit()
print(ans-1)
### BUGGY CODE ###

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

limit = pow(10,18)

f = 0
for i in range(N):
    if A[i] != 0:
        ans *= A[i]
    else:
        print(0)
        exit()

    if ans > limit:
        f = 1

if f == 1:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

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

limit = pow(10,18)

f = 0
for i in range(N):
    if A[i] != 0 and f == 0:
        ans *= A[i]
    elif A[i] != 0:
        pass
    else:
        print(0)
        exit()

    if ans > limit:
        f = 1

if f == 1:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

def solve():
    N, K = map(int, input().split())
    ps = list(map(int, input().split()))
    expected = max([sum([(x + 1) / 2 for x in ps[left: left + K]]) for left in range(N - K + 1)])
    print(expected)

solve()

### FIXED CODE ###

def solve():
    N, K = map(int, input().split())
    ps = list(map(int, input().split()))
    curSum = sum(ps[:K])
    curMax = curSum
    i = K; j = 0
    while i < N:
        curSum -= ps[j]
        curSum += ps[i]
        curMax = max(curSum, curMax)
        i += 1; j += 1
    print((curMax + K) / 2)
solve()
### BUGGY CODE ###


n, m = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
result = sum(a)
b_ = []
for i in range(m):
    b, c = map(int, input().split(' '))
    tmp = [c] * b
    b_ += tmp
result = a + b_
result.sort(reverse=True)
print(sum(result[:n]))

### FIXED CODE ###


n, m = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
result = sum(a)
b_ = []
for i in range(m):
    b, c = map(int, input().split(' '))
    b_ += [(b,c)]
for i in range(n):
    b_ += [(1, a[i])]

from operator import itemgetter
b_.sort(key=itemgetter(1), reverse=True)

count = n
res = 0
for j, k in b_:
    if count > j:
        res += k * j
        count -= j
    elif count <= j:
        res += k * count
        break
print(res)
### BUGGY CODE ###

N=int(input())
li = list(map(int, input().split()))
c=0
ali=[]
for i in range(0,N):
  for j in range(0,N):
    for k in range(0,N):
      if li[i]+li[j]>li[k] and li[j]+li[k]>li[i] and li[k]+li[i]>li[j]:
        if li[i]!=li[j] and li[j]!=li[k] and li[k]!=li[i]:
          ali.append(sorted([i,j,k]))
def get_duplicate_list(seq):
    seen = []
    return [x for x in seq if not seen.append(x) and seen.count(x) == 2]
print(len(get_duplicate_list(ali)))

### FIXED CODE ###

N=int(input())
li = list(map(int, input().split()))
c=0
ali=[]
for i in range(0,N):
  for j in range(0,N):
    for k in range(0,N):
      if li[i]+li[j]>li[k] and li[j]+li[k]>li[i] and li[k]+li[i]>li[j]:
        if li[i]!=li[j] and li[j]!=li[k] and li[k]!=li[i]:
          if i!=j and j!=k and k!=i and i<j and j<k:
            ali.append(sorted([i,j,k]))
print(len(ali))
### BUGGY CODE ###



S = input()
N = int(input())
l = len(S)

sub = {}
for i in range(1,l+1):
    for j in range(0,l+1-i):
        temp = S[j:j+i]
        if temp not in sub:
            sub [temp]  = True

sub = list(sub.keys())
sub.sort()
print(sub[N-1])





### FIXED CODE ###



S = input()
N = int(input())
l = len(S)

sub = {}
for i in range(1,6):
    for j in range(0,l+1-i):
        temp = S[j:j+i]
        if temp not in sub:
            sub [temp]  = True

sub = list(sub.keys())
sub.sort()
print(sub[N-1])
### BUGGY CODE ###

N = int(input())
A = [0] + list(map(int,input().split()))
ansl = []
ans = 10**9 + 7

for i in range(1,N+1):
    for j in range(1,N+1):
        if i < j:
            ansl.append((A[i])*(A[j]))

print(sum(ansl)%ans)

### FIXED CODE ###

import itertools

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

acc = list(itertools.accumulate(A))
ans = 0
mod = 10**9 + 7

for i in range(N-1):
    ans += acc[i]*(acc[i+1] -acc[i])
    

print(ans%mod)
### BUGGY CODE ###

def main():
    class rolling_hash():
        def __init__(self, sequence):
            seq_size = len(sequence)  # 文字列の長さ
            self.Hash_0start = [0]*(seq_size+1)  # 先頭からi-1文字目までのハッシュ値
            p = 0
            for i, j in enumerate(sequence):
                p = (p+(j+1)*pow(3, i, mod)) % mod
                self.Hash_0start[i+1] = p

        def calc_hash(self, l, r):  # l文字目からr-1文字目までのハッシュ値
            return ((self.Hash_0start[r] - self.Hash_0start[l])
                    * pow(3, l*(mod-2), mod)) % mod

    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    mod = 2**61-1

    memo = [0]*n

    for k in range(32):
        a1 = [i % 2 for i in a]
        a1 += a1
        a2 = [i ^ 1 for i in a1]
        b_hash = rolling_hash([i % 2 for i in b]).calc_hash(0, n)
        a1 = rolling_hash(a1)
        a2 = rolling_hash(a2)
        for i, j in enumerate(memo):
            if j is None:
                continue
            elif a1.calc_hash(i, i+n) == b_hash:
                pass
            elif a2.calc_hash(i, i+n) == b_hash:
                memo[i] += 2**k
            else:
                memo[i] = None
        a = [i // 2 for i in a]
        b = [i // 2 for i in b]

    for i, j in enumerate(memo):
        if j is not None:
            print(i, j)


main()


### FIXED CODE ###

def main():
    mod = 2**31-1
    pow3 = [1]*200001
    p = 1
    i3 = pow(3, mod-2, mod)
    for i in range(1, 200001):
        p = p*3 % mod
        pow3[i] = p

    def rolling_hash(seq):
        h = 0
        for i, j in enumerate(seq):
            h += (j+1)*pow3[i]
        h %= mod
        H0s = [0]*n
        for i, j in enumerate(seq):
            H0s[i] = h
            h = (h-j-1+(j+1)*pn)*i3 % mod
        return H0s

    def rolling_hash2(seq):
        p = 0
        p2 = 0
        for i, j in enumerate(seq):
            p += (j+1)*pow3[i]
            p2 += (2-j)*pow3[i]
        return p % mod, p2 % mod

    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    m = max(a+b)
    a1 = [0]*n
    b1 = [0]*n
    memo = [0]*n
    cnt = n
    pn = pow3[n]

    for k in range(len(bin(m))-2):
        k2 = 2**k
        for i, j in enumerate(a):
            a1[i] = (j & k2) >> k
        for i, j in enumerate(b):
            b1[i] = (j & k2) >> k
        b_hash, b_hash2 = rolling_hash2(b1)
        A1 = rolling_hash(a1)
        for i, (j, k) in enumerate(zip(memo, A1)):
            if j is None:
                continue
            elif k == b_hash:
                pass
            elif k == b_hash2:
                memo[i] += k2
            else:
                memo[i] = None
                cnt -= 1
        if cnt == 0:
            return

    for i, j in enumerate(memo):
        if j is not None:
            print(i, j)


main()
### BUGGY CODE ###

a,b,x = map(int,input().split())
c = 0
for i in range(a,b+1):
    if i%x == 0:
        c += 1
print(c)

### FIXED CODE ###

a,b,x = map(int,input().split())
if a%x != 0:
    print(b//x-a//x)
else:
    print(b//x-a//x+1)
### BUGGY CODE ###

x = raw_input()

w,h = [int(i) for i in x.split()]

p = []
for i in range(w):
    p.append(input())

q = []
for i in range(h):
    q.append(input())


cost = 0
p.sort()
q.sort()

iter = w+h


for i in range(iter):

    if(w==0):
        cost += q[0]*(w+1)
        h -= 0
        q.pop(0)

    elif(h==0):
        cost += p[0]*(h+1)
        w -= 0
        p.pop(0)

    elif(p[0]==q[0] and h>w):
        cost += p[0]*(h+1)
#        print cost,w,h
        w -= 1
        p.pop(0)

    elif(p[0]<q[0]):
        cost += p[0]*(h+1)
 #       print cost,w,h
        w -= 1
        p.pop(0)
    
    else:
        cost += q[0]*(w+1)
  #      print cost,w,h
        h -= 1
        q.pop(0)
    

print cost


### FIXED CODE ###

x = raw_input()
w,h = [int(i) for i in x.split()]
p = []
for i in range(w):
    p.append(input())
q = []
for i in range(h):
    q.append(input())
cost = 0
p.sort()
q.sort()
iter = w+h

p_iter = 0
q_iter = 0
for i in range(iter):
    if(w==0):
        cost += q[q_iter]*(w+1)
        h -= 0
        q_iter += 1

    elif(h==0):
        cost += p[p_iter]*(h+1)
        w -= 0
        p_iter += 1

    elif(p[p_iter]==q[q_iter] and h>w):
        cost += p[p_iter]*(h+1)
        w -= 1
        p_iter += 1

    elif(p[p_iter]<q[q_iter]):
        cost += p[p_iter]*(h+1)
        w -= 1
        p_iter += 1
    
    else:
        cost += q[q_iter]*(w+1)
        h -= 1
        q_iter += 1
    
print cost
### BUGGY CODE ###

N, K, C, = map(int,input().split())
S = list(input())
ans = []

def solve(index):
    i = 0
    cnt = 0
    while i < N:
        if S[i] == 'o' and i != index:
            cnt += 1
            i += C + 1
        else:
            i += 1
    return cnt < K

for index in range(N):
    if S[index] == 'x':
        continue
    elif solve(index):
        ans.append(index + 1)

for i in ans:
    print(i)

### FIXED CODE ###

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

def solve(List):
    ans = []
    i = 0
    while i < N:
        if List[i] == 'o':
            ans.append(i+1)
            i += C
        i += 1
    return ans

n = solve(S)

if len(n) > K:
    pass
else:
    r = solve(S[::-1])
    r = list(map(lambda x: N+1-x, r[::-1]))
    ans = list(set(n) & set(r))
    ans.sort()
    for i in ans:
        print(i)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n,q = list(map(int,input().split()))
s = input()
d = [list(map(int,input().split())) for i in range(q)]

for i in d:
    print(s[i[0]-1:i[1]].count("AC"))


### FIXED CODE ###

# -*- coding: utf-8 -*-
n,q = list(map(int,input().split()))
s = input()
s2 = s[1::]
d = [list(map(int,input().split())) for i in range(q)]

#AC開始位置を記録する
ac_idx = []

aci_append = ac_idx.append
for i,v in enumerate(zip(s,s2)):
    if v == ("A","C"):
        aci_append(i)

#2分探索, nibuntansaku,二分探索
from bisect import bisect_left

for l,r in d:
    print(bisect_left(ac_idx,r-1) - bisect_left(ac_idx,l-1))
### BUGGY CODE ###

#!/usr/bin/env python3
import math
import copy
N, K = map(int, input().split())
A = list(map(int, input().split()))

for k in range(K):
    D = [0]*N

    for i in range(N):
        D[i] += 1
        if A[i] == 0:
            continue

        left = math.ceil(i - A[i] - 0.5)
        right = math.floor(i + A[i] + 0.5)
        if left < 0: left = 0
        if right > N-1: right = N-1
    
        for j in range(left, right+1):
            if i == j: continue
            D[j] += 1

    A = D


print(' '.join(map(str,A)))

    


### FIXED CODE ###

#!/usr/bin/env python3
N, K = map(int, input().split())
A = list(map(int, input().split()))

if K > 41:
    K = 41

for k in range(K):
    D = [0]*N

    for i in range(N):
        left = max(i - A[i], 0)
        right = min(i + A[i], N-1)
        D[left] += 1
        if right + 1 < N: D[right+1] -= 1
    

    for i in range(1, N):
        D[i] += D[i-1]
    A = D


print(' '.join(map(str,A)))