Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):


def gcd(x,y):
    x, y = max(x,y), min(x,y)
    while x!=y :
        x, y = max(x,y), min(x,y)
        x -= y
    return x
#print(gcd(4,8))

a,b,c,d = map(int,input().split())
c_ok = b//c - (a-1)//c
d_ok = b//d - (a-1)//d

cd = int(c*d/gcd(c,d))
cd_ok = b//cd - (a-1)//cd

print(int(b-a+1-c_ok-d_ok+cd_ok))

Fixed submission:


def gcd(x,y):
    x, y = max(x,y), min(x,y)
    while x!=0 :
        x, y = max(x,y), min(x,y)
        x %= y
    return y
#print(gcd(4,8))

a,b,c,d = map(int,input().split())
c_ok = b//c - (a-1)//c
d_ok = b//d - (a-1)//d

cd = int(c*d/gcd(c,d))
cd_ok = b//cd - (a-1)//cd

print(int(b-a+1-c_ok-d_ok+cd_ok))

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

a,b,c,d = map(int,input().split())
c_ok = b//c - (a-1)//c
d_ok = b//d - (a-1)//d

cd = int(c*d/math.gcd(c,d))
cd_ok = b//cd - (a-1)//cd

print(int(b-a+1-c_ok-d_ok+cd_ok))

Fixed submission:


def gcd(x,y):
    x, y = max(x,y), min(x,y)
    while x!=0 :
        x, y = max(x,y), min(x,y)
        x %= y
    return y
#print(gcd(4,8))

a,b,c,d = map(int,input().split())
c_ok = b//c - (a-1)//c
d_ok = b//d - (a-1)//d

cd = int(c*d/gcd(c,d))
cd_ok = b//cd - (a-1)//cd

print(int(b-a+1-c_ok-d_ok+cd_ok))

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

a,b,c,d = map(int,input().split())
c_ok = b//c - (a-1)//c
d_ok = b//d - (a-1)//d

cd = int(c*d/math.gcd(c,d))
cd_ok = b//cd - (a-1)//cd

print(int(b-a+1-c_ok-d_ok+cd_ok))

Fixed submission:


def gcd(x,y):
    x, y = max(x,y), min(x,y)
    while x!=0 :
        x, y = max(x,y), min(x,y)
        x %= y
    return y
#print(gcd(4,8))

a,b,c,d = map(int,input().split())
c_ok = b//c - (a-1)//c
d_ok = b//d - (a-1)//d

cd = int(c*d/gcd(c,d))
cd_ok = b//cd - (a-1)//cd

print(int(b-a+1-c_ok-d_ok+cd_ok))
Buggy python submission (verdict: Runtime Error):
n = int(input())
A = [list(map(int,input().split())) for i in range(n)]

# B = [[[0, 0] for i in range(n)] for j in range(n)]
D = {}
for i in range(n):
    for j in range(i+1, n):
        dy = A[i][1] - A[j][1]
        dx = A[i][0] - A[j][0]
        try:
            D[(dx, dy)] += 1
        except:
            D[(dx, dy)] = 1

ans = n - max(list(D.values()))
print(ans)

Fixed submission:
n = int(input())
A = [list(map(int,input().split())) for i in range(n)]

# B = [[[0, 0] for i in range(n)] for j in range(n)]
if n == 1:
    print(1)
else:

    D = {}
    for i in range(n):
        for j in range(n):
            if i != j:
                dy = A[i][1] - A[j][1]
                dx = A[i][0] - A[j][0]
                try:
                    D[(dx, dy)] += 1
                except:
                    D[(dx, dy)] = 1
    # print(D)
    ans = n - max(list(D.values()))
    print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int,input().split()))

a, b = max(A), min(A)
for t in [a, b]:
    for i in range(len(A)):
        if A[i] == t:
            A.pop(i)

ans = a-b
for i in range(n-2):
    ans += abs(A[i])
print(ans)

for i in range(n-2):
    if A[i] > 0:
        print(b, A[i])
        b -= A[i]
    else:
        print(a, A[i])
        a -= A[i]
print(a, b)

Fixed submission:
import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int,input().split()))

a, b = max(A), min(A)
for t in [a, b]:
    for i in range(len(A)):
        if A[i] == t:
            A.pop(i)
            break

