Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
k,n=map(int,input().split())
a=list(map(int,input().split()))

d=[]
for i in range(len(a)-1):
    d.append(abs(a[i]-a[i+1]))

d.append(k-a[-1]+a[0])
d+=d[:n-2]
ans=[]
for i in range(n):
    total=sum(d[i:i+n-1])
    ans.append(total)

print(min(ans))  

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

d=[]
for i in range(n-1):
    d.append(a[i+1]-a[i])

d.append(k-a[-1]+a[0])
d=sorted(d,reverse=True)
print(sum(d[1:]))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

n,x,y = map(int,input().split())

adj = [[] for i in range(n)]

adj[x-1].append(y-1)
adj[y-1].append(x-1)

for i in range(n-1):
    adj[i].append(i+1)
    adj[i+1].append(i)

ans = [0]*(n-1)
for i in range(n):
    q = deque([])
    q.append(i)

    dist = [-1]*n
    dist[i] = 0

    while len(q) > 0:
        v = q.popleft()
    
        for nv in adj[v]:
            if dist[nv] != -1:
                continue
        
            dist[nv] = dist[v] + 1
            q.append(nv)
    for i in dist:
        if i != 0:
            ans[i-1] += 1

for i in ans:
    print(i//2)

Fixed submission:
n,x,y=map(int,input().split())

ans=[0]*n

for i in range(1,n):
    for j in range(i+1,n+1):
        d=min(abs(j-i),abs(x-i)+1+abs(j-y))
        ans[d]+=1


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

Buggy python submission (verdict: Time Limit Exceeded):
import queue
n,x,y = map(int,input().split())

adj = [[] for i in range(n)]

adj[x-1].append(y-1)
adj[y-1].append(x-1)

for i in range(n-1):
    adj[i].append(i+1) 
    adj[i+1].append(i)
        
ans = [0 for _ in range(n+1)]

def bfs(start):
    inf = 1001001001
    q = queue.Queue()
    q.put(start)
    dist = [inf]*n
    dist[start] = 0
    
    while not q.empty():
        v = q.get()

        for i in adj[v]:
            if dist[i] == inf:
                dist[i] = dist[v] + 1
                q.put(i)

    for i in range(n):
        ans[dist[i]] += 1

for i in range(n):
    bfs(i)

for i in range(1,n):
    print(ans[i]//2)

Fixed submission:
n,x,y=map(int,input().split())

ans=[0]*n

for i in range(1,n):
    for j in range(i+1,n+1):
        d=min(abs(j-i),abs(x-i)+1+abs(j-y))
        ans[d]+=1


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

Buggy python submission (verdict: Time Limit Exceeded):
import queue
n,x,y = map(int,input().split())

adj = [[] for i in range(n)]

adj[x-1].append(y-1)
adj[y-1].append(x-1)

for i in range(n-1):
    adj[i].append(i+1) 
    adj[i+1].append(i)
        
ans = [0 for _ in range(n+1)]

def bfs(start):
    inf = 1001001001
    q = queue.Queue()
    q.put(start)
    dist = [inf]*n
    dist[start] = 0
    
    while not q.empty():
        v = q.get()

        for i in adj[v]:
            if dist[i] == inf:
                dist[i] = dist[v] + 1
                q.put(i)

    for i in range(n):
        ans[dist[i]] += 1

for i in range(n):
    bfs(i)

for i in range(1,n):
    print(ans[i]//2)

Fixed submission:
n,x,y=map(int,input().split())

ans=[0]*n

for i in range(1,n):
    for j in range(i+1,n+1):
        d=min(abs(j-i),abs(x-i)+1+abs(j-y))
        ans[d]+=1


for i in range(1,n):
    print(ans[i])
Buggy python submission (verdict: Runtime Error):
n = int(input())
 
a = list(map(int,input().split()))
 
total = 0
 
cnt = [0]*n
for i in range(n):
    cnt[a[i]] += 1
    
for i in cnt:
    if i > 0:
        total += (i*(i-1))//2
 
for i in range(n):
    ans = 0
    before = (cnt[a[i]]*(cnt[a[i]]-1))//2
    after = ((cnt[a[i]]-1)*(cnt[a[i]]-2))//2
    
    ans = total - before + after
    print(ans)

Fixed submission:
import collections

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

a=collections.Counter(A)

total=0
for v in a.values():
    if v>1:
        c=(v*(v-1))//2
        total+=c

for i in A:
    ans=total-(a[i]*(a[i]-1))//2+((a[i]-1)*(a[i]-2))//2
    print(ans)

Buggy python submission (verdict: Runtime Error):
from collections import Counter

n = int(input())

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

total = 0

cnt = [0]*n
for i in range(n):
    cnt[a[i]] += 1
    
for i in cnt:
    if i > 0:
        total += (i*(i-1))//2

for i in range(n):
    ans = 0
    before = (cnt[a[i]]*(cnt[a[i]]-1))//2
    after = ((cnt[a[i]]-1)*(cnt[a[i]]-2))//2
    
    ans = total - before + after
    print(ans)

Fixed submission:
import collections

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

a=collections.Counter(A)

total=0
for v in a.values():
    if v>1:
        c=(v*(v-1))//2
        total+=c

for i in A:
    ans=total-(a[i]*(a[i]-1))//2+((a[i]-1)*(a[i]-2))//2
    print(ans)

Buggy python submission (verdict: Runtime Error):
from collections import Counter

n = int(input())

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

total = 0

cnt = [0]*n
for i in range(n):
    cnt[a[i]] += 1
    
for i in cnt:
    total += (i*(i-1))//2

for i in range(n):
    ans = 0
    before = (cnt[a[i]]*(cnt[a[i]]-1))//2
    after = ((cnt[a[i]]-1)*(cnt[a[i]]-2))//2
    
    ans = total - before + after
    print(ans)

Fixed submission:
import collections

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

a=collections.Counter(A)

total=0
for v in a.values():
    if v>1:
        c=(v*(v-1))//2
        total+=c

for i in A:
    ans=total-(a[i]*(a[i]-1))//2+((a[i]-1)*(a[i]-2))//2
    print(ans)
Buggy python submission (verdict: Runtime Error):

if a==0:
    print(0)
elif n>a:
    print(n-b)
elif n<=a:
    print(n)


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

ans=n//(a+b)*a
r=n%(a+b)
ans+=min(r,a)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

s = input()
Q = int(input())

l = deque()
l.append(s)

rev = True
for i in range(Q):
    q = list(input().split())
    if q[0] == "1":
        rev = not rev
    else:
        if rev:
            if q[1] == "1":
                l.appendleft(q[2])
            else:
                l.append(q[2])
        else:
            if q[1] == "1":
                l.append(q[2])
            else:
                l.appendleft(q[2])

ans = ""    
for i in l:
    ans += i

if not rev:
    print(ans[::-1])
else:
    print(ans)

Fixed submission:
from collections import deque

s=input()
n=int(input())
q=deque()
q.append(s)
f=1
for i in range(n):
    t=list(input().split())
    if int(t[0])==1:
        f*=-1
    else:
        if f==1:
            if t[1]=='1' :
                q.appendleft(t[2])
            else:
                q.append(t[2])
        else:
            if t[1]=='2':
                q.appendleft(t[2])
            else:    
                q.append(t[2])
ans=''.join(q)
if f==-1:
    ans=ans[::-1]


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

b=[i//2 for i in a if i%2==0]

for j in b:
    if j%3==0 :
        ans=True
    elif j%5==0:
        ans=True
    else:
        ans=False
        break
if ans:
    print('APPROVED')
else:
    print('DENIED')


Fixed submission:
n=int(input())
a=list(map(int,input().split()))
b=[]
for i in a:
   if i%2==0:
       b.append(i)

ans=True       
for i in b:
    if i%3==0 or i%5==0:
        ans=True
    else:
        ans=False
        break
        
if ans:
    print('APPROVED')
else:
    print('DENIED')

Buggy python submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))

b=[i for i in a if i%2==0]

for j in b:
    if j%3==0 or j%5==0:
        ans=True
    else:
        ans=False
        break
if ans:
    print('APPROVED')
else:
    print('DENIED')


Fixed submission:
n=int(input())
a=list(map(int,input().split()))
b=[]
for i in a:
   if i%2==0:
       b.append(i)

ans=True       
for i in b:
    if i%3==0 or i%5==0:
        ans=True
    else:
        ans=False
        break
        
if ans:
    print('APPROVED')
else:
    print('DENIED')

Buggy python submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))

