Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):

s=list(input())



for i in range(len(s)):
    if s[i]=="A" or s[i]=="T" or s[i]=="G" or s[i]=="C":
        s[i]=1
    else:
        s[i]=0
list=[]
for i in range(len(s)):
    for j in range(len(s)-i):
        if s[i+j]==0:
            list.append(j)
            break

print(max(list))


Fixed submission:

s=list(input())



for i in range(len(s)):
    if s[i]=="A" or s[i]=="T" or s[i]=="G" or s[i]=="C":
        s[i]=1
    else:
        s[i]=0
list_s=[]
for i in range(len(s)):
    flag=1
    for j in range(len(s)-i):
        if s[i+j]==0:
            list_s.append(j)
            flag=0
            break
    if flag:
        list_s.append(len(s)-i)

print(max(list_s))
Buggy python submission (verdict: Time Limit Exceeded):
n, q=map(int, input().split())
s=input()
l_list=[]
r_list=[]

for i in range(q):
    l, r=map(int, input().split())
    l_list.append(l)
    r_list.append(r)


for i in range(q):#10**5
    count=0
    target_s=s[l_list[i]-1:r_list[i]]
    print(target_s.count("AC"))


Fixed submission:
n, q=map(int, input().split())
s=input()
l_list=[]
r_list=[]

t=[0]*(n+1)
for i in range(n):
    t[i+1]=t[i]+(1 if s[i:i+2]=="AC" else 0)

for i in range(q):
    l, r=map(int, input().split())
    print(t[r-1]-t[l-1])

Buggy python submission (verdict: Time Limit Exceeded):
n, q=map(int, input().split())
s=list(input())
l_list=[]
r_list=[]

for i in range(q):
    l, r=map(int, input().split())
    l_list.append(l)
    r_list.append(r)


for i in range(q):
    count=0
    target_s=s[l_list[i]-1:r_list[i]]
    indexes=[i for i, x in enumerate(target_s) if x=="A"]
    for j in indexes:
        if j+1<=len(target_s)-1 and target_s[j+1]=="C":
            count=count+1

    print(count)


Fixed submission:
n, q=map(int, input().split())
s=input()
l_list=[]
r_list=[]

t=[0]*(n+1)
for i in range(n):
    t[i+1]=t[i]+(1 if s[i:i+2]=="AC" else 0)

for i in range(q):
    l, r=map(int, input().split())
    print(t[r-1]-t[l-1])

Buggy python submission (verdict: Time Limit Exceeded):
n, q=map(int, input().split())
s=list(input())
l_list=[]
r_list=[]
for i in range(q):
    l, r=map(int, input().split())
    l_list.append(l)
    r_list.append(r)

for i in range(q):
    count=0
    target_s=s[l_list[i]-1:r_list[i]]
    for j in range(len(target_s)-1):
        if target_s[j]=="A":
            if target_s[j+1]=="C":
                count=count+1
    print(count)


Fixed submission:
n, q=map(int, input().split())
s=input()
l_list=[]
r_list=[]

t=[0]*(n+1)
for i in range(n):
    t[i+1]=t[i]+(1 if s[i:i+2]=="AC" else 0)

for i in range(q):
    l, r=map(int, input().split())
    print(t[r-1]-t[l-1])

Buggy python submission (verdict: Time Limit Exceeded):
n, q=map(int, input().split())
s=list(input())
l_list=[]
r_list=[]
for i in range(q):
    l, r=map(int, input().split())
    l_list.append(l)
    r_list.append(r)

for i in range(q):
    count=0
    target_s=s[l_list[i]-1:r_list[i]]
    for i in range(len(target_s)-1):
        if target_s[i]=="A":
            if target_s[i+1]=="C":
                count=count+1
    print(count)


Fixed submission:
n, q=map(int, input().split())
s=input()
l_list=[]
r_list=[]

t=[0]*(n+1)
for i in range(n):
    t[i+1]=t[i]+(1 if s[i:i+2]=="AC" else 0)

for i in range(q):
    l, r=map(int, input().split())
    print(t[r-1]-t[l-1])
Buggy python submission (verdict: Time Limit Exceeded):
import sys

n, x=map(int, input().split())
A=list(map(int, input().split()))

ans=0
for i in range(n-1):
    while(A[i]+A[i+1]>x and A[i+1]>0):
        A[i+1]=A[i+1]-1
        ans=ans+1
    while(A[i]+A[i+1]>x and A[i]>0):
        A[i]=A[i]-1
        ans=ans+1
    if A[i]+A[i+1]>x:
        print(0)
        sys.exit()