ans = a-b
for i in range(n-2):
    ans += abs(A[i])
print(ans)

for i in range(n-2):
    if A[i] > 0:
        print(b, A[i])
        b -= A[i]
    else:
        print(a, A[i])
        a -= A[i]
print(a, b)

Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int,input().split()))

a = max(A)
b = min(A)
A.pop(a)
A.pop(b)

ans = a-b
for i in range(n-2):
    ans += abs(A[i])
print(ans)

for i in range(n-2):
    if A[i] > 0:
        print(b, A[i])
        b -= A[i]
    else:
        print(a, A[i])
        a -= A[i]
print(a, b)

Fixed submission:
import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int,input().split()))

a, b = max(A), min(A)
for t in [a, b]:
    for i in range(len(A)):
        if A[i] == t:
            A.pop(i)
            break

ans = a-b
for i in range(n-2):
    ans += abs(A[i])
print(ans)

for i in range(n-2):
    if A[i] > 0:
        print(b, A[i])
        b -= A[i]
    else:
        print(a, A[i])
        a -= A[i]
print(a, b)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
n = len(s)
t = ""

i = 0
while i < n-1:
    if s[i:i+2] == "BC":
        t += "D"
        i += 2
    else:
        t += s[i]
        i += 1

# print(t)

m = len(t)
i = 0
p = 0
ans = 0
while i < m:
    while i < m and (t[i] == "A" or t[i] == "D"):
        if t[i] == "A":
            p += 1
        else:
            ans += p
        i += 1
    p = 0
    i += 1

print(ans)

Fixed submission:
s = input()
n = len(s)
A = []

i = 0
while i < n-1:
    if s[i:i+2] == "BC":
        A.append("D")
        i += 2
    else:
        A.append(s[i])
        i += 1

t = "".join(A)
# print(t)

m = len(t)
i = 0
p = 0
ans = 0
while i < m:
    while i < m and (t[i] == "A" or t[i] == "D"):
        if t[i] == "A":
            p += 1
        else:
            ans += p
        i += 1
    p = 0
    i += 1

print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
A = [list(map(int,input().split())) for i in range(n-1)]

B = [[] for i in range(n+1)]

for i in range(len(A)):
    B[A[i][0]].append([A[i][1],A[i][2]])
    B[A[i][1]].append([A[i][0],A[i][2]])

root = 0
for i in range(len(B)):
    root = max(root, len(B[i]))

ANS = [-1 for i in range(n+1)]
ANS[root]=0
#print(B)
def nuru(k):
    col = ANS[k]
    for j in range(len(B[k])):
        if ANS[B[k][j][0]] == -1:
            ANS[B[k][j][0]] = (col + B[k][j][1])%2
            nuru(B[k][j][0])

nuru(root)

#print(ANS)

for i in range(n):
    print(ANS[i+1])


Fixed submission:
n = int(input())
A = [list(map(int,input().split())) for i in range(n-1)]

B = [[] for i in range(n+1)]

for i in range(len(A)):
    B[A[i][0]].append([A[i][1],A[i][2]])
    B[A[i][1]].append([A[i][0],A[i][2]])

root = 0
for i in range(len(B)):
    root = max(root, len(B[i]))

ANS = [-1 for i in range(n+1)]
ANS[root]=0
#print(B)
nurulist = [root]
t = 0
while t < len(nurulist):
    k = nurulist[t]
    col = ANS[k]
    for j in range(len(B[k])):
        if ANS[B[k][j][0]] == -1:
            ANS[B[k][j][0]] = (col + B[k][j][1])%2
            nurulist.append(B[k][j][0])
    t += 1


#print(ANS)

for i in range(n):
    print(ANS[i+1])

Buggy python submission (verdict: Runtime Error):
n = int(input())
A = [list(map(int,input().split())) for i in range(n-1)]

B = [[] for i in range(n+1)]

for i in range(len(A)):
    B[A[i][0]].append([A[i][1],A[i][2]])
    B[A[i][1]].append([A[i][0],A[i][2]])

root = 0
for i in range(len(B)):
    root = max(root, len(B[i]))

ANS = [0 for i in range(n+1)]