b=[i for i in a if i%2==0]

for j in b:
    if j%3==0 or j%5==0:
        ans=True
    else:
        print('DENIED')
        exit()
if ans:
    print('APPROVED')

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
b=[]
for i in a:
   if i%2==0:
       b.append(i)

ans=True       
for i in b:
    if i%3==0 or i%5==0:
        ans=True
    else:
        ans=False
        break
        
if ans:
    print('APPROVED')
else:
    print('DENIED')
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a={}

for i in range(n):
    s=input()
    if not a.get(s):
        a[s]=1
    else:
        v=a[s]
        v+=1
        a[s]=v
ans=[]
for i in a.items():
    if i[1]==max(a.values()):
        ans.append(i[0])

ans=sorted(ans)
for i in ans:
    print(i) 


Fixed submission:
import collections 

n=int(input())
a=[]
for i in range(n):
    s=input()
    a.append(s)

b=collections.Counter(a) 
mx=max(b.values())
ans=[]

for word,counts in b.items():
    if counts==mx:
        ans.append(word)
        
ans=sorted(ans)
for i in ans:
    print(i)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
a=sorted(a)
for i in a:
    if a.count(i)>1:
        print('NO')
        exit()
        
print('YES')        
        

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
b=set(a)

if len(a)==len(b):
    print('YES')