print(ans)


Fixed submission:
import sys

n, x=map(int, input().split())
A=list(map(int, input().split()))

ans=0
for i in range(n-1):
    next_sum=A[i]+A[i+1]
    if next_sum>x:
        if next_sum-x<=A[i+1]:
            A[i+1]=A[i+1]-(next_sum-x)
            ans=ans+(next_sum-x)
        else:
            ans=ans+A[i+1]
            if next_sum-x-A[i+1]<=A[i]:
                A[i]=A[i]-(next_sum-x-A[i+1])
                ans=ans+(next_sum-x-A[i+1])
            else:
                print(0)
                sys.exit()
            A[i+1]=0
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
ans = [0] * (N)
for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            n = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x - 1
            if n <= N:
                ans[n] += 1
for i in ans:
    print(i)


Fixed submission:
N = int(input())
ans = [0] * N
for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            n = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x - 1
            if n < N:
                ans[n] += 1
for i in ans:
    print(i)
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
from itertools import accumulate

N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
a = [0]+list(accumulate(A))
b = [0]+list(accumulate(B))
ans,j = 0,M
for i in range(N+1):
    if i > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans,i+j)
print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
from itertools import accumulate

N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
a = [0]+list(accumulate(A))
b = [0]+list(accumulate(B))
ans,j = 0,M
for i in range(N+1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans,i+j)
print(ans)

Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
from itertools import accumulate

N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
Acc = list(accumulate(A))
Bcc = list(accumulate(B))
a = N-1
b = M-1
ans = 0
for n,i in enumerate(Acc):
    if i > K:
        a = n-1
        break
for n,i in enumerate(Bcc):
    if i > K:
        b = n-1
        break
if a > b:
    K -= Acc[a]
    b = 0
    for i in B:
        if i <= K:
            K -= i
            b += 1
        elif i < A[a]:
            K += A[a]-i
            a -= 1
            b += 1
        else:
            break
else:
    K -= Bcc[b]
    a = 0
    for i in A:
        if i <= K:
            K -= i
            b += 1
        elif i < B[b]:
            K += B[b] - i
            b -= 1
            a += 1
        else:
            break
a = a+1 if a else a
b = b+1 if b else b
print(a+b)

Fixed submission:
import sys
input = sys.stdin.readline
from itertools import accumulate

N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
a = [0]+list(accumulate(A))
b = [0]+list(accumulate(B))
ans,j = 0,M
for i in range(N+1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans,i+j)
print(ans)
Buggy python submission (verdict: Runtime Error):
import math
from collections import defaultdict
N = int(input())
d = defaultdict(int)
def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial):
            input_list[s] = False
l = sieve_of_erastosthenes(N)
cnt = 0
while N != 1 and cnt<len(l):

    while l[cnt] and N%cnt == 0:
        d[cnt] += 1
        N //=cnt
    cnt += 1
ans = 0
for i in d.values():
    tmp = 1
    while i - tmp >= 0:
        i -= tmp
        tmp += 1
        ans += 1
print(ans)

Fixed submission:
import copy
from collections import defaultdict

N = int(input())
tmp = copy.copy(N)
d = defaultdict(int)
if N == 1:
    print(0)
    exit()
for i in range(2, int(N ** 0.5) + 3):
    while N % i == 0:
        N //= i
        d[i] += 1
if N > 1:
    d[N] += 1
ans = 0
for i in d.values():
    tmp = 1
    while i - tmp >= 0:
        i -= tmp
        tmp += 1
        ans += 1
print(ans)

Buggy python submission (verdict: Runtime Error):
import math
from collections import defaultdict
N = int(input())
d = defaultdict(int)
def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial):
            input_list[s] = False
l = sieve_of_erastosthenes(int(pow(N,0.5))+2)
cnt = 0
while N != 1 and cnt<len(l):

    while l[cnt] and N%cnt == 0:
        d[cnt] += 1
        N //=cnt
    cnt += 1
ans = 0
for i in d.values():
    tmp = 1
    while i - tmp >= 0:
        i -= tmp
        tmp += 1
        ans += 1
print(ans)

Fixed submission:
import copy
from collections import defaultdict

N = int(input())
tmp = copy.copy(N)
d = defaultdict(int)
if N == 1:
    print(0)
    exit()