def nuru(k):
    col = ANS[k]
    for j in range(len(B[k])):
        ANS[B[k][j][0]] = (col + B[k][j][1])%2
        nuru(j)

nuru(root)

#print(ANS)

for i in range(n):
    print(ANS[i+1])


Fixed submission:
n = int(input())
A = [list(map(int,input().split())) for i in range(n-1)]

B = [[] for i in range(n+1)]

for i in range(len(A)):
    B[A[i][0]].append([A[i][1],A[i][2]])
    B[A[i][1]].append([A[i][0],A[i][2]])

root = 0
for i in range(len(B)):
    root = max(root, len(B[i]))

ANS = [-1 for i in range(n+1)]
ANS[root]=0
#print(B)
nurulist = [root]
t = 0
while t < len(nurulist):
    k = nurulist[t]
    col = ANS[k]
    for j in range(len(B[k])):
        if ANS[B[k][j][0]] == -1:
            ANS[B[k][j][0]] = (col + B[k][j][1])%2
            nurulist.append(B[k][j][0])
    t += 1


#print(ANS)

for i in range(n):
    print(ANS[i+1])
Buggy python submission (verdict: Runtime Error):
n = int(input())
C = [int(input()) for i in range(n)]
nc = 10 ** 5 + 3
mod = 10**9+7

A = [0] * n
B = [-1] * nc

A[-1] = 1
B[C[-1]] = n-1
# print(B)

for i in range(n-2, -1, -1):
    if B[C[i]] != -1 and B[C[i]] != i+1:
        A[i] = (A[i+1] + A[B[C[i]]]) % mod
    else:
        A[i] = A[i+1]
    B[C[i]] = i
    # print(A,B)

# print(A)
# print(B)
print(A[0])

Fixed submission:
n = int(input())
C = [int(input()) for i in range(n)]
nc = 2 * 10 ** 5 + 3
mod = 10**9+7

A = [0] * n
B = [-1] * nc

A[-1] = 1
B[C[-1]] = n-1
# print(B)

for i in range(n-2, -1, -1):
    if B[C[i]] != -1 and B[C[i]] != i+1:
        A[i] = (A[i+1] + A[B[C[i]]]) % mod
    else:
        A[i] = A[i+1]
    B[C[i]] = i
    # print(A,B)

# print(A)
# print(B)
print(A[0])

Buggy python submission (verdict: Runtime Error):
n = int(input())
C = [int(input()) for i in range(n)]
mod = 10**9+7

A = [0] * n
B = [-1] * (n+1)

A[-1] = 1
B[C[-1]] = n-1
# print(B)

for i in range(n-2, -1, -1):
    if B[C[i]] != -1 and B[C[i]] != i+1:
        A[i] = (A[i+1] + A[B[C[i]]]) % mod
    else:
        A[i] = A[i+1]
    B[C[i]] = i
    # print(A,B)

# print(A)
# print(B)
print(A[0])

Fixed submission:
n = int(input())
C = [int(input()) for i in range(n)]
nc = 2 * 10 ** 5 + 3
mod = 10**9+7

A = [0] * n
B = [-1] * nc

A[-1] = 1
B[C[-1]] = n-1
# print(B)

for i in range(n-2, -1, -1):
    if B[C[i]] != -1 and B[C[i]] != i+1:
        A[i] = (A[i+1] + A[B[C[i]]]) % mod
    else:
        A[i] = A[i+1]
    B[C[i]] = i
    # print(A,B)

# print(A)
# print(B)
print(A[0])
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
A = [list(map(int, input().split())) for i in range(m)]

ans = int(0.5*n*(n-1))
AA=[ans]
G = [i for i in range(n+1)]
H = [1 for i in range(n+1)]
for i in range(m) :
    x = A[m-1-i][0]
    y = A[m-1-i][1]
    #print("{} {}".format(x,y))
    if G[x] != G[y] :
        xx=G[x]
        for j in range(n+1) :
            if G[j] == xx :
                G[j] = G[y]
        ans -= H[xx] * H[G[y]]
        nn = H[xx] + H[G[y]]
        H[xx]=0
        H[G[y]]=nn
    #print(G)
    #print(H)
    #print(ans)
    AA.append(ans)

for i in range(len(AA)-1):
    print(AA[len(AA)-2-i])


