Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()

def solve(SS):
	n = len(SS)
	Z = [0] * n
	i, j = 1, 0
	while i < n:
		while (i + j < n) and (j < i) and (SS[j] == SS[i + j]):
			j += 1
		Z[i] = j
		if j == 0:
			i += 1
			continue
		else:
			k = 1
			while (i + k < n) and (k + Z[k] < j):
				Z[i + k] = Z[k]
				k += 1
			i += k
			j -= k

	return max(Z)

ans = 0
for i in range(N):
	ans = max(ans, solve(S[i:]))

print(ans)

Fixed submission:
N = int(input())
S = input()

def solve(SS):
	n = len(SS)
	Z = [0] * n
	Z[0] = n
	i, j = 1, 0
	while i < n:
		while (i + j < n) and (SS[j] == SS[i + j]):
			j += 1
		Z[i] = j
		if j == 0:
			i += 1
			continue
		else:
			k = 1
			while (i + k < n) and (k + Z[k] < j):
				Z[i + k] = Z[k]
				k += 1
			i += k
			j -= k

	out = 0
	for i in range(n):
		tmp = min(Z[i], i)
		out = max(out, tmp)
	return out

ans = 0
for i in range(N):
	ans = max(ans, solve(S[i:]))

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()

ans = 0
for i in range(N//2+1):
	for j in range(i+1, N//2+2):
		s = S[i:j]

		if s in S[j:]:
			ans = max(len(s), ans)

print(ans)

Fixed submission:
N = int(input())
S = input()

def solve(SS):
	n = len(SS)
	Z = [0] * n
	Z[0] = n
	i, j = 1, 0
	while i < n:
		while (i + j < n) and (SS[j] == SS[i + j]):
			j += 1
		Z[i] = j
		if j == 0:
			i += 1
			continue
		else:
			k = 1
			while (i + k < n) and (k + Z[k] < j):
				Z[i + k] = Z[k]
				k += 1
			i += k
			j -= k

	out = 0
	for i in range(n):
		tmp = min(Z[i], i)
		out = max(out, tmp)
	return out

ans = 0
for i in range(N):
	ans = max(ans, solve(S[i:]))

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()

ans = 0
for i in range(N//2+1):
	for j in range(i+1, N//2+2):
		s = S[i:j]

		if s in S[j:]:
			ans = max(len(s), ans)

print(ans)

Fixed submission:
N = int(input())
S = input()

def solve(SS):
	n = len(SS)
	Z = [0] * n
	Z[0] = n
	i, j = 1, 0
	while i < n:
		while (i + j < n) and (SS[j] == SS[i + j]):
			j += 1
		Z[i] = j
		if j == 0:
			i += 1
			continue
		else:
			k = 1
			while (i + k < n) and (k + Z[k] < j):
				Z[i + k] = Z[k]
				k += 1
			i += k
			j -= k

	out = 0
	for i in range(n):
		tmp = min(Z[i], i)
		out = max(out, tmp)
	return out

ans = 0
for i in range(N):
	ans = max(ans, solve(S[i:]))

print(ans)
Buggy python submission (verdict: Runtime Error):
N=int(input())
A=list(map(int,input().split()))

B=[]
for i in range(N-1):
    B.append(min(A[i],A[i+1]))
B.append(A[-1])

print(sum(B))

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

A = []

for i in range(N):
	if i == 0:
		A.append(B[0])
	elif 1 <= i <= N-2:
		A.append(min(B[i],B[i-1]))
	else:
		A.append(B[-1])

print(sum(A))
Buggy python submission (verdict: Time Limit Exceeded):
import collections as c
n = int(input())
s = [sorted(input()) for _ in range(n)]

cnt = 0
for i in range(n-1):
    for j in range(i+1,n):
        if s[i] == s[j]:
            cnt += 1

print(cnt)

Fixed submission:
import collections as c

N = int(input())
S = sorted(["".join(sorted(input())) for _ in range(N)])

D = c.Counter(S)

D_value = []

for a in D.values():
	D_value.append(a)

ans = 0

for i in D_value:
	if i == 0:
		continue
	ans += (i * (i-1)) // 2

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import collections as c
n = int(input())
s = [input() for _ in range(n)]

ans = []
for i in range(n):
    ans.append(c.Counter(s[i]))

cnt = 0
for i in range(n-1):
    for j in range(i+1,n):
        if ans[i] == ans[j]:
            cnt += 1

print(cnt)

Fixed submission:
import collections as c

N = int(input())
S = sorted(["".join(sorted(input())) for _ in range(N)])

D = c.Counter(S)

D_value = []

for a in D.values():
	D_value.append(a)

ans = 0

for i in D_value:
	if i == 0:
		continue
	ans += (i * (i-1)) // 2

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = [input() for _ in range(n)]

ans = [[0]*26 for _ in range(n)]
for i in range(n):
    for j in range(97,123):
        ans[i][j-97] = s[i].count(chr(j))


cnt = 0
for i in range(n-1):
    for j in range(i+1,n):
        if ans[i] == ans[j]:
            cnt += 1

print(cnt)

Fixed submission:
import collections as c

N = int(input())
S = sorted(["".join(sorted(input())) for _ in range(N)])

D = c.Counter(S)

D_value = []

for a in D.values():
	D_value.append(a)

ans = 0

for i in D_value:
	if i == 0:
		continue
	ans += (i * (i-1)) // 2

print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
n = int(input())
h = list(map(int, input().split()))

for i in range(n-1):
    if h[i] > h[i+1] + 1:
        print("No")
        sys.exit()
    
    elif h[i] == h[i+1] + 1 and h[i+1] > h[i+2]:
        print("No")
        sys.exit()

print("Yes")

Fixed submission:
import sys
n = int(input())
h = list(map(int, input().split()))[::-1]

for i in range(1,n):
    if h[i] > h[i-1] + 1:
        print("No")
        sys.exit()
    elif h[i] == h[i-1] + 1:
        h[i] -= 1




print("Yes")
Buggy python submission (verdict: Runtime Error):
import collections as c
import sys

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

A = c.Counter(a)

if list(A.keys()) == [0]:
	print("Yes")
	sys.exit()

if len(A.keys()) == 2:
	if 0 not in A.keys():
		print("No")
		sys.exit()
	else:
		if A.values()[0]*2 == A.values()[1]:
			print("Yes")
			sys.exit()
		else:
			print("No")
			sys.exit()

if len(A.keys()) != 3:
	print("No")
	sys.exit()

x,y,z = A.keys()
if x^y != z:
	print("No")
	sys.exit()

x,y,z = A.values()
if x == y == z:
	print("Yes")
else:
	print("No")

Fixed submission:
import collections as c
import sys

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

A = c.Counter(a)

if list(A.keys()) == [0]:
	print("Yes")
	sys.exit()

if len(A.keys()) == 2:
	if 0 not in A.keys():
		print("No")
		sys.exit()
	else:
		if list(A.values())[0]*2 == list(A.values())[1]:
			print("Yes")
			sys.exit()
		else:
			print("No")
			sys.exit()

if len(A.keys()) != 3:
	print("No")
	sys.exit()

x,y,z = A.keys()
if x^y != z:
	print("No")
	sys.exit()

x,y,z = A.values()
if x == y == z:
	print("Yes")
else:
	print("No")
Buggy python submission (verdict: Runtime Error):
n,a,b = map(int,input().split())
print(min([n*a,b]) 

Fixed submission:
n,a,b = map(int,input().split())
print(min([n*a,b]))

Buggy python submission (verdict: Runtime Error):
a,b,n = map(int,input().split())
print(min([n*a,b])

Fixed submission:
n,a,b = map(int,input().split())
print(min([n*a,b]))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
aa = a+a
g = sum(a)//2
ans = []
for i in range(n):
    temp = sum([aa[i+1+j*2] for j in range(n//2)])
    ans.append(g-temp)
for k in ans:
    print(2*k,end=" ")
        

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
aa = a+a
g = sum(a)//2
ans = []
for i in range(1):
    temp = sum([aa[i+1+j*2] for j in range(n//2)])
    ans.append(g-temp)
temp = ans[0]
for i in range(1,n):
    temp = a[i-1] - temp
    ans.append(temp)
for k in ans:
    print(2*k,end=" ")

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
aa = []
for s in a:
    aa.append(s)
for s in a:
    aa.append(s)
g = sum(a)//2
ans = []
for i in range(n):
    temp = sum([aa[i+1+j*2] for j in range(n//2)])
    ans.append(g-temp)
for k in ans:
    print(2*k,end=" ")
        

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
aa = a+a
g = sum(a)//2
ans = []
for i in range(1):
    temp = sum([aa[i+1+j*2] for j in range(n//2)])
    ans.append(g-temp)
temp = ans[0]
for i in range(1,n):
    temp = a[i-1] - temp
    ans.append(temp)
for k in ans:
    print(2*k,end=" ")
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int ,input().split())
mod = 10**9+7
B = K
R = N-K

def nCk_mod(n,k,mod):
	if n < k:
		return 1
	out = 1
	for i in range(n-k+1,n+1):
		out *= i
		out %= mod
	for i in range(1,k+1):
		out *= pow(i,mod-2,mod)
		out %= mod

	return out

ans = []

for i in range(1,B+1):
	if R < i-1:
		ans.append(0)
		continue
	s_1 = nCk_mod(B-1,i-1,mod)
	s_2 = nCk_mod(R+1, i, mod)

	ans.append((s_1*s_2)%mod)

for a in ans:
    print(a, end=" ")
print()

Fixed submission:
N, K = map(int ,input().split())
mod = 10**9+7
B = K
R = N-K

def nCk_mod(n,k,mod):
	if n < k:
		return 1
	out = 1
	for i in range(n-k+1,n+1):
		out *= i
		out %= mod
	for i in range(1,k+1):
		out *= pow(i,mod-2,mod)
		out %= mod

	return out

ans = []

for i in range(1,B+1):
	if R < i-1:
		ans.append(0)
		continue
	s_1 = nCk_mod(B-1,i-1,mod)
	s_2 = nCk_mod(R+1, i, mod)

	ans.append((s_1*s_2)%mod)

for a in ans:
    print(a, end=" ")
print()
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
job = [list(map(int, input().split())) for _ in range(N)]
job.sort(key = lambda x: x[1])

cond = True
cnt = 0
tmp = 0
for i in range(N):
	c,d = job.pop(0)
	cnt += (d - tmp)
	cnt -= c
	if cnt < 0:
		cond = False
		break
	tmp = d

if cond:
	print("Yes")
else:
	print("No")



Fixed submission:
import heapq
N = int(input())
q = []
for _ in range(N):
	at,bt = map(int,input().split())
	heapq.heappush(q,[bt,at])

cond = True
cnt = 0
tmp = 0
for _ in range(N):
	d,c = heapq.heappop(q)
	cnt += (d - tmp)
	cnt -= c
	if cnt < 0:
		cond = False
		break
	tmp = d

if cond:
	print("Yes")
else:
	print("No")

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
job = [list(map(int, input().split())) for _ in range(N)]
job.sort(key = lambda x: x[1])

cond = True
cnt = 0
tmp = 0
for i in range(N):
	c,d = job.pop(0)
	cnt += (d - tmp)
	cnt -= c
	if cnt < 0:
		cond = False
		break
	tmp = d

if cond:
	print("Yes")
else:
	print("No")



Fixed submission:
import heapq
N = int(input())
q = []
for _ in range(N):
	at,bt = map(int,input().split())
	heapq.heappush(q,[bt,at])

cond = True
cnt = 0
tmp = 0
for _ in range(N):
	d,c = heapq.heappop(q)
	cnt += (d - tmp)
	cnt -= c
	if cnt < 0:
		cond = False
		break
	tmp = d

if cond:
	print("Yes")
else:
	print("No")
Buggy python submission (verdict: Time Limit Exceeded):
H, W = map(int, input().split())
S = [input() for _ in range(H)]

def solve(i,j):
	if S[i][j] == "#":
		return 0
	cnt = 1
	tmp = j
	while True:
		tmp -= 1
		if tmp < 0:
			break
		if S[i][tmp] == "#":
			break
		cnt += 1
	tmp = j
	while True:
		tmp += 1
		if tmp >= W:
			break
		if S[i][tmp] == "#":
			break
		cnt += 1
	tmp = i
	while True:
		tmp -= 1
		if tmp < 0:
			break
		if S[tmp][j] == "#":
			break
		cnt += 1
	tmp = i
	while True:
		tmp += 1
		if tmp >= H:
			break
		if S[tmp][j] == "#":
			break
		cnt += 1

	return cnt
		
ans = 0
for i in range(H):
	for j in range(W):
		ans = max(ans, solve(i,j))

print(ans)

Fixed submission:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

H,W = map(int, readline().split())
grid = np.frombuffer(read(), 'S1').reshape(H,-1)[:,:W]

X,Y = np.where(grid == b'#')

A = np.ones((H,W), np.int32)
B = np.ones((H,W), np.int32)

A[X,Y] = 0
B[X,Y] = 0

for w in range(W-1):
	A[:,w+1] += A[:,w] * (A[:,w+1] != 0)
for w in range(W-2,-1,-1):
	A[:,w] = np.maximum(A[:,w], A[:,w+1]) * (A[:,w] != 0)


for h in range(H-1):
	B[h+1,:] += B[h,:] * (B[h+1,:] != 0)
for h in range(H-2,-1,-1):
	B[h,:] = np.maximum(B[h,:], B[h+1,:]) * (B[h,:] != 0)

C = A+B

print(np.max(C)-1)

Buggy python submission (verdict: Time Limit Exceeded):
H, W = map(int, input().split())
S = [input() for _ in range(H)]

def solve(i,j):
	if S[i][j] == "#":
		return 0
	cnt = 1
	tmp = j
	while True:
		tmp -= 1
		if tmp < 0:
			break
		if S[i][tmp] == "#":
			break
		cnt += 1
	tmp = j
	while True:
		tmp += 1
		if tmp >= W:
			break
		if S[i][tmp] == "#":
			break
		cnt += 1
	tmp = i
	while True:
		tmp -= 1
		if tmp < 0:
			break
		if S[tmp][j] == "#":
			break
		cnt += 1
	tmp = i
	while True:
		tmp += 1
		if tmp >= H:
			break
		if S[tmp][j] == "#":
			break
		cnt += 1

	return cnt
		
ans = 0
for i in range(H):
	for j in range(W):
		ans = max(ans, solve(i,j))

print(ans)

Fixed submission:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

H,W = map(int, readline().split())
grid = np.frombuffer(read(), 'S1').reshape(H,-1)[:,:W]

X,Y = np.where(grid == b'#')

A = np.ones((H,W), np.int32)
B = np.ones((H,W), np.int32)

A[X,Y] = 0
B[X,Y] = 0

for w in range(W-1):
	A[:,w+1] += A[:,w] * (A[:,w+1] != 0)
for w in range(W-2,-1,-1):
	A[:,w] = np.maximum(A[:,w], A[:,w+1]) * (A[:,w] != 0)


for h in range(H-1):
	B[h+1,:] += B[h,:] * (B[h+1,:] != 0)
for h in range(H-2,-1,-1):
	B[h,:] = np.maximum(B[h,:], B[h+1,:]) * (B[h,:] != 0)

C = A+B

print(np.max(C)-1)
Buggy python submission (verdict: Runtime Error):
n = int(input())
book=[]
for i in range(n):
    a,b=input().split()
    temp=[a,int(b),i+1]
    book.append(temp)

book.sort(key=lambda x:x[0])
book.sort(key=lambda x:x[1])

for j in range[len(book)]:
    print(book[j][3])

Fixed submission:
a, p = map(int, input().split())

print(((a * 3) + p) // 2)
Buggy python submission (verdict: Runtime Error):
n = int(input())
book=[]
for i in range(n):
    a,b=input().split()
    temp=[a,int(b),i+1]
    book.append(temp)

book.reverse(key = lambda x:x[1])
book.sort(key = lambda x:x[0])

for j in range(len(book)):
    print(book[j][2])

Fixed submission:
n = int(input())
l = [input().split()+[i+1] for i in range(n)]
for i in range(n):
    l[i][1] = int(l[i][1])
l = sorted(l, key=lambda x : x[1], reverse=True)
l = sorted(l, key=lambda x : x[0])
for i in range(n):
    print(l[i][2])

Buggy python submission (verdict: Runtime Error):
n = int(input())
book=[]
for i in range(n):
    a,b=input().split()
    temp=[a,int(b),i+1]
    book.append(temp)

book.reverse(key = lambda x:x[1])
book.sort(key = lambda x:x[0])

for j in range(len(book)):
    print(book[j][2])


Fixed submission:
n = int(input())
l = [input().split()+[i+1] for i in range(n)]
for i in range(n):
    l[i][1] = int(l[i][1])
l = sorted(l, key=lambda x : x[1], reverse=True)
l = sorted(l, key=lambda x : x[0])
for i in range(n):
    print(l[i][2])

Buggy python submission (verdict: Runtime Error):
n = int(input())
book=[]
for i in range(n):
    a,b=input().split()
    temp=[a,int(b),i+1]
    book.append(temp)

book.sort(key = lambda x:x[1], reverce = True)
book.sort(key = lambda x:x[0])

for j in range(len(book)):
    print(book[j][2])

Fixed submission:
n = int(input())
l = [input().split()+[i+1] for i in range(n)]
for i in range(n):
    l[i][1] = int(l[i][1])
l = sorted(l, key=lambda x : x[1], reverse=True)
l = sorted(l, key=lambda x : x[0])
for i in range(n):
    print(l[i][2])

Buggy python submission (verdict: Runtime Error):
n = int(input())
book=[]
for i in range(n):
    a,b=input().split()
    temp=[a,int(b),i+1]
    book.append(temp)

book.sort(key = lambda x:x[1])
book.sort(key = lambda x:x[0])

for j in range(len(book)):
    print(book[j][3])

Fixed submission:
n = int(input())
l = [input().split()+[i+1] for i in range(n)]
for i in range(n):
    l[i][1] = int(l[i][1])
l = sorted(l, key=lambda x : x[1], reverse=True)
l = sorted(l, key=lambda x : x[0])
for i in range(n):
    print(l[i][2])

Buggy python submission (verdict: Runtime Error):
n = int(input())
book=[]
for i in range(n):
    a,b=input().split()
    temp=[a,int(b),i+1]
    book.append(temp)

book.sort(key=lambda x:x[0])
book.sort(key=lambda x:x[1])

for j in range[len(book)]:
    print(book[j][3])

Fixed submission:
n = int(input())
l = [input().split()+[i+1] for i in range(n)]
for i in range(n):
    l[i][1] = int(l[i][1])
l = sorted(l, key=lambda x : x[1], reverse=True)
l = sorted(l, key=lambda x : x[0])
for i in range(n):
    print(l[i][2])

Buggy python submission (verdict: Runtime Error):
n = int(input())
book=[]
for i in range(n):
    a,b=input().split()
    temp=[a,int(b),i+1]
    book.append(temp)

book.sort(key=lambda x:x[0])
book.sort(key=lambda x:x[1])

for j in range[len(book)]:
    print(book[j][3])

Fixed submission:
n = int(input())
l = [input().split()+[i+1] for i in range(n)]
for i in range(n):
    l[i][1] = int(l[i][1])
l = sorted(l, key=lambda x : x[1], reverse=True)
l = sorted(l, key=lambda x : x[0])
for i in range(n):
    print(l[i][2])
Buggy python submission (verdict: Runtime Error):
d=input()
a,b=map([d[:2],d[2:]])
temp=[]
for i in [a,b]:
    if 1 <= i <=12:
        temp.append(2)
    elif 0 <= i <= 99:
        temp.append(1)
    else:
        temp.append(0)

if sum(temp) == 4:
    print('AMBIGUOUS')
elif sum(temp) == 3:
    if temp[0]==2:
        print('MMYY')
    else:
        print('YYMM')
else:
    print('NA')

Fixed submission:
d=input()
a,b=map(int, [d[:2],d[2:]])
temp=[]
for i in [a,b]:
    if 1 <= i <=12:
        temp.append(2)
    elif 0 <= i <= 99:
        temp.append(1)
    else:
        temp.append(0)

if sum(temp) == 4:
    print('AMBIGUOUS')
elif sum(temp) == 3:
    if temp[0]==2:
        print('MMYY')
    else:
        print('YYMM')
else:
    print('NA')
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)

N = int(input())
u = []
v = []
w = []
for _ in range(N-1):
	tu, tv, tw = map(int ,input().split())
	u.append(tu)
	v.append(tv)
	w.append(tw)

inf = float("inf")
E = [[inf for _ in range(N+1)] for _ in range(N+1)]
for i in range(N-1):
	t = w[i] % 2
	E[u[i]][v[i]] = t
	E[v[i]][u[i]] = t

flg = [inf for _ in range(N+1)]
flg[0] = 0

def dfs(q):
	cp = q.pop()
	next = [i for i in range(1,N+1) if E[cp][i] != inf]

	for np in next:
		if flg[np] == inf:
			if E[cp][np] == 0:
				flg[np] = flg[cp]
			else:
				flg[np] = flg[cp] * (-1)

			q.append(np)
	if len(q) == 0:
		return

	dfs(q)

flg[1] = 1
dfs([1])

for i in range(1,N+1):
	if flg[i] == 1:
		print(1)
	else:
		print(0)


Fixed submission:
import sys
sys.setrecursionlimit(10**7)

N = int(input())
u = []
v = []
w = []
for _ in range(N-1):
	tu, tv, tw = map(int ,input().split())
	u.append(tu)
	v.append(tv)
	w.append(tw)

inf = float("inf")
E = [[] for _ in range(N+1)]
for i in range(N-1):
	if w[i] % 2 == 0:
		E[u[i]].append(v[i])
		E[v[i]].append(u[i])
	else:
		E[u[i]].append(v[i] * (-1))
		E[v[i]].append(u[i] * (-1))

flg = [inf for _ in range(N+1)]
flg[0] = 0

def dfs(q):
	cp = q.pop()
	next = E[cp]

	for np in next:
		if flg[abs(np)] == inf:
			if np > 0:
				flg[abs(np)] = flg[cp]
			else:
				flg[abs(np)] = flg[cp] * (-1)
			q.append(abs(np))

	if len(q) == 0:
		return

	dfs(q)

flg[1] = 1
dfs([1])

for i in range(1,N+1):
	if flg[i] == 1:
		print(1)
	else:
		print(0)
Buggy python submission (verdict: Time Limit Exceeded):
R,G,B,N = map(int, input().split())
cnt = 0
for r in range((N+R)//R):
	for g in range((N+G)//G):
		b = (N-(R*r+G*g))/B
		if b >= 0 and b%1==0:
			cnt += 1
print(cnt)

Fixed submission:
def solve():
    R,G,B,N=map(int,input().split())
    ans=0
    for i in range(N+1):
        for j in range(N+1):
            tmp=N-R*i-G*j
            if tmp>=0 and tmp%B==0:
                ans+=1
    print(ans)

solve()
Buggy python submission (verdict: Runtime Error):
import sys
N = int(sys.stdin.readline())
S = list(map(str,sys.stdin.read().rstrip().split("\n")))

ans = 0
A = 0
B = 0
BA = 0
for s in S:
	ans += s.count('AB')
	if  s[0] == 'B' and s[-1] == 'A':
		BA += 1
	elif s[0] == 'B':
		B += 1
	elif s[-1] == 'A':
		A += 1


if A+B >= BA:
	ans += BA
	BA = 0
else:
	ans += A+B
	BA -= A+B

if A >= B:
	ans += B
	C = A - B
else:
	ans += A
	C = B - A

if BA > 0:
	if C >= BA:
		ans += BA
	else:
		s,t = divmod(BA,C)
		ans += s*C
		ans += t//2


print(ans)

Fixed submission:
import sys
N = int(sys.stdin.readline())
S = list(map(str,sys.stdin.read().rstrip().split("\n")))

ans = 0
A = 0
B = 0
BA = 0
for s in S:
	ans += s.count('AB')
	if  s[0] == 'B' and s[-1] == 'A':
		BA += 1
		continue
	elif s[0] == 'B':
		B += 1
	elif s[-1] == 'A':
		A += 1

if BA == 0:
	ans += min(A,B)
else:
	if A+B > 0:
		ans += BA + min(A,B)
	else:
		ans += BA-1

print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))


def check(num):
	cnt = 0
	cond = True

	for i in range(N):
		if A[i] % num != 0:
			cnt += 1
		if cnt > 1:
			cond = False
			break

	return cond

def BinarySearch(s,l):
	if s == l:
		return s
	if s+1 == l:
		if check(l):
			return l
		elif check(s):
			return s

	center = s + (l-s)//2
	
	if check(center):
		return BinarySearch(center, l)
	else:
		return BinarySearch(s, center-1)

print(BinarySearch(0, max(A))

Fixed submission:
import math

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

def division_enumeration(num):
	ans = []
	d = math.floor(float(num)**(1/2))
	for i in range(1,d+1):
		if num % i == 0:
			ans.append(i)
			ans.append(num//i)

	return ans

trgs = sorted(set(division_enumeration(A[0]) + division_enumeration(A[1])), reverse = True)

for trg in trgs:
	cnt = 0
	cond = True
	for i in range(N):
		if A[i] % trg != 0:
			cnt += 1
			if cnt > 1:
				cond = False
				break
	if not cond:
		continue
	
	ans = trg
	break

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,q = map(int, input().split())
s = input()
l = [list(map(int, input().split())) for _ in range(q)]
ind = []
for i in range(len(s)-1):
    if s[i] == "A" and s[i+1] == "C":
        ind.append(i+1)

for ll in l:
    print(len([j for j in ind if ll[0] <= j < ll[1]]))

Fixed submission:
N, q = map(int, input().split())
S = input()
Q = [list(map(int ,input().split())) for _ in range(q)]

cnt = [0] * (N+1)
tmp = S[0]
for i in range(2,N+1):
	if tmp == "A" and S[i-1] == "C":
		cnt[i] = cnt[i-1] + 1
	else:
		cnt[i] = cnt[i-1]

	tmp = S[i-1]

for l,r in Q:
	ans = cnt[r] - cnt[l-1]

	if S[l-2] == "A" and S[l-1] == "C":
		ans -= 1

	print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int,input().split()))

def solve(l, ans):
	if l == []:
		return ans

	cnd = [] 
	for i in range(len(l)):
		if l[i] == i+1:
			cnd.append(i)

	if cnd == []:
		return 0

	for ind in cnd:
		ans.append(ind+1)
		cond = solve(l[0:ind] + l[(ind+1):(len(l)+1)], ans)
		if cond == 0:
			ans.pop()
			continue
		else:
			return cond


	return 0	

ans = solve(a,[])

if ans == 0:
	print(-1)
else:
	for A in ans[::-1]:
		print(A)

Fixed submission:
n = int(input())
B = list(map(int, input().split()))

ans = []

for i in range(n):
    for j in range(len(B)-1, -1, -1):
        if B[j] == j+1:
            ans.append(B.pop(j))
            break
    else:
        print(-1)
        break
else:
    for a in ans[::-1]:
        print(a)
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
s = input()

print(s[:k-1] + s[k-1].lower() + s[k:n])

Fixed submission:
H, W = map(int, input().split())
h, w = map(int, input().split())

print((H - h) * (W - w))
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
x = sorted(list(map(int, input().split())))
xx = sorted([x[i+1] - x[i] for i in range(m-1)])

for i in range(n-1):
    xx.pop()

ans = sum(xx)
print(ans)



Fixed submission:
n, m = map(int, input().split())
x = sorted(list(map(int, input().split())))
xx = sorted([x[i+1] - x[i] for i in range(m-1)])

for i in range(n-1):
    if len(xx) == 0:
        break
    xx.pop()

ans = sum(xx)
print(ans)
Buggy python submission (verdict: Runtime Error):
a, b, c = map(int, input(),split())

print(int((a*b)/2))

Fixed submission:
a, b, c = map(int, input().split())

print((a*b)//2)

Buggy python submission (verdict: Runtime Error):
a, b, c = map(int, input(),split())

print((a*b)//2)

Fixed submission:
a, b, c = map(int, input().split())

print((a*b)//2)