else:
    print('NO')

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

for i in a:
    if a.count(i)>1:
        print('NO')
        exit()
        
print('YES')      

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
b=set(a)

if len(a)==len(b):
    print('YES')
else:
    print('NO')
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())

p = list(map(int,input().split()))

s = [0]*n

for i in range(1,n+1):
    a = min(p[:i])
    
    s[i-1] = a

cnt = 0
for i in range(n):
    if p[i] == s[i]:
        cnt += 1
        
print(cnt)

Fixed submission:
n=int(input())
p=list(map(int,input().split()))
ans=0
a=p[0]
for i in range(n):
    if p[i] <= a:
        ans+=1
    
    a=min(a,p[i])    


print(ans)

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

p = list(map(int,input().split()))

s = [0]*n

for i in range(1,n+1):
    a = min(p[:i])
    
    s[i-1] = a

cnt = 0
for i in range(n):
    if p[i] == s[i]:
        cnt += 1
        
print(cnt)

Fixed submission:
n=int(input())
p=list(map(int,input().split()))
ans=0
a=p[0]
for i in range(n):
    if p[i] <= a:
        ans+=1
    
    a=min(a,p[i])    


print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
p=list(map(int,input().split()))
ans=0
for i in range(n):
    if p[i] <= min(p[:i+1]):
        ans+=1


print(ans)  

Fixed submission:
n=int(input())
p=list(map(int,input().split()))
ans=0
a=p[0]
for i in range(n):
    if p[i] <= a:
        ans+=1
    
    a=min(a,p[i])    


print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
p=list(map(int,input().split()))
ans=0
for i in range(n):
    if p[i] <= min(p[:i+1]):
        ans+=1


print(ans)  

Fixed submission:
n=int(input())
p=list(map(int,input().split()))
ans=0
a=p[0]
for i in range(n):
    if p[i] <= a:
        ans+=1
    
    a=min(a,p[i])    


print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import itertools 

n = int(input())

L = list(map(int,input().split()))

cnt = 0
for a,b,c in itertools.combinations(L,3):
    if a >= b+c:
        continue
    if b >= a+c:
        continue
    if c >= a+b:
        continue
    
    cnt += 1

print(cnt)   


Fixed submission:
import itertools
import bisect

n = int(input())

L = list(map(int,input().split()))

A = sorted(L)

ans = 0

for i in range(n):
    for j in range(i+1,n):
        total = L[i] + L[j]
        ans += bisect.bisect_left(A,total) - (j+1)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
import bisect

n = int(input())

L = list(map(int,input().split()))

A = sorted(L)

ans = 0

for a,b in itertools.combinations(A,2):
    total = a + b
    l = bisect.bisect(A,max(a,b))
    r = bisect.bisect_left(A,total) 
    ans += max(0,r-l)

print(ans)        


Fixed submission:
import itertools
import bisect

n = int(input())

L = list(map(int,input().split()))

A = sorted(L)

ans = 0

for i in range(n):
    for j in range(i+1,n):
        total = L[i] + L[j]
        ans += bisect.bisect_left(A,total) - (j+1)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
import bisect

n = int(input())

L = list(map(int,input().split()))

A = sorted(L)

ans = 0

for a,b in itertools.combinations(A,2):
    total = a + b
    l = bisect.bisect(A,max(a,b))
    r = bisect.bisect_left(A,total) 
    ans += max(0,r-l)