Fixed submission:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

n, m = map(int, input().split())
A = [list(map(int, input().split())) for i in range(m)]

for i in range(m):
    for j in range(2):
        A[i][j] -= 1

U = UnionFind(n)
ans = n * (n-1) // 2
ANS = []
for i in range(m-1, -1, -1):
    ANS.append(ans)
    a = A[i][0]
    b = A[i][1]
    ua = U.find(a)
    ub = U.find(b)
    if ua != ub:
        ans -= U.parents[ua] * U.parents[ub]
        U.union(ua, ub)

for i in range(len(ANS)-1, -1, -1):
    print(ANS[i])
Buggy python submission (verdict: Runtime Error):
L=int(input())
A=[int(input()) for i in range(L)]
su=sum(A)
#print(A)

DP=[[0 for i in range(5)] for j in range(L)]

mod=A[0]%2
if A[0]==0 :
    mod=2
DP[1]=[A[0],min(A[0],mod%2),min(A[0],mod%2,(mod+1)%2),min(A[0],mod%2,(mod+1)%2),min(A[0],mod%2,(mod+1)%2)]

for i in range(2,L):
    mod=A[i]%2
    if A[i]==0 :
        mod=2
    DP[i][0]+=DP[i-1][0]+A[i]
    DP[i][1]+=min(DP[i-1][0],DP[i-1][1])+mod
    DP[i][2]+=min(DP[i-1][j] for j in range(3))+(mod+1)%2
    DP[i][3]+=min(DP[i-1][j] for j in range(4))+mod
    DP[i][4]+=min(DP[i-1][j] for j in range(5))+A[i]

#print(DP)
print(min(DP[L-1]))


Fixed submission:
L=int(input())
A=[int(input()) for i in range(L)]
su=sum(A)
#print(A)

DP=[[0 for i in range(5)] for j in range(L+1)]

mod=A[0]%2
if A[0]==0 :
    mod=2
DP[1]=[A[0],min(A[0],mod%2),min(A[0],mod%2,(mod+1)%2),min(A[0],mod%2,(mod+1)%2),min(A[0],mod%2,(mod+1)%2)]

for i in range(2,L+1):
    mod=A[i-1]%2
    if A[i-1]==0 :
        mod=2
    DP[i][0]+=DP[i-1][0]+A[i-1]
    DP[i][1]+=min(DP[i-1][0],DP[i-1][1])+mod
    DP[i][2]+=min(DP[i-1][j] for j in range(3))+(mod+1)%2
    DP[i][3]+=min(DP[i-1][j] for j in range(4))+mod
    DP[i][4]+=min(DP[i-1][j] for j in range(5))+A[i-1]

#print(DP)
print(min(DP[L]))

Buggy python submission (verdict: Runtime Error):
L=int(input())
A=[int(input()) for i in range(L)]
su=sum(A)
#print(A)

DP=[[0 for i in range(5)] for j in range(L)]

DP[1]=[A[0],min(A[0],A[0]%2),min(A[0],A[0]%2,(A[0]+1)%2),min(A[0],A[0]%2,(A[0]+1)%2),min(A[0],A[0]%2,(A[0]+1)%2)]

for i in range(2,L):
    mod=A[i]%2
    if A[i]==0 :
        mod=2
    DP[i][0]+=DP[i-1][0]+A[i]
    DP[i][1]+=min(DP[i-1][0],DP[i-1][1])+mod
    DP[i][2]+=min(DP[i-1][j] for j in range(3))+(mod+1)%2
    DP[i][3]+=min(DP[i-1][j] for j in range(4))+mod
    DP[i][4]+=min(DP[i-1][j] for j in range(5))+A[i]

#print(DP)
print(min(DP[L-1]))


Fixed submission:
L=int(input())
A=[int(input()) for i in range(L)]
su=sum(A)
#print(A)

DP=[[0 for i in range(5)] for j in range(L+1)]

mod=A[0]%2
if A[0]==0 :
    mod=2
DP[1]=[A[0],min(A[0],mod%2),min(A[0],mod%2,(mod+1)%2),min(A[0],mod%2,(mod+1)%2),min(A[0],mod%2,(mod+1)%2)]