for i in range(2, int(N ** 0.5) + 3):
    while N % i == 0:
        N //= i
        d[i] += 1
if N > 1:
    d[N] += 1
ans = 0
for i in d.values():
    tmp = 1
    while i - tmp >= 0:
        i -= tmp
        tmp += 1
        ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
from math import gcd
from collections import defaultdict
N=int(input())
mod = 10**9+7
d_1 = defaultdict(int)
d_2 = defaultdict(int)
zeros = 0

def to_irreducible(a,b):
    GCD = gcd(a,b)
    return list(map(lambda x:x//GCD,[a,b]))
for i in range(N):
    a,b=map(int,input().split(' '))
    if a==b==0:
        zeros += 1
        continue
    if a*b >= 0 and b!=0:
        a,b = to_irreducible(abs(a),abs(b))
        d_1[(a,b)] +=1
    else:
        a,b = to_irreducible(abs(b),abs(a))
        d_1[(a,b)] +=0
        d_2[(a,b)] +=1

ans =  1

for k,v_1 in d_1.items():
    v_2 = d_2[k]
    ans *= pow(2,v_1,mod) + pow(2,v_2,mod) -1
    ans %= mod

print(ans+zeros-1)

Fixed submission:
n=int(list(input())[-1])
if n in [2,4,5,7,9]:
    print('hon')
elif n==3:
    print('bon')
else:
    print('pon')
Buggy python submission (verdict: Runtime Error):
from math import gcd
from fractions import Fraction
from numpy import sign
N=int(input())
d={}
mod = 10**9+7
d={}
zeros = 0
b_zero = 0
a_zero = 0
for i in range(N):
    a, b = map(int,input().split(' '))
    a, b = map(lambda x:x//gcd(a,b),[a,b])
    if a == b == 0:
        zeros += 1
    elif a == 0:
        a_zero += 1
    elif b == 0:
        b_zero += 1
    else:
        h,t=sorted([Fraction(a,b),Fraction(-b,a)])
        key = str(h)+'/'+str(t)
        d.setdefault(key,[0,0])
        if a*b > 0:
            d[key][0] += 1
        else:
            d[key][1] += 1
ans = 1
for  v in d.values():
    h,t=sorted(v)
    if h>0:
        ans *= pow(2,h,mod) + pow(2,t,mod) -1
    else:
        ans *= pow(2,t,mod)
    ans %=mod
ans += pow(2,a_zero,mod) + pow(2,b_zero,mod) + zeros -3
print(ans)

Fixed submission:
from math import gcd
from collections import defaultdict
N=int(input())
mod = 10**9+7
d_1 = defaultdict(int)
d_2 = defaultdict(int)
zeros = 0

def to_irreducible(a,b):
    GCD = gcd(a,b)
    return list(map(lambda x:x//GCD,[a,b]))
for i in range(N):
    a,b=map(int,input().split(' '))
    if a==b==0:
        zeros += 1
    elif a*b >= 0 and b!=0:
        a,b = to_irreducible(abs(a),abs(b))
        d_1[(a,b)] +=1
    else:
        a,b = to_irreducible(abs(b),abs(a))
        d_1[(a,b)] +=0
        d_2[(a,b)] +=1

ans =  1

for k,v_1 in d_1.items():
    v_2 = d_2[k]
    ans *= (pow(2,v_1,mod) + pow(2,v_2,mod) -1)
    ans %= mod

print((ans+zeros-1)%mod)
Buggy python submission (verdict: Runtime Error):
N,K=map(int,input().split(' '))
A=list(map(lambda x:int(x)-1,input().split(' ')))
roop=[0]
flg = [0 for i in range(N)]
n = A[0]
cnt = 0
while not flg[n] and n !=0:
    cnt += 1
    roop.append(n)
    flg[n]=cnt
    n = A[n]
if K<=len(roop):
    print(roop[K])
else:
    print(roop[flg[n]:cnt+1][(K-flg[n])%(cnt-flg[n]+1)]+1)

Fixed submission:
N,K=map(int,input().split(' '))
A=list(map(lambda x:int(x)-1,input().split(' ')))
roop=[0]
flg = [0 for i in range(N)]
flg[0]=1
n = A[0]
for i in range(2,N+1):
    if flg[n]==0:
        roop.append(n)
        flg[n] = i
        n = A[n]
    else:
        end=i
        break
if K <len(roop):
    print(roop[K]+1)
else:
    K-=flg[n]-1
    K%=(end-flg[n])
    roop=roop[flg[n]-1:end]
    print(roop[K]+1)
Buggy python submission (verdict: Runtime Error):
N,M,K=map(int,input().split(' '))
mod = 998244353
ans =0
fac=[0]*N
inv=[0]*N
finv=[0]*N
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2,N):
    fac[i] = fac[i-1]*i%mod
    inv[i] = mod-inv[mod%i]*(mod//i)%mod
    finv[i] = finv[i-1]*inv[i]%mod
def COM(n,k):
    if (n < k):
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n]*(finv[k]*finv[n-k]%mod)%mod
for i in range(K+1):
    #print(M*pow(M-1,N-1-i,mod),COM(N-1,i))
    ans += M*pow(M-1,N-1-i,mod)*COM(N-1,i)
    ans %=mod
print(ans)

Fixed submission:
N,M,K=map(int,input().split(' '))
mod = 998244353
ans =0
fac=[0]*(N+1)
inv=[0]*(N+1)
finv=[0]*(N+1)
fac[0] = fac[1] = 1
finv[0] = 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
def COM(n,k):
    return fac[n]*(finv[k]*finv[n-k]%mod)%mod
for i in range(K+1):
    ans += M*pow(M-1,N-1-i,mod)*COM(N-1,i)
    ans %=mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
S=input()
lenS=len(S)
ans = 0
l = []
for i in range(lenS):
    l.append(int(S[i:])%673)
for k,v in Counter(l).items():
    if k==0:
        ans += v
    else:
        ans += v*(v-1)//2
print(ans)

Fixed submission:
S=list(map(int,input()[::-1]))
lenS=len(S)
cnt = [0]*2019
tmp = 0
for n,i in enumerate(S):
    tmp += i*pow(10,n,2019)
    cnt[tmp%2019]+=1
ans = cnt[0]*(cnt[0]+1)//2
for i in cnt[1:]:
    ans += i*(i-1)//2
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
S=input()
lenS=len(S)
ans = 0
l = []
for i in range(lenS):
    l.append(int(S[i:])%673)
for k,v in Counter(l).items():
    if k==0:
        ans += v
    else:
        ans += v*(v-1)//2
print(ans)

Fixed submission:
S=list(map(int,input()[::-1]))
lenS=len(S)
cnt = [0]*2019
tmp = 0
for n,i in enumerate(S):
    tmp += i*pow(10,n,2019)
    cnt[tmp%2019]+=1
ans = cnt[0]*(cnt[0]+1)//2
for i in cnt[1:]:
    ans += i*(i-1)//2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
S=input()
ans = 0
d={'R':0,'G':0,'B':0}
R,G,B=[],[],[]
for i in S:
    d[i]+=1
    R.append(d['R'])
    G.append(d['G'])
    B.append(d['B'])
for i in range(N-2):
    for j in range(i+1,N-1):
        s = [S[i],S[j]]
        if len(set(s))==2:
            if 'R' not in s:
                ans += R[-1]-R[j]
            elif 'G' not in s:
                ans += G[-1]-G[j]
            else:
                ans += B[-1]-B[j]
            if 0<=2*j-i<N and len(set([S[i],S[j],S[2*j-i]]))==3:
                ans -=1
print(ans)

Fixed submission:
N=int(input())
S=input()
ans = 0
d={'R':0,'G':0,'B':0}
R,G,B=[],[],[]
for i in S:
    d[i]+=1
    R.append(d['R'])
    G.append(d['G'])
    B.append(d['B'])
for i in range(N-2):
    for j in range(i+1,N-1):
        s = [S[i],S[j]]
        if len(set(s))==2:
            if 'R' not in s:
                ans += R[-1]-R[j]
            elif 'G' not in s:
                ans += G[-1]-G[j]
            else:
                ans += B[-1]-B[j]
            if 0<=2*j-i<N and len(set([S[i],S[j],S[2*j-i]]))==3:
                ans -=1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split(' '))
mod =10**9+7
dp=[pow(K//i,N,mod) for i in range(1,K+1)]
for i in range(K,1,-1):
    tmp=[1]
    for j in range(2,int(pow(i+1,0.5))+1):
        if i%j==0:
            tmp.append(j)
            if i != j*j:
                tmp.append(i//j)
    for k in tmp:
        dp[k-1] -=dp[i-1]
ans = 0
for n,i in enumerate(dp):
    ans += (n+1)*i
    ans %=mod
print(ans)

Fixed submission:
N,K=map(int,input().split(' '))
mod =10**9+7
dp=[pow(K//i,N,mod) for i in range(1,K+1)]
for i in range(K,1,-1):
    tmp=[1]
    for j in range(2,int(pow(i+1,0.5))+1):
        if i%j==0:
            tmp.append(j)
            if i != j*j:
                tmp.append(i//j)
    for k in tmp:
        dp[k-1] -=dp[i-1]
ans = 0
for n,i in enumerate(dp):
    ans += (n+1)*i
    ans %=mod
print(ans)
Buggy python submission (verdict: Runtime Error):
import heapq as hq
X,Y,A,B,C=map(int,input().split(' '))
P,Q,R=[sorted(list(map(int,input().split(' '))),reverse=True) for i in range(3)]
P=P[:X]
Q=Q[:Y]
hq.heapify(P)
hq.heapify(Q)
R=R[::-1]
while len(R)>0:
    p=hq.heappop(P)
    q=hq.heappop(Q)
    r=R.pop()
    if r<min(p,q):
        hq.heappush(P,p)
        hq.heappush(Q,q)
        break
    if p<=q and p<r:
        hq.heappush(P,r)
        hq.heappush(Q,q)
    elif p>q and q<r:
        hq.heappush(P,p)
        hq.heappush(Q,r)
print(sum(P)+sum(Q))

Fixed submission:
import heapq as hq
X,Y,A,B,C=map(int,input().split(' '))
P,Q,R=[sorted(list(map(int,input().split(' '))),reverse=True) for i in range(3)]
P=P[:X]
Q=Q[:Y]
hq.heapify(P)
hq.heapify(Q)
R=R[::-1]
while len(R)>0:
    p=hq.heappop(P)
    q=hq.heappop(Q)
    r=R.pop()
    if r<=min(p,q):
        hq.heappush(P,p)
        hq.heappush(Q,q)
        break
    if p<=q and p<r:
        hq.heappush(P,r)
        hq.heappush(Q,q)
    elif p>q and q<r:
        hq.heappush(P,p)
        hq.heappush(Q,r)
print(sum(P)+sum(Q))
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
from itertools import product

H,W,K=map(int,input().split(' '))
arr = np.vstack([[int(i) for i in input()] for j in range(H)])
ans = H+W-2
for p in product([0,1],repeat=H-1):
    sp=np.zeros((sum(p)+1,W),int)
    row=0
    sp[0]+=arr[0]
    for j in range(H-1):
        if p[j]:
            row+=1
        sp[row]+=arr[j+1]
    if np.max(sp)>K:
        continue
    sum_arr = np.zeros(len(sp),int)
    cut_cnt = sum(p)
    for c in range(W):
        sum_arr += sp[:,c]
        if max(sum_arr)>K:
            cut_cnt+=1
            sum_arr=sp[:,c]
            if cut_cnt > ans:
                break
    ans = min(cut_cnt,ans)
print(ans)

Fixed submission:
import numpy as np
from itertools import product

H,W,K=map(int,input().split(' '))
arr = np.vstack([[int(i) for i in input()] for j in range(H)])
ans = H+W-2
for p in product([0,1],repeat=H-1):
    if sum(p)>ans:
        continue
    sp=np.zeros((sum(p)+1,W),int)
    row=0
    sp[0]+=arr[0]
    for j in range(H-1):
        if p[j]:
            row+=1
        sp[row]+=arr[j+1]
    if np.max(sp)>K:
        continue
    sum_arr = np.zeros(len(sp),int)
    cut_cnt = sum(p)
    for c in range(W):
        sum_arr += sp[:,c]
        if max(sum_arr)>K:
            cut_cnt+=1
            sum_arr=sp[:,c]
            if cut_cnt > ans:
                break
    ans = min(cut_cnt,ans)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
from itertools import product

H,W,K=map(int,input().split(' '))
arr = np.vstack([[int(i) for i in input()] for j in range(H)])
ans = H+W-2
for p in product([0,1],repeat=H-1):
    sp=np.zeros((sum(p)+1,W),int)
    row=0
    sp[0]+=arr[0]
    for j in range(H-1):
        if p[j]:
            row+=1
        sp[row]+=arr[j+1]
    if np.max(sp)>K:
        continue
    sum_arr = np.zeros(len(sp),int)
    cut_cnt = sum(p)
    for c in range(W):
        sum_arr += sp[:,c]
        if max(sum_arr)>K:
            cut_cnt+=1
            sum_arr=sp[:,c]
    ans = min(cut_cnt,ans)
print(ans)

Fixed submission:
import numpy as np
from itertools import product

H,W,K=map(int,input().split(' '))
arr = np.vstack([[int(i) for i in input()] for j in range(H)])
ans = H+W-2
for p in product([0,1],repeat=H-1):
    if sum(p)>ans:
        continue
    sp=np.zeros((sum(p)+1,W),int)
    row=0
    sp[0]+=arr[0]
    for j in range(H-1):
        if p[j]:
            row+=1
        sp[row]+=arr[j+1]
    if np.max(sp)>K:
        continue
    sum_arr = np.zeros(len(sp),int)
    cut_cnt = sum(p)
    for c in range(W):
        sum_arr += sp[:,c]
        if max(sum_arr)>K:
            cut_cnt+=1
            sum_arr=sp[:,c]
            if cut_cnt > ans:
                break
    ans = min(cut_cnt,ans)
print(ans)
Buggy python submission (verdict: Runtime Error):
N=int(input())
ans = []
def same(c):
    if len(c)==N:
        ans.append(c)
        return
    else:
        for i in range(ord('a'),ord(c[-1])+2):
            same(c+chr(i))
same('a')
for i in ans:
    print(ans)

Fixed submission:
N=int(input())
ans = []
def same(c):
    if len(c)==N:
        ans.append(c)
        return
    else:
        for i in range(ord('a'),ord('a')+len(list(set(list(c))))+1):
            same(c+chr(i))

same('a')
for i in ans:
    print(i)
Buggy python submission (verdict: Runtime Error):
from collections import deque
s=deque(list(input()))
q=int(input())
r = False
for i in range(q):
    tmp = list(input().split(' '))
    if tmp[0]=='1':
        r = not r
    elif (not r and tmp[1]=='1') or (r and tmp[1] =='2'):
        s.appendleft(tmp[2])
    else:
        s.append(tmp[2])
if not r:
    for i in s:
        print(i,end='')
else:
    for i in s[::-1]:
        print(i,end='')

Fixed submission:
from collections import deque
s=deque(list(input()))
q=int(input())
r = False
for i in range(q):
    tmp = list(input().split(' '))
    if tmp[0]=='1':
        r = not r
    elif (not r and tmp[1]=='1') or (r and tmp[1] =='2'):
        s.appendleft(tmp[2])
    else:
        s.append(tmp[2])
if not r:
    for i in s:
        print(i,end='')
else:
    for i in reversed(s):
        print(i,end='')

Buggy python submission (verdict: Runtime Error):
from collections import deque
s=deque(list(input()))
q=int(input())
r = False
for i in range(q):
    tmp = list(input().split(' '))
    if tmp[0]=='1':
        r = not r
    elif (not r and tmp[1]=='1') or (r and tmp[1] =='2'):
        s.appendleft(tmp[2])
    else:
        s.append(tmp[2])
if not r:
    for i in s:
        print(i,end='')
else:
    for i in s[::-1]:
        print(i,end='')

Fixed submission:
from collections import deque
s=deque(list(input()))
q=int(input())
r = False
for i in range(q):
    tmp = list(input().split(' '))
    if tmp[0]=='1':
        r = not r
    elif (not r and tmp[1]=='1') or (r and tmp[1] =='2'):
        s.appendleft(tmp[2])
    else:
        s.append(tmp[2])
if not r:
    for i in s:
        print(i,end='')
else:
    for i in reversed(s):
        print(i,end='')

Buggy python submission (verdict: Time Limit Exceeded):
s=input()
q=int(input())
r = False
for i in range(q):
    tmp = list(input().split(' '))
    if tmp[0]=='1':
        r = not r
    elif (not r and tmp[1]=='1') or (r and tmp[1] =='2'):
        s = tmp[2]+s
    else:
        s = s + tmp[2]
if not r:
    print(s)
else:
    print(s[::-1])

Fixed submission:
from collections import deque
s=deque(list(input()))
q=int(input())
r = False
for i in range(q):
    tmp = list(input().split(' '))
    if tmp[0]=='1':
        r = not r
    elif (not r and tmp[1]=='1') or (r and tmp[1] =='2'):
        s.appendleft(tmp[2])
    else:
        s.append(tmp[2])
if not r:
    for i in s:
        print(i,end='')
else:
    for i in reversed(s):
        print(i,end='')