print(ans)        

Fixed submission:
import itertools
import bisect

n = int(input())

L = list(map(int,input().split()))

A = sorted(L)

ans = 0

for i in range(n):
    for j in range(i+1,n):
        total = L[i] + L[j]
        ans += bisect.bisect_left(A,total) - (j+1)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools 

n = int(input())

L = list(map(int,input().split()))

cnt = 0
for a,b,c in itertools.combinations(L,3):
    if a >= b+c:
        continue
    if b >= a+c:
        continue
    if c >= a+b:
        continue
    
    cnt += 1

print(cnt)   

Fixed submission:
import itertools
import bisect

n = int(input())

L = list(map(int,input().split()))

A = sorted(L)

ans = 0

for i in range(n):
    for j in range(i+1,n):
        total = L[i] + L[j]
        ans += bisect.bisect_left(A,total) - (j+1)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())

ans = 0
for i in range(1,n):
    ans += i

print(ans)   

Fixed submission:
n=int(input())

print(n*(n-1)//2)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
b=[]

for i in range(n):
    a=int(input())
    b.append(a)

for i in range(n):
    c=b[:i]+b[i+1:]
    print(max(c))
    

Fixed submission:
n=int(input())
b=[]

for i in range(n):
    a=int(input())
    b.append(a)
    
c=sorted(b,reverse=True)    
for i in range(n):
    if b[i]==c[0]:
        print(c[1])
    else:
        print(c[0])
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())

m=list(map(int,input().split()))

a=sorted(m)
count=0

for i in range(min(a),max(a)+1):
    b=[j for j in a if i > j]
    if len(b) == N/2:
        count +=1
          
print(count)           

Fixed submission:
N=int(input())

m=list(map(int,input().split()))

a=sorted(m)

ans=a[int(N/2)]-a[int(N/2)-1]
    
          
print(ans)

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

m=list(map(int,input().split()))

a=sorted(m)
count=0

for i in range(min(a),max(a)+1):
    b=[j for j in a if i > j]
    if len(b) == N/2:
        count +=1
          
print(count)           

Fixed submission:
N=int(input())

m=list(map(int,input().split()))

a=sorted(m)

ans=a[int(N/2)]-a[int(N/2)-1]
    
          
print(ans)
Buggy python submission (verdict: Runtime Error):
import math

def lcm(x,y):
    return (x*y)//math.gcd(x,y)

a,b,c,d=map(int,input().split())
d1=math.floor(b/c)
d2=math.floor(b/d)
d3=math.floor(b/lcm(c,d))

d4=math.floor((a-1)/c)
d5=math.floor((a-1)/d)
d6=math.floor((a-1)/lcm(c,d))

ansb=b-(d1+d2-d3)
ansa=a-1-(d1+d2-d3)
print(ansb-ansa)

Fixed submission:
import fractions

def lcm(x,y):
    return (x*y)//fractions.gcd(x,y)

a,b,c,d=map(int,input().split())
d1=b//c
d2=b//d
d3=b//lcm(c,d)

d4=(a-1)//c
d5=(a-1)//d
d6=(a-1)//lcm(c,d)

ansb=b-(d1+d2-d3)
ansa=a-1-(d4+d5-d6)
print(ansb-ansa)

Buggy python submission (verdict: Runtime Error):
import math

def lcm(x,y):
    return (x*y)//math.gcd(x,y)