for i in range(2,L+1):
    mod=A[i-1]%2
    if A[i-1]==0 :
        mod=2
    DP[i][0]+=DP[i-1][0]+A[i-1]
    DP[i][1]+=min(DP[i-1][0],DP[i-1][1])+mod
    DP[i][2]+=min(DP[i-1][j] for j in range(3))+(mod+1)%2
    DP[i][3]+=min(DP[i-1][j] for j in range(4))+mod
    DP[i][4]+=min(DP[i-1][j] for j in range(5))+A[i-1]

#print(DP)
print(min(DP[L]))
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
X=list(map(int,input().split()))
X.sort()

if m==1 :
    print(0)
else :

    sa=[]
    for i in range(m-1):
        sa.append(X[i+1]-X[i])


    sa.sort(reverse=1)


    jo=[]
    for i in range(n-1):
        jo.append(sa[i])


    print(X[m-1]-X[0]-sum(jo))


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

if m==1 or n>=m :
    print(0)
else :

    sa=[]
    for i in range(m-1):
        sa.append(X[i+1]-X[i])


    sa.sort(reverse=1)


    jo=[]
    for i in range(n-1):
        jo.append(sa[i])


    print(X[m-1]-X[0]-sum(jo))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
C = [list(map(int,input().split())) for i in range(n-1+m)]

r = -1
R = [1] * (n+1)
for i in range(len(C)):
    R[C[i][1]] = 0
for i in range(1, n+1):
    if R[i] == 1:
        r = i

# print(r)

# V = [0] * (n+1)
P = [0] * (n+1)

M = [[] for i in range(n+1)]
for i in range(n-1+m):
    M[C[i][0]].append(C[i][1])

# 1始まりの場合
Q = [r]
s = 0
# V[r] = 1
while s < len(Q):
    i = Q[s]
    for x in M[i]:
        if x != P[i]:
            # V[x] = 1
            P[x] = i
            Q.append(x)
    s += 1
# print(P)

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

Fixed submission:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
C = [list(map(int,input().split())) for i in range(n-1+m)]

r = -1
R = [1] * (n+1)
for i in range(len(C)):
    R[C[i][1]] = 0
for i in range(1, n+1):
    if R[i] == 1:
        r = i

# print(r)

F = [0] * (n+1)
P = [0] * (n+1)

M = [[] for i in range(n+1)]
for i in range(n-1+m):
    M[C[i][0]].append(C[i][1])
    F[C[i][1]] += 1

# 1始まりの場合
Q = [r]
s = 0
# V[r] = 1
while s < len(Q):
    i = Q[s]
    for x in M[i]:
        F[x] -= 1
        if F[x] == 0:
            P[x] = i
            Q.append(x)
    s += 1
# print(P)

for i in range(1, n+1):
    print(P[i])
Buggy python submission (verdict: Runtime Error):
n=int(input())
a=input()
b=input()

if n==1 :
    print("Hello World")
else :
    print(int(a)+int(b))


Fixed submission:
n=int(input())

 
if n==1 :
    print("Hello World")
else :
    a=input()
    b=input()
    print(int(a)+int(b))
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())

