Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
# N: 処理する区間の長さ
N, Q = map(int, input().split())
INF = 2**31

N-=1
LV = (N-1).bit_length()
N0 = 2**LV
data1 = [INF]*(2*N0)
data2 = [INF]*(2*N0)
lazy1 = [None]*(2*N0)
lazy2 = [None]*(2*N0)

# 伝搬対象の区間を求める
def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(data,lazy,*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if v is None:
            continue
        lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
        lazy[i-1] = None

# 区間[l, r)をxで更新
def update(l, r, x, data,lazy):
    *ids, = gindex(l, r)
    propagates(data,lazy,*ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] = data[R-1] = x
        if L & 1:
            lazy[L-1] = data[L-1] = x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = min(data[2*i-1], data[2*i])


ans = (N-2)*(N-2)
update(1,N-1,N-2,data1,lazy1)
update(1,N-1,N-2,data2,lazy2)
for i in range(Q):
  t,x = map(int, input().split())
  if t==1:
    ans -= data1[x-1]
    update(1,data1[x-1],x,data2,lazy2)
  else:
    ans -= data2[x-1]
    update(1,data2[x-1],x,data1,lazy1)
print(ans)


Fixed submission:
# N: 処理する区間の長さ 0_indexed
class SegmentTree:
  def __init__(self,N):
    self.N0 = 2**(N-1).bit_length()
    self.data = [None]*(2*self.N0)
    self.INF = (-1, 2**31-1)
  # 区間[l, r+1)の値をvに書き換える
  # vは(t, value)という値にする (新しい値ほどtは大きくなる)
  def update(self, l, r, v):
    L = l + self.N0; R = r + self.N0
    while L < R:
      if R & 1:
        R -= 1
        self.data[R-1] = v
      if L & 1:
        self.data[L-1] = v
        L += 1
      L >>= 1; R >>= 1
  # a_iの現在の値を取得
  def _query(self, k):
    k += self.N0-1
    s = self.INF
    while k >= 0:
      if self.data[k]:
        s = max(s, self.data[k])
      k = (k - 1) // 2
    return s
  # これを呼び出す
  def query(self,k):
    return self._query(k)[1]

N, Q = map(int, input().split())
row = SegmentTree(N-2)
col = SegmentTree(N-2)
ans = (N-2)*(N-2)
row.update(0,N-2,(0,N-2))
col.update(0,N-2,(0,N-2))
min_row = N
min_col = N
for i in range(1,Q+1):
  t,x = map(int, input().split())
  if t==1:
    num = col.query(x-2)
    ans -= num
    if x<min_col:
      row.update(0,num,(i,x-2))
      min_col = x
  else:
    num = row.query(x-2)
    ans -= num
    if x<min_row:
      col.update(0,num,(i,x-2))
      min_row = x
print(ans)
Buggy python submission (verdict: Runtime Error):
ans = 0
for i in range(L,R+1):
    if i%d==0:
        ans += 1
print(ans)

Fixed submission:
def solve():
    L, R, d = map(int, input().split())
    ans = R//d-(L-1)//d
    return ans
print(solve())
Buggy python submission (verdict: Time Limit Exceeded):
#素因数分解して列挙する関数、約数列挙ではない！
from collections import Counter
from math import log2

def factorize(n):
  if n==1:
    return 1
  b = 2
  fct = []
  while b * b <= n:
    while n % b == 0:
      n //= b
      fct.append(b)
    b = b + 1
  if n > 1:
    fct.append(n)
  c = Counter(fct)
  ans = 1
  for v in c.values():
    ans *= v+1
  return ans
def solve():
  ans = 0
  N = int(input())
  for i in range(1,N+1,2):
    f = factorize(i)
    m = int(log2(N//i))
    ans += i*f*(m*pow(2,m+1)+1)
  return ans
print(solve())

Fixed submission:
def solve():
    ans = 0
    N = int(input())
    for i in range(1,N+1):
        for j in range(1,N//i+1):
            ans += i*j
    return ans
print(solve())
Buggy python submission (verdict: Runtime Error):
def solve():
  N = int(input())
  k = 1
  while N>pow(26,k):
    N -= pow(26,k)
    k += 1
  ans = ''
  N -= 1
  for i in range(k,1,-1):
    ans += chr(ord('a')+N//pow(26,i-1))
    N%=pow(26,i-1)
  ans += chr(ord('a')+N%pow(26,i))
  return ans
print(solve())

Fixed submission:
N = int(input())
lis = [0,26]
num = 26
n = 1
while lis[-1]<N:
    num *= 26
    lis.append(lis[-1]+num)
    n += 1
c = N-lis[-2]-1
ans = ''
for i in range(n):
    ans = chr(c%26+ord('a')) + ans
    c //= 26
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def comb_mod(n,r,mod):
    ans = 1
    lis = []
    for i in range(r):
        ans *= n+i
        ans *= pow(i+1,-1,mod)
        ans %= mod
        lis.append(ans)
    return lis
def solve():
    ans = 1
    mod = 10**9+7
    K = int(input())
    S = input()
    s = len(S)
    lis = comb_mod(s,K,mod)
    for k in range(K):
        ans *= 26
        ans += lis[k]*pow(25,k+1,mod)
        ans %= mod
    return ans
print(solve())


Fixed submission:
def comb_mod(n,r,mod):
    ans = 1
    lis = []
    for i in range(r):
        ans *= n+i
        ans *= pow(i+1,mod-2,mod)
        ans %= mod
        lis.append(ans)
    return lis
def solve():
    ans = 1
    mod = 10**9+7
    K = int(input())
    S = input()
    s = len(S)
    lis = comb_mod(s,K,mod)
    for k in range(K):
        ans *= 26
        ans += lis[k]*pow(25,k+1,mod)
        ans %= mod
    return ans
print(solve())
Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    ans = 0
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    for j in range(K):
        check = [0]*(N+1)
        for i in range(N):
            check[max(0,i-A[i])] += 1
            check[min(N,i+A[i]+1)] -= 1
        A = [check[0]]*N
        for i in range(1,N):
            A[i] = A[i-1]+check[i]
        if A==[N]*N:
            break
    return A
print(*solve())

Fixed submission:
from copy import copy
def solve():
    ans = 0
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    for j in range(K):
        check = [0]*(N+1)
        for i in range(N):
            check[max(0,i-A[i])] += 1
            check[min(N,i+A[i]+1)] -= 1
        B = [check[0]]*N
        for i in range(1,N):
            B[i] = B[i-1]+check[i]
        A = copy(B)
        if A==[N]*N:
            break
    return A
print(*solve())

Buggy python submission (verdict: Time Limit Exceeded):
from copy import copy
def solve():
    ans = 0
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    for j in range(K):
        check = [0]*(N+1)
        for i in range(N):
            check[max(0,i-A[i])] += 1
            check[min(N,i+A[i]+1)] -= 1
        B = [check[0]]*N
        for i in range(1,N):
            B[i] = B[i-1]+check[i]
        A = copy(B)
        if A==[N]*N:
            break
    return A
print(*solve())

Fixed submission:
from copy import copy
def solve():
    ans = 0
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    for j in range(K):
        check = [0]*(N+1)
        for i in range(N):
            check[max(0,i-A[i])] += 1
            check[min(N,i+A[i]+1)] -= 1
        B = [check[0]]*N
        for i in range(1,N):
            B[i] = B[i-1]+check[i]
        A = copy(B)
        if A==[N]*N:
            break
    return A
print(*solve())
Buggy python submission (verdict: Runtime Error):
def solve():
    n = int(input())
    a = list(map(int, input().split()))

    ans = 1
 
    for i in a:
        ans *= i
      	if ans > int(1e18): return -1
    
    
    return ans
    

print(solve())


Fixed submission:
N, M = map(int, input().split())
print(N*M)
Buggy python submission (verdict: Runtime Error):
def solve():
    n = int(input())
    a = list(map(int, input().split()))

    ans = 1
 
    for i in a:
        ans *= i
      	if ans > int(1e18): return -1
    
    
    return ans
    

print(solve())


Fixed submission:
def solve():
    N = int(input())
    A = list(map(int, input().split()))
    if 0 in A:
        return 0
    prod = 1
    for i in range(N):
        if 10**18//prod < A[i]:
            return -1
        prod *= A[i]
    return prod
print(solve())
Buggy python submission (verdict: Time Limit Exceeded):
mod = 998244353
N, S = map(int, input().split())
A = list(map(int, input().split()))
dp = [[0]*(S+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(1,N+1):
    dp[i][0] = dp[i-1][0]*2%mod

for i in range(1,N+1):
    for j in range(1,S+1):
        dp[i][j] = dp[i-1][j]*2%mod
        if j>=A[i-1]:
            dp[i][j] += dp[i-1][j-A[i-1]]

ans = dp[-1][-1]%mod
print(ans)


Fixed submission:
mod = 998244353
N, S = map(int, input().split())
A = list(map(int, input().split()))
dp = [[0]*(S+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(1,N+1):
    dp[i][0] = dp[i-1][0]*2%mod

for i in range(1,N+1):
    for j in range(1,S+1):
        dp[i][j] = dp[i-1][j]*2%mod
        if j>=A[i-1]:
            dp[i][j] += dp[i-1][j-A[i-1]]

ans = dp[-1][-1]%mod
print(ans)

Buggy python submission (verdict: Runtime Error):
def solve():
    N = int(input())
    A = [0]*N
    B = [0]*N
    for i in range(N):
        A[i],B[i] = map(int, input().split())
    A.sort()
    B.sort(reverse=True)
    if N%2==1:
        mid = (N+1)//2-1
        ans = B[mid]-A[mid]+1
    else:
        mid1 = N//2-1
        mid2 = N//2
        ans = (B[mid1]+B[mid2])-(A[mid1]+A[mid2])+1
    return ans
print(solve())


Fixed submission:
mod = 998244353
N, S = map(int, input().split())
A = list(map(int, input().split()))
dp = [[0]*(S+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(1,N+1):
    dp[i][0] = dp[i-1][0]*2%mod

for i in range(1,N+1):
    for j in range(1,S+1):
        dp[i][j] = dp[i-1][j]*2%mod
        if j>=A[i-1]:
            dp[i][j] += dp[i-1][j-A[i-1]]

ans = dp[-1][-1]%mod
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
mod = 998244353
from itertools import groupby, accumulate, product, permutations, combinations
N, S = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
from collections import deque
cum = list(accumulate(A))[::-1]
A = A[::-1]
d = deque([(0,0,0)])
i = 0
lis = [0]*(N+1)
while len(d):
    a,cnt,i = d.popleft()
    if a+A[i]==S:
        lis[cnt+1] += 1
    elif a+cum[i]>=S and a+A[i]<S:
        d.append((a+A[i],cnt+1,i+1))
    if i<N-1 and cum[i+1]>=S-a:
        d.append((a,cnt,i+1))
ans = 0
for i in range(1,N+1):
    ans += lis[i]*pow(2,N-i,mod)
    ans %= mod
print(ans)

Fixed submission:
mod = 998244353
N, S = map(int, input().split())
A = list(map(int, input().split()))
dp = [[0]*(S+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(1,N+1):
    dp[i][0] = dp[i-1][0]*2%mod

for i in range(1,N+1):
    for j in range(1,S+1):
        dp[i][j] = dp[i-1][j]*2%mod
        if j>=A[i-1]:
            dp[i][j] += dp[i-1][j-A[i-1]]

ans = dp[-1][-1]%mod
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))


def solve(N,A):
    ans = 0
    lis = [0]*(2*10**5)
    for i,a in enumerate(A):
        lis[-a-i]+=1
    for i,a in enumerate(A):
        ans += lis[a-i]
    return ans
print(solve(N,A))

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


def solve(N,A):
    ans = 0
    lis = [0]*(2*10**5)
    for i,a in enumerate(A):
        if -a-i >= -2*10**5:
            lis[-a-i]+=1
    for i,a in enumerate(A):
        if a-i < 0:
            ans += lis[a-i]
    return ans
print(solve(N,A))
Buggy python submission (verdict: Runtime Error):
N, A, B, C = map(int, input().split())
dic = {'A':A,'B':B,'C':C}
S = [input() for _ in range(N)]

def solve(N,dic,S):
    ans = ['Yes']
    for i in range(N):
        if dic[S[i][0]]>dic[S[i][1]]:
            dic[S[i][0]]-=1
            dic[S[i][1]]+=1
            ans.append(S[i][1])
        elif dic[S[i][0]]<dic[S[i][1]] or dic[S[i][0]]>1:
            dic[S[i][1]]-=1
            dic[S[i][0]]+=1
            ans.append(S[i][0])
        elif dic[S[i][0]]==0:
            return ['No']
        else:
            if S[i][0] in S[i+1]:
                dic[S[i][0]]+=1
                dic[S[i][1]]-=1
                ans.append(S[i][0])
            else:
                dic[S[i][1]]+=1
                dic[S[i][0]]-=1
                ans.append(S[i][1])
    return ans
print(*solve(N,dic,S),sep='\n')

Fixed submission:
N, A, B, C = map(int, input().split())
dic = {'A':A,'B':B,'C':C}
S = [input() for _ in range(N)]

def solve(N,dic,S):
    ans = ['Yes']
    for i in range(N):
        if dic[S[i][0]]>dic[S[i][1]]:
            dic[S[i][0]]-=1
            dic[S[i][1]]+=1
            ans.append(S[i][1])
        elif dic[S[i][0]]<dic[S[i][1]] or dic[S[i][0]]>1:
            dic[S[i][1]]-=1
            dic[S[i][0]]+=1
            ans.append(S[i][0])
        elif dic[S[i][0]]==0:
            return ['No']
        elif i==N-1:
            dic[S[i][0]]+=1
            dic[S[i][1]]-=1
            ans.append(S[i][0])
        else:
            if S[i][0] in S[i+1]:
                dic[S[i][0]]+=1
                dic[S[i][1]]-=1
                ans.append(S[i][0])
            else:
                dic[S[i][1]]+=1
                dic[S[i][0]]-=1
                ans.append(S[i][1])
    return ans
print(*solve(N,dic,S),sep='\n')
Buggy python submission (verdict: Time Limit Exceeded):
S = [int(i) for i in input()]
from collections import Counter
def solve(S):
    n = len(S)
    cum = [0]*(n+1)
    for i in range(n):
        cum[i+1] = (cum[i]+S[n-1-i]*10**i)%2019
    c = [0]*2019
    for i in range(n+1):
        c[cum[i]] += 1
    ans = 0
    for v in c:
        ans += v*(v-1)//2
    return ans
print(solve(S))

Fixed submission:
S = [int(i) for i in input()]

def solve(S):
    n = len(S)
    cum = [0]*(n+1)
    mods = [0]*n
    mods[0] = 1
    for i in range(1,n):
        mods[i] = mods[i-1]*10%2019
    for i in range(n):
        cum[i+1] = (cum[i]+S[n-1-i]*mods[i])%2019
    c = [0]*2019
    for i in range(n+1):
        c[cum[i]] += 1
    ans = 0
    for v in c:
        ans += v*(v-1)//2
    return ans
print(solve(S))

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
from collections import Counter
def solve(S):
    n = len(S)
    cum = [0]*(n+1)
    for i in range(n):
        cum[i+1] = (cum[i]+int(S[n-1-i])*10**i)%2019
    c = Counter(cum)
    ans = 0
    for v in c.values():
        ans += v*(v-1)//2
    return ans
print(solve(S))

Fixed submission:
S = [int(i) for i in input()]

def solve(S):
    n = len(S)
    cum = [0]*(n+1)
    mods = [0]*n
    mods[0] = 1
    for i in range(1,n):
        mods[i] = mods[i-1]*10%2019
    for i in range(n):
        cum[i+1] = (cum[i]+S[n-1-i]*mods[i])%2019
    c = [0]*2019
    for i in range(n+1):
        c[cum[i]] += 1
    ans = 0
    for v in c:
        ans += v*(v-1)//2
    return ans
print(solve(S))

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
from collections import Counter
def solve(S):
    n = len(S)
    cum = [0]*(n+1)
    for i in range(n):
        cum[i+1] = (cum[i]+int(S[n-1-i])*10**i)%2019
    c = Counter(cum)
    ans = 0
    for v in c.values():
        ans += v*(v-1)//2
    return ans
print(solve(S))

Fixed submission:
S = [int(i) for i in input()]

def solve(S):
    n = len(S)
    cum = [0]*(n+1)
    mods = [0]*n
    mods[0] = 1
    for i in range(1,n):
        mods[i] = mods[i-1]*10%2019
    for i in range(n):
        cum[i+1] = (cum[i]+S[n-1-i]*mods[i])%2019
    c = [0]*2019
    for i in range(n+1):
        c[cum[i]] += 1
    ans = 0
    for v in c:
        ans += v*(v-1)//2
    return ans
print(solve(S))
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))

dp = [0]*N

cum = A[0]
for i in range(N):
    if i == 0:
        dp[i] = 0
        continue
    if i == 1:
        dp[i] = max(A[0],A[1])
        continue
    if i%2==0: #奇数の時
        cum += A[i]
        dp[i] = max(dp[i−1],dp[i-2]+A[i])

    if i%2==1: #偶数の時
        dp[i] = max(dp[i-2]+A[i],cum)

ans = dp[-1]


print(ans)
#print(*ans, sep='\n')

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

dp = [0]*N

cum = A[0]
for i in range(N):
    if i == 0:
        dp[i] = 0
        continue
    if i == 1:
        dp[i] = max(A[0],A[1])
        continue
    if i%2==0: #奇数の時
        cum += A[i]
        dp[i] = max(dp[i-1],dp[i-2]+A[i])

    if i%2==1: #偶数の時
        dp[i] = max(dp[i-2]+A[i],cum)

ans = dp[-1]


print(ans)
#print(*ans, sep='\n')
Buggy python submission (verdict: Runtime Error):
N, X, Y = map(int, input().split())
ans = [0]*N

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

for i in range(1,N):
	print(ans[i])


Fixed submission:
S = input()
ans = 'No'
if S[2]==S[3] and S[4]==S[5]:
  ans = 'Yes'
print(ans)

#print(*ans, sep='\n')
Buggy python submission (verdict: Time Limit Exceeded):
X,Y,A,B,C = map(int, input().split())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))
R = list(map(int, input().split()))
P.sort(reverse=True)
P = P[:X]
Q.sort(reverse=True)
Q = Q[:Y]
sp = sum(P)
sq = sum(Q)
ans = sp+sq
R.sort(reverse=True)
import heapq  # heapqライブラリのimport
heapq.heapify(P)  # リストを優先度付きキューへ
heapq.heapify(Q)
p = heapq.heappop(P) # 最小値の取り出し
q = heapq.heappop(Q)
r = R.pop(0)
while p<r or q<r:
  #print(p,q,r,ans)
  if r-p > r-q:
    heapq.heappush(P, r)
    ans += r-p
    p = heapq.heappop(P)
  else:
    heapq.heappush(Q, r)
    ans += r-q
    q = heapq.heappop(Q)
  if len(R)==0:
    break
  r = R.pop(0)
  #print(p,q,r,ans)
print(ans)

#print(*ans[1:], sep='\n')


Fixed submission:
X,Y,A,B,C = map(int, input().split())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))
R = list(map(int, input().split()))
P.sort(reverse=True)
P = P[:X]
Q.sort(reverse=True)
Q = Q[:Y]
sp = sum(P)
sq = sum(Q)
ans = sp+sq
R.sort(reverse=True)
import heapq  # heapqライブラリのimport
heapq.heapify(P)  # リストを優先度付きキューへ
heapq.heapify(Q)
p = heapq.heappop(P) # 最小値の取り出し
q = heapq.heappop(Q)
r = R.pop(0)
while p<r or q<r:
  #print(p,q,r,ans)
  if r-p > r-q:
    heapq.heappush(P, r)
    ans += r-p
    p = heapq.heappop(P)
  else:
    heapq.heappush(Q, r)
    ans += r-q
    q = heapq.heappop(Q)
  if len(R)==0:
    break
  r = R.pop(0)
  #print(p,q,r,ans)
print(ans)

#print(*ans[1:], sep='\n')

Buggy python submission (verdict: Time Limit Exceeded):
X,Y,A,B,C = map(int, input().split())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))
R = list(map(int, input().split()))
P.sort(reverse=True)
P = P[:X]
Q.sort(reverse=True)
Q = Q[:Y]
sp = sum(P)
sq = sum(Q)
ans = sp+sq
R.sort(reverse=True)
import heapq  # heapqライブラリのimport
heapq.heapify(P)  # リストを優先度付きキューへ
heapq.heapify(Q)
p = heapq.heappop(P) # 最小値の取り出し
q = heapq.heappop(Q)
r = R.pop(0)
while p<r or q<r:
  #print(p,q,r,ans)
  if r-p > r-q:
    heapq.heappush(P, r)
    ans += r-p
    p = heapq.heappop(P)
  else:
    heapq.heappush(Q, r)
    ans += r-q
    q = heapq.heappop(Q)
  if len(R)==0:
    break
  r = R.pop(0)
  #print(p,q,r,ans)
print(ans)

#print(*ans[1:], sep='\n')


Fixed submission:
X,Y,A,B,C = map(int, input().split())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))
R = list(map(int, input().split()))
P.sort(reverse=True)
P = P[:X]
Q.sort(reverse=True)
Q = Q[:Y]
sp = sum(P)
sq = sum(Q)
ans = sp+sq
R.sort(reverse=True)
import heapq  # heapqライブラリのimport
heapq.heapify(P)  # リストを優先度付きキューへ
heapq.heapify(Q)
p = heapq.heappop(P) # 最小値の取り出し
q = heapq.heappop(Q)
r = R.pop(0)
while p<r or q<r:
  #print(p,q,r,ans)
  if r-p > r-q:
    heapq.heappush(P, r)
    ans += r-p
    p = heapq.heappop(P)
  else:
    heapq.heappush(Q, r)
    ans += r-q
    q = heapq.heappop(Q)
  if len(R)==0:
    break
  r = R.pop(0)
  #print(p,q,r,ans)
print(ans)

#print(*ans[1:], sep='\n')
Buggy python submission (verdict: Runtime Error):
import itertools
H, W, K = map(int, input().split())

S = [0]*H
for i in range(H):
  S[i] = input()
Sdivs = []
mcnt = 1100
for b in itertools.product([0, 1], repeat=H-1):
  start = 0
  end = 1
  Sdivs=[]
  for a in b:
    if a==1:
      Sdivs.append(S[start:end])
      start = end
    end += 1
  Sdivs.append(S[start:end])
  cnt = sum(b)
  ones_cum = [0]*len(Sdivs)
  ones = [0]*len(Sdivs)
  mark1,mark2 = False,False
  ws = [0]
  for w in range(1,W):
    if mark2 == True:
      #print(mark)
      break
    for i,Sdiv in enumerate(Sdivs):
      #print(w)
      for s in Sdiv:
        ones_cum[i] += s[w-1]=='1'
        ones[i] += s[w-1]=='1'
      if ones_cum[i] > K:
        mark1 = True
        if w-1 == ws[-1]:
          mark2 = True
        ws.append(w-1)
      #print(ones_cum,ws)
    if mark1 == True:
      mark1 = False
      ones_cum = ones
    ones = [0]*len(Sdivs)
  if mark2 == True:
    continue
  cnt += len(ws)-1
  mcnt = min(mcnt,cnt)
print(mcnt)

Fixed submission:
N, M = map(int, input().split())

ans = N*(N-1)//2+M*(M-1)//2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
Q = int(input())
for i in range(Q):
  Query = input().split()
  if len(Query) == 3:
    T,F,C = Query
    if F == '1':
      S = C+S
    else:
      S = S+C
  else:
    T = Query
    S = S[::-1]
print(S)

Fixed submission:
S = input()
Q = int(input())
flip = 0
head = []
tail = []
for i in range(Q):
  Query = input().split()
  if len(Query) == 3:
    T,F,C = Query
    F = int(F)-1
    if F^flip == 1:
      tail.append(C)
    else:
      head.append(C)
  else:
    flip ^= 1
if flip:
  head, tail = tail, head
  S = S[::-1]
head = ''.join(head[::-1])
tail = ''.join(tail)
print(head+S+tail)
Buggy python submission (verdict: Runtime Error):
N, M, K = map(int, input().split())
friend = [[] for _ in range(N+1)]
block = [[] for _ in range(N+1)]

for i in range(M):
  A,B = map(int, input().split())
  friend[A].append(B)
  friend[B].append(A)

for i in range(K):
  C,D = map(int, input().split())
  block[C].append(D)
  block[D].append(C)
#print(friend)
#print(block)

#import queue
grouping = [False]*(N+1)
#print(grouping)
grouping[0] = True
group = [0]*(N+1)
g_num = 0
g_cnt = []
for i in range(1,N+1):
  cnt = 0
  if grouping[i] == True:
    continue 
  group[i] = g_num
  grouping[i] = True
  #q = queue.Queue()
  #q.put(i)
  stack = [i]
  #while not q.empty():
  while len(stack)>0:
    #print('v:',visited)
    #p = q.get()
    p = stack.pop()
    for f in friend[p]:
      #print(p,f)
      if grouping[f]==False:
        #q.put(f)
        stack.append(f)
        group[f]=g_num
        grouping[f] =True
        cnt += 1
  g_num += 1
  g_cnt.append(cnt)
  #print('g:',grouping)
ans = []
for i in range(1,N+1):
  c = g_cnt[group[i]]-len(friend[i])
  for b in block[i]:
    if group[b]==group[i]:
      c -= 1
  ans.append(c)
print(*ans)

Fixed submission:
print(int((int(input())+1)/2))
Buggy python submission (verdict: Runtime Error):
n,a,b = [int(i) for i in input().split()]
mod = 10**9+7

def mpow(a,n):
  if n == 1:
    return a
  x = mpow(a,n//2)
  ans = x*x%mod
  if n%2==1:
    ans *= a
  return ans

def comb(n,a,b):
  if a < b:
    s, l = a, b
  else:
    s, l = b, a
  rs = 1
  for i in range(s):
    rs = rs*(n-i)%mod
  rl = rs
  for i in range(s,l):
    rl = rl*(n-i)%mod
  for i in range(1,s+1):
    rs = rs*mpow(i,mod-2)%mod
  rl = rl
  for i in range(s+1,l+1):
    rl = rl*mpow(i,mod-2)%mod
  if a < b:
    nCa, nCb = rs, rl
  else:
    nCa, nCb = rl, rs
  return nCa, nCb
nCa,nCb = comb(n,a,b)
print((mpow(2,n)-1-nCa-nCb)%mod)
# print(nCa,nCb)

Fixed submission:
inp = [int(i) for i in input().split()]
N = inp[0]
R = inp[1]
if N >= 10:
	print(R)
else:
  	print(R+100*(10-N))
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
P = list(map(int, input().split()))
m = 0
for i in range(N-K+1):
  sum = 0
  for j in range(i,i+K):
    sum += (P[j]+1)/2
    m = max(m, sum)
print(m)


Fixed submission:
N, K = map(int, input().split())
P = list(map(int, input().split()))
p = 0
for j in range(K):
  p += (P[j]+1)/2
m = p
for i in range(N-K):
  p = p + (P[i+K]+1)/2 - (P[i]+1)/2
  m = max(m,p)
print(m)