def cnt(x,y,z):
    if x%z==0:
        return (y//z)-(x//z)+1
    else:
        return (y//z)-(x//z)
        
a,b,c,d=map(int,input().split())
s=lcm(c,d)
d1=cnt(a,b,c)
d2=cnt(a,b,d)
d3=cnt(a,b,s)

ans=(b-a+1)-(d1+d2-d3)
print(ans)

Fixed submission:
import fractions

def lcm(x,y):
    return (x*y)//fractions.gcd(x,y)

a,b,c,d=map(int,input().split())
d1=b//c
d2=b//d
d3=b//lcm(c,d)

d4=(a-1)//c
d5=(a-1)//d
d6=(a-1)//lcm(c,d)

ansb=b-(d1+d2-d3)
ansa=a-1-(d4+d5-d6)
print(ansb-ansa)
Buggy python submission (verdict: Runtime Error):
W,H,x,y=map(int,input().split())

s=0
if (W-x)*H >= (H-y)*W:
    s=(W-x)*H
else:
    s=(H-y)*W

if W%x==0 and H%y==0:
    print(s,"1")
else:
    print(s,"0")

Fixed submission:
W,H,x,y=map(int,input().split())

if W == x+x and H == y+y:
    print(W*H/2,1)
else:
    print(W*H/2,0)
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())

s=[0]*n

for i in range(m):
    l,r=map(int,input().split())
    x=l
    while x<=r:
        s[x-1]+=1
        x+=1
        
ans=[str(i) for i in s] 
print(ans.count(str(m)))

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

s=[0]*n
left=[]
right=[]
for i in range(m):
    l,r=map(int,input().split())
    left.append(l)
    right.append(r)
    
if min(right)<max(left):
    print(0)
else:
    print(min(right)-max(left)+1)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
def divisor(n):
    i = 1
    l = []
    while i * i <= n:
        if n%i == 0:
            l.append(i)
            l.append(n//i)
        i += 1
    l = list(set(l))
    return l   

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

arr_1=[]
for i in a:
    arr_1.append(divisor(i))

arr_2=sum(arr_1,[])
arr_3=Counter(arr_2)
ans=0
for d,c in arr_3.items():
    if c>=n-1 and d>=ans:
        ans=d
print(ans)       

Fixed submission:
from fractions import gcd

n=int(input())
a_1=list(map(int,input().split()))
a_2=list(reversed(a_1))
l=[0]
r=[0]

for i in range(n):
    l.append(gcd(l[i],a_1[i]))  

for i in range(n):    
    r.append(gcd(r[i],a_2[i]))
    
r=list(reversed(r))

m=[]
for i in range(n):
   m.append(gcd(l[i],r[i+1])) 

print(max(m))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
def divisor(n):
    i = 1
    l = []
    while i * i <= n:
        if n%i == 0:
            l.append(i)
            l.append(n//i)
        i += 1
    l = list(set(l))
    return l   

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

arr_1=[]
for i in a:
    arr_1.append(divisor(i))

arr_2=sum(arr_1,[])
arr_3=Counter(arr_2)
ans=0
for d,c in arr_3.items():
    if c>=n-1 and d>=ans:
        ans=d
print(ans)

Fixed submission:
from fractions import gcd

n=int(input())
a_1=list(map(int,input().split()))
a_2=list(reversed(a_1))
l=[0]
r=[0]

for i in range(n):
    l.append(gcd(l[i],a_1[i]))  

for i in range(n):    
    r.append(gcd(r[i],a_2[i]))
    
r=list(reversed(r))

m=[]
for i in range(n):
   m.append(gcd(l[i],r[i+1])) 

print(max(m))
Buggy python submission (verdict: Runtime Error):
l=[]
total=0
for i in range(5):
    t=int(input())
    if t%10 == 0:
        total +=t
    else:    
        total +=(t//10+1)*10
        b=(t//10+1)*10-t
        l.append(b)
a=max(l)
print(total-a)

Fixed submission:
l=[]
total=0
a=0
for i in range(5):
    t=int(input())
    if t%10 == 0:
        total +=t
    else:    
        total +=(t//10+1)*10
        a=max(a,10-(t%10))
print(total-a)

Buggy python submission (verdict: Runtime Error):
l=[]
total=0
for i in range(5):
    t=int(input())
    if t%10 == 0:
        total +=t
    else:    
        total +=(t//10+1)*10
        l.append((t//10+1)*10-t)
a=max(l)
print(total-a)

Fixed submission:
l=[]
total=0
a=0
for i in range(5):
    t=int(input())
    if t%10 == 0:
        total +=t
    else:    
        total +=(t//10+1)*10
        a=max(a,10-(t%10))
print(total-a)

Buggy python submission (verdict: Runtime Error):
l=[]
total=0
for i in range(5):
    t=int(input())
    if t%10 !=0:
        total +=(t+9)//10*10
        l.append((t+9)//10*10-t)
    else:
        total +=t
a=max(l)
print(total-a)

Fixed submission:
l=[]
total=0
a=0
for i in range(5):
    t=int(input())
    if t%10 == 0:
        total +=t
    else:    
        total +=(t//10+1)*10
        a=max(a,10-(t%10))
print(total-a)

Buggy python submission (verdict: Runtime Error):
l=[]
max=0
total=0
for i in range(5):
    t=int(input())
    if t%10 !=0:
        total +=((t//10)+1)*10
        l.append(t)
    else:
        total +=t
a=min(l,key=lambda x:x%10)

print(total-(10-a%10))

Fixed submission:
l=[]
total=0
a=0
for i in range(5):
    t=int(input())
    if t%10 == 0:
        total +=t
    else:    
        total +=(t//10+1)*10
        a=max(a,10-(t%10))
print(total-a)
Buggy python submission (verdict: Runtime Error):
n,Q=map(int,input().split())
s=input()

a=[0]*(n+1)
for i in range(n):
    if s[i]=='A' and s[i+1]=='C':
        a[i+1]=a[i]+1
    else:
        a[i+1]=a[i]

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

Fixed submission:
n,Q=map(int,input().split())
s=input()

a=[0]*(n+1)
for i in range(2,n+1):
    if s[i-2]=='A' and s[i-1]=='C':
        a[i]=a[i-1]+1
    else:
        a[i]=a[i-1]

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

Buggy python submission (verdict: Runtime Error):
n,Q=map(int,input().split())
s=input()

a=[0]*(n+1)
for i in range(n):
    if s[i]=='A' and s[i+1]=='C':
        a[i+1]=a[i]+1
    else:
        a[i+1]=a[i]

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

Fixed submission:
n,Q=map(int,input().split())
s=input()

a=[0]*(n+1)
for i in range(2,n+1):
    if s[i-2]=='A' and s[i-1]=='C':
        a[i]=a[i-1]+1
    else:
        a[i]=a[i-1]

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

Buggy python submission (verdict: Runtime Error):
n,Q=map(int,input().split())
s=input()

a=['']*(n+1)
for i in range(n):
    a[i+1]=a[i]+s[i]    

for i in range(Q):
    l,r=map(int,input().split())
    q=a[r][l-1:]
    print(q.count('AC'))

Fixed submission:
n,Q=map(int,input().split())
s=input()

a=[0]*(n+1)
for i in range(2,n+1):
    if s[i-2]=='A' and s[i-1]=='C':
        a[i]=a[i-1]+1
    else:
        a[i]=a[i-1]

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

Buggy python submission (verdict: Time Limit Exceeded):
n,Q=map(int,input().split())
s=input()

for i in range(Q):
    l,r=map(int,input().split())
    q=s[l-1:r]
    print(q.count('AC'))

Fixed submission:
n,Q=map(int,input().split())
s=input()

a=[0]*(n+1)
for i in range(2,n+1):
    if s[i-2]=='A' and s[i-1]=='C':
        a[i]=a[i-1]+1
    else:
        a[i]=a[i-1]

for i in range(Q):
    l,r=map(int,input().split())
    print(a[r]-a[l])
Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())

h = list(map(int,input().split()))

INF = 100100100100100
dp = [INF]*N

dp[0] = 0

for i in range(1,N):
    for k in range(1,K+1):
        if i < k:
            break
        dp[i] = min(dp[i], dp[i-k] + abs(h[i] - h[i-k]))
        
print(dp[N-1])

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

h = list(map(int,input().split()))

INF = 100100100100100
dp = [INF]*N

dp[0] = 0

for i in range(1,N):
    for k in range(1,K+1):
        if i < k:
            break
        dp[i] = min(dp[i], dp[i-k] + abs(h[i] - h[i-k]))
        
print(dp[N-1])

Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())

h = list(map(int,input().split()))

INF = 100100100100100
dp = [INF]*N

dp[0] = 0

for i in range(1,N):
    for k in range(1,K+1):
        if i >= k:
            dp[i] = min(dp[i], dp[i-k] + abs(h[i] - h[i-k]))
        
print(dp[N-1])

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

h = list(map(int,input().split()))

INF = 100100100100100
dp = [INF]*N

dp[0] = 0

for i in range(1,N):
    for k in range(1,K+1):
        if i < k:
            break
        dp[i] = min(dp[i], dp[i-k] + abs(h[i] - h[i-k]))
        
print(dp[N-1])
Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
a=[]

for i in range(N):
    b=int(input())
    a.append(b)

a=sorted(a)


min=a[K-1]-a[0]
for j in range(N-K+1):
    s=a[j:j+K]
    
    if min >= s[K-1]-s[0]:
        min=s[K-1]-s[0]
        
print(min)      

Fixed submission:
N,K=map(int,input().split())
a=[]

for i in range(N):
    b=int(input())
    a.append(b)

a=sorted(a)

b=[]
for j in range(N-K+1):
    c=a[j+K-1]-a[j]
    b.append(c)    
        
print(min(b))