ans=0
for i in range(1,m//n+1):
    if m%i==0 :
        ans=i
print(ans)


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

ans=0
for i in range(1,int(m**0.5)+2):
    if m%i==0 :
        a=m//i
        if min(a,i)>=n :
            ans=max(ans,max(a,i))
        elif max(a,i)>=n :
            ans=max(ans,min(a,i))
print(ans)
Buggy python submission (verdict: Runtime Error):
n=int(input())
V=list(map(int,input().split()))

A=[[0,i] for i in range(10**5+3)]
B=[[0,i] for i in range(10**5+3)]

for i in range(0,n,2):
    A[V[i]][0]+=1
for i in range(1,n,2):
    B[V[i]][0]+=1

A.sort(reverse=1)
B.sort(reverse=1)

#print(A[:10])
#print(B[:10])

Ma=[]
Mb=[]

ma=A[0][0]
mb=B[0][0]
i=0
j=0
while A[i][0]==ma :
    Ma.append(A[i][1])
    i+=1

while B[j][0]==mb :
    Mb.append(B[j][1])
    j+=1

if Ma==Mb :
    print(min(n-ma-B[j][0],n-mb-A[i][0]))
else :
    print(n-ma-mb)


Fixed submission:
n=input()

ans=""
for i in range(len(n)):
  if n[i]=="1" :
    ans+="9"
  elif n[i]=="9" :
    ans+="1"

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

A=[[0,i] for i in range(10**5)]
B=[[0,i] for i in range(10**5)]

for i in range(0,n,2):
    A[V[i]][0]+=1
for i in range(1,n,2):
    B[V[i]][0]+=1

A.sort(reverse=1)
B.sort(reverse=1)

#print(A[:10])
#print(B[:10])

Ma=[]
Mb=[]

ma=A[0][0]
mb=B[0][0]
i=0
j=0
while A[i][0]==ma :
    Ma.append(A[i][1])
    i+=1

while B[j][0]==mb :
    Mb.append(B[j][1])
    j+=1

if Ma==Mb :
    print(min(n-ma-B[j][0],n-mb-A[i][0]))
else :
    print(n-ma-mb)


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

A = [[0] * (10**5+1) for i in range(2)]

for i in range(n):
    A[i%2][V[i]] += 1

C = [[0] * (10**5+1) for i in range(2)]  # A[0][:i], A[1][:i]の最大値
for i in range(1, len(C[0])):
    C[0][i] = max(C[0][i-1], A[0][i])
    C[1][i] = max(C[1][i-1], A[1][i])

# print(A[0][:150])
# print(A[1][:150])
# print(C[:150])

ans = 0
for i in range(1, len(C[0])):
    ans = max(ans, C[1][i-1] + A[0][i])
    ans = max(ans, C[0][i-1] + A[1][i])

print(n - ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
A=list(map(int,input().split()))
for i in range(n):
    A[i]=A[i]%m

B=[]

for i in range(n):
    sumi=A[i]
    ri=i+1
    while ri<n and sumi%m!=0 :
        sumi=(sumi+A[ri])%m
        ri+=1
    if ri==n and sumi%m!=0 :
        ri=-1
    B.append(ri)
#print(B)

mco=0
for i in range(n):
    coi=0
    ms=0
    s=i
    while s!=n and s!=-1 :
        ms=s
        s=B[s]
        B[ms]=-1
        coi+=1
        #print("s"+str(s))
    if s==-1 :
        coi-=1
    #print(coi)
    mco+=coi*(coi+1)//2

print(mco)


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

B=[]
su=0
for i in range(n):
    su+=A[i]
    B.append(su)

#print(B)

C={}
C[0]=1
for i in range(n):
    C[B[i]%m]=C.get(B[i]%m,0)+1

#print(C)

#D=C.values()
su=0
#print(C.values())
for i in C.values():
    su+=i*(i-1)//2
print(su)
Buggy python submission (verdict: Runtime Error):
a=int(input())
N=[0 for i in range(a)]
b=input()
for i in range(a):
  N[i]=int(b.aplit())

2ans=0
2ans2=0
for i in range(a-1):
  if N[i]==N[i+1]:
    2ans2+=1
  else :
    if 2ans2%2==1 :
      2ans2+=1
    ans+=2ans2/2
    2ans2=0
return 2ans

Fixed submission:
a=int(input())
N=[0 for i in range(a)]
b=input()
#print(b)
N=b.split()
for i in range(a):
  N[i]=int(N[i])

#print(N)
  
a2ans=0
a2ans2=0
for i in range(a-1):
  if N[i]==N[i+1]:
    a2ans2+=1
    #print(a2ans2)
  else :
    if a2ans2%2==1 :
      a2ans2+=1
    
    a2ans+=a2ans2/2
    a2ans2=0


if a2ans2%2==1 :
  a2ans2+=1
#print(a2ans2)
a2ans+=a2ans2/2
a2ans2=0



print(int(a2ans))
Buggy python submission (verdict: Time Limit Exceeded):
n,c=map(int,input().split())
D=[]
for i in range(c):
    D.append(list(map(int,input().split())))
C=[]
for i in range(n):
    C.append(list(map(int,input().split())))

#print(D)

C1=[]
C2=[]
C3=[]
for i in range(n):
    for j in range(n):
        f=(i+j)%3
        if f==0:
            C1.append(C[i][j])
        if f==1:
            C2.append(C[i][j])
        if f==2:
            C3.append(C[i][j])
        

miniwa=1000*500*500

#print(C3)

for c1 in range(0,c):
    iwa1=sum(D[i-1][c1] for i in C1)
    for c2 in range(0,c):
        iwa2=sum(D[j-1][c2] for j in C2)
        for c3 in range(0,c):
            if c1!=c2 and c2!=c3 and c3!=c1 :
                iwa3=sum(D[k-1][c3] for k in C3)
                iwa=iwa1+iwa2+iwa3
                miniwa=min(miniwa,iwa)

print(miniwa)


Fixed submission:
n,c=map(int,input().split())
D=[]
for i in range(c):
    D.append(list(map(int,input().split())))
C=[]
for i in range(n):
    C.append(list(map(int,input().split())))

#print(D)

C1=[]
C2=[]
C3=[]
for i in range(n):
    for j in range(n):
        f=(i+j)%3
        if f==0:
            C1.append(C[i][j])
        if f==1:
            C2.append(C[i][j])
        if f==2:
            C3.append(C[i][j])
        

miniwa=1000*500*500

#print(C3)
iwa1=[]
iwa2=[]
iwa3=[]

for cc in range(0,c):
    iwa1.append(sum(D[i-1][cc] for i in C1))
    iwa2.append(sum(D[i-1][cc] for i in C2))
    iwa3.append(sum(D[i-1][cc] for i in C3))

for c1 in range(0,c):
    for c2 in range(0,c):
        for c3 in range(0,c):
            if c1!=c2 and c2!=c3 and c3!=c1 :
                iwa=iwa1[c1]+iwa2[c2]+iwa3[c3]
                miniwa=min(miniwa,iwa)

print(miniwa)
Buggy python submission (verdict: Time Limit Exceeded):
from operator import itemgetter

s=input()
k=int(input())

S=[]
ls=len(s)
for i in range(ls):
    S.append([s[i:ls],0,ls-i])

S.sort()

S[0][1]=S[0][2]
for i in range(ls-1):
    t=0
    lS0=len(S[i][0])
    lSp1=len(S[i+1][0])
    while t<lS0 and t<lSp1 and S[i][0][t]==S[i+1][0][t]:
        t+=1
    S[i+1][1]=S[i+1][2]-t

#print(S)




k-=1
i=0
while k>=S[i][1] :
    k-=S[i][1]
    i+=1

ans=S[i][0][0:(S[i][2]-S[i][1]+k+1)]

#print(i)

print(ans)


Fixed submission:
s = input()
n = len(s)
k = int(input())

A = []
for i in range(n):
    A.append(s[i:])

A.sort()
# print(A)

B = []

for i in range(min(k, len(A))):
    for j in range(1, len(A[i])+1):
        B.append(A[i][:j])

B.sort()

# print(B)
co = 1
i = 1
mae = B[0]
while co < k:
    #print(i)
    if mae != B[i]:
        co += 1
        mae = B[i]
    i += 1
print(mae)

Buggy python submission (verdict: Time Limit Exceeded):
from operator import itemgetter

s=input()
k=int(input())

S=[]
for i in range(len(s)):
    S.append([s[i:len(s)],0,len(s)-i])

S.sort()

S[0][1]=S[0][2]
for i in range(len(S)-1):
    t=0
    while t<len(S[i][0]) and t<len(S[i+1][0]) and S[i][0][t]==S[i+1][0][t]:
        t+=1
    S[i+1][1]=S[i+1][2]-t

#print(S)




k-=1
i=0
while k>=S[i][1] :
    k-=S[i][1]
    i+=1

ans=S[i][0][0:(S[i][2]-S[i][1]+k+1)]

#print(i)

print(ans)


Fixed submission:
s = input()
n = len(s)
k = int(input())

A = []
for i in range(n):
    A.append(s[i:])

A.sort()
# print(A)

B = []

for i in range(min(k, len(A))):
    for j in range(1, len(A[i])+1):
        B.append(A[i][:j])

B.sort()

# print(B)
co = 1
i = 1
mae = B[0]
while co < k:
    #print(i)
    if mae != B[i]:
        co += 1
        mae = B[i]
    i += 1
print(mae)