Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
P=list(map(int,input().split()))
X=[]
for i in range(m):
    X.append(list(map(int,input().split())))



import networkx as nx

G = nx.Graph()

for i in range(n):
    G.add_node(i+1)
    
#print(G.nodes())

for i in range(m):
    G.add_edge(X[i][0],X[i][1])
    G[X[i][0]][X[i][1]]["capacity"] = 1.0

#print(G.edges())

#print(nx.maximum_flow(G, 1, 2)[0])



#print(G.successors(1))

co=0
for i in range(n):
    #print(nx.maximum_flow(G, i+1, P[i])[0])
    if i+1==P[i] or nx.maximum_flow(G, i+1, P[i])[0]==1.0:
        co+=1
    #elif nx.maximum_flow(G, i+1, P[i])[0]==1.0 :
    #    co+=1
print(co)



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

for i in range(n):
    P[i] -= 1
for i in range(m):
    for j in range(2):
        X[i][j] -= 1

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

for i in range(m):
    M[X[i][0]].append(X[i][1])
    M[X[i][1]].append(X[i][0])

G = [0] * n
clr = 0

for i in range(n):
    if G[i] == 0 and len(M[i]) > 0:
        clr += 1
        G[i] = clr
        
        Q = M[i][:]
        st = 0
        while st < len(Q):
            if G[Q[st]] == 0:
                G[Q[st]] = clr
                for item in M[Q[st]]:
                    Q.append(item)

            st += 1

# print(G)

ans = 0
for i in range(n):
    if G[i] == 0 and i == P[i]:
        ans += 1

G2 = [[[], []] for i in range(clr+1)]

for i in range(n):
    G2[G[i]][0].append(i)
    G2[G[i]][1].append(P[i])
# print(G2)
# print(ans)

for i in range(1, clr+1):
    ans += len(G2[i][0]) * 2 - len(set(G2[i][0] + G2[i][1]))

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

ans=0

B1=[] #時計回り、引き返さない
su=0
for i in range(n):
    su+=A[i][1]
    B1.append(su-A[i][0])

#print(B1)

ans=max(ans,max(B1))

B2=[] #反時計回り、引き返さない
su=0
for i in range(n-1,-1,-1):
    su+=A[i][1]
    B2.append(su-(c-A[i][0]))

#print(B2)


ans=max(ans,max(B2))


B3=[] #時計回り、引き返す(半周以上周ってから引き返してはいけない)
B4=[] #反時計回り、引き返す（同上）

for i in range(n):
    if A[i][0]<=(c-0.1)//2 :
        B3.append(B1[i]-A[i][0])

#print(B3)

for i in range(n-1,-1,-1):
    j=0
    if (c-A[i][0])<=(c-0.1)//2 :
        B4.append(B2[j]-(c-A[i][0]))
    j+=1

#print(B4)

if len(B3)>0 :
    aa=B3.index(max(B3))
    #print(max(B3)+max(B2[:n-aa-1]))
    ans=max(ans,max(B3)+max(B2[:n-aa-1]))
if len(B4)>0 :
    bb=B4.index(max(B4))
    #print(max(B4)+max(B1[:n-bb-1]))
    ans=max(ans,max(B4)+max(B1[:n-bb-1]))

print(ans)


Fixed submission:
n, c = map(int, input().split())
XR = [list(map(int,input().split())) for i in range(n)]
XL = [[c-XR[i][0], XR[i][1]] for i in range(n)]
XL.sort()

CR = []
cal = 0
for i in range(n):
    dis = XR[i][0]
    cal += XR[i][1]
    CR.append([cal-dis, dis])


CSR = [CR[0][0]]
for i in range(n-1):
    CSR.append(max(CSR[i], CR[i+1][0]))

CL = []
cal = 0
for i in range(n):
    dis = XL[i][0]
    cal += XL[i][1]
    CL.append([cal-dis, dis])


CSL = [CL[0][0]]
for i in range(n-1):
    CSL.append(max(CSL[i], CL[i+1][0]))


# print(CSR)
# print(CSL)
# print(CR)
# print(CL)

ans = max(max(CSR), max(CSL))
for i in range(n-1):
    # print(CL[i][0]-CL[i][1]+CSR[n-2-i], CL[i][0],CL[i][1],CSR[n-2-i])
    ans = max(ans, CL[i][0]-CL[i][1]+CSR[n-2-i])
    ans = max(ans, CR[i][0]-CR[i][1]+CSL[n-2-i])

print(max(ans, 0))
Buggy python submission (verdict: Time Limit Exceeded):
a,b,k=map(int,input().split())

for i in range(a,b+1):
    if i<=a+k-1 or i>=b-k+1 :
        print(i)


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

st=a
while st<=min(a+k-1,b) :
    print(st)
    st+=1
st=max(st,b-k+1)
while st<=b :
    print(st)
    st+=1
Buggy python submission (verdict: Time Limit Exceeded):
import sys
n = int(input())
print(0, flush=True)
s = input()
if s == "Vacant":
    sys.exit()
l = 0
r = n
ls = s
rs = s

def nibun(l, r, m, ls, rs, s):
    if ((m-l) % 2 == 0 and ls == s) or\
        ((m-l) % 2 == 1 and ls != s):
        return 1
    else:
        return 0

for ii in range(21):
    m = (l+r)//2
    print(m, flush=True)
    s = input()
    if s == "Vacant":
        break
    if nibun(l, r, m, ls, rs, s) == 0:
        r = m
        rs = s
    else:
        l = m
        ls = s

Fixed submission:
import sys
n = int(input())
print(0, flush=True)
s = input()
if s == "Vacant":
    sys.exit()
l = 0
r = n
ls = s
rs = s

def nibun(l, r, m, ls, rs, s):
    if ((m-l) % 2 == 0 and ls == s) or\
        ((m-l) % 2 == 1 and ls != s):
        return 1
    else:
        return 0

for ii in range(21):
    m = (l+r)//2
    print(m, flush=True)
    s = input()
    if s == "Vacant":
        break
    if nibun(l, r, m, ls, rs, s) == 0:
        r = m
        rs = s
    else:
        l = m
        ls = s

Buggy python submission (verdict: Time Limit Exceeded):
import sys
n = int(input())
print(0, flush=True)
s = input()
if s == "Vacant":
    sys.exit()
s = s[0]
l = 0
r = n
ls = s
rs = s

def nibun(l, r, m, ls, rs, s):
    if ((m-l) % 2 == 0 and ls == s) or\
        ((m-l) % 2 == 1 and ls != s):
        return 1
    else:
        return 0

for ii in range(21):
    m = (l+r)//2
    print(m, flush=True)
    s = input()
    if s == "Vacant":
        break
    s = s[0]
    if nibun(l, r, m, ls, rs, s) == 0:
        r = m
        rs = s
    else:
        l = m
        ls = s

    


Fixed submission:
import sys
n = int(input())
print(0, flush=True)
s = input()
if s == "Vacant":
    sys.exit()
l = 0
r = n
ls = s
rs = s

def nibun(l, r, m, ls, rs, s):
    if ((m-l) % 2 == 0 and ls == s) or\
        ((m-l) % 2 == 1 and ls != s):
        return 1
    else:
        return 0

for ii in range(21):
    m = (l+r)//2
    print(m, flush=True)
    s = input()
    if s == "Vacant":
        break
    if nibun(l, r, m, ls, rs, s) == 0:
        r = m
        rs = s
    else:
        l = m
        ls = s
Buggy python submission (verdict: Runtime Error):
a, b, c, d = map(int,input().split())
A = ["Left", "Balanced", "Right"]
print(A[(c+d) // (a+b) - (a+b) // (c+d) + 1])

Fixed submission:
a, b, c, d = map(int,input().split())
A = ["Left", "Balanced", "Right"]
print(A[int((c+d) > (a+b)) - int((a+b) > (c+d)) + 1])
Buggy python submission (verdict: Runtime Error):
import string
s = input()

s = sorted(set(s))
moji = [chr(i) for i in range(ord('a'), ord('z')+1)]
# print(s)
# print(moji)

def b():
    for i in range(len(moji)):
        if moji[i] != s[i]:
            return moji[i]
    return "None"

print(b())



Fixed submission:
import string
s = input()

s = sorted(set(s))
moji = [chr(i) for i in range(ord('a'), ord('z')+1)]
# print(s)
# print(moji)

def b():
    for i in range(len(moji)):
        if i > len(s)-1 or moji[i] != s[i]:
            return moji[i]
    return "None"

print(b())
Buggy python submission (verdict: Runtime Error):

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

if a % 3 == 0 or b % 3 == 0 or (a+b) % 3 == 0:
    print("Possible")
else:
    print("Impossible")

Fixed submission:

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

if a % 3 == 0 or b % 3 == 0 or (a+b) % 3 == 0:
    print("Possible")
else:
    print("Impossible")
Buggy python submission (verdict: Time Limit Exceeded):
a, b, c = map(int,input().split())

def aa():
    if a == b and a == c and a % 2 == 0:
        return -1
    else:
        A = [a-b, b-c, c-a]
        j = 0
        while True:
            for i in range(3):
                if A[i] % 2 == 1:
                    return j
                else:
                    A[i] //= 2
            j += 1

print(aa())

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

def aa():
    if a == b and a == c:
        if a % 2 == 0:
            return -1
        else:
            return 0
    else:
        A = [a-b, b-c, c-a]
        j = 0
        while True:
            for i in range(3):
                if A[i] % 2 == 1:
                    return j
                else:
                    A[i] //= 2
            j += 1

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

i = 0
def w(i):
    # print(i)
    if A[i] - A[i-1] == 0:
        return 0
    else:
        return (A[i]-A[i-1]) / abs(A[i]-A[i-1])
v = w(1)
ans = 1

i = 2
while i < n:
    nv = w(i)
    if nv * v < 0:
        ans += 1
        i += 2
        if i == n+1:
            ans += 1
    else:
        i += 1
    if nv != 0:
        v = nv
print(ans)

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

# i = 0
# def w(i):
#     # print(i)
#     if A[i] - A[i-1] == 0:
#         return 0
#     else:
#         return (A[i]-A[i-1]) / abs(A[i]-A[i-1])
# v = w(1)
# ans = 1

# i = 2
# while i < n:
#     print(i)
#     nv = w(i)
#     if nv * v < 0:
#         ans += 1
#         i += 2
#         v = 0
#         if i == n:
#             print("p")
#             ans += 1
#     else:
#         i += 1
#     if nv != 0:
#         v = nv

B = []
for i in range(1, n):
    if A[i] != A[i-1]:
        B.append(int((A[i]-A[i-1]) / abs(A[i]-A[i-1])))
# print(B)

ans = 1
t = 0
m = 0
for i in range(len(B)):
    # print(i)
    if B[i] * t < 0:
        # print("p")
        ans += 1
        t = 0
        if i == len(B):
            ans += 1
    else:
        t = B[i]

print(ans)

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

v = (A[1]-A[0]) / abs(A[1]-A[0])
ans = 1
i = 2
while i < n:
    if (A[i] - A[i-1]) * v < 0:
        v *= -1
        ans += 1
        i += 2
        if i == n+1:
            ans += 1
    else:
        i += 1
print(ans)

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

# i = 0
# def w(i):
#     # print(i)
#     if A[i] - A[i-1] == 0:
#         return 0
#     else:
#         return (A[i]-A[i-1]) / abs(A[i]-A[i-1])
# v = w(1)
# ans = 1

# i = 2
# while i < n:
#     print(i)
#     nv = w(i)
#     if nv * v < 0:
#         ans += 1
#         i += 2
#         v = 0
#         if i == n:
#             print("p")
#             ans += 1
#     else:
#         i += 1
#     if nv != 0:
#         v = nv

B = []
for i in range(1, n):
    if A[i] != A[i-1]:
        B.append(int((A[i]-A[i-1]) / abs(A[i]-A[i-1])))
# print(B)

ans = 1
t = 0
m = 0
for i in range(len(B)):
    # print(i)
    if B[i] * t < 0:
        # print("p")
        ans += 1
        t = 0
        if i == len(B):
            ans += 1
    else:
        t = B[i]

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

# print(B)

ans = 0
for i in range(n):
    ma = -1
    mm = A[i]
    while mm <= m and ma != mm:
        ma = mm
        mm = B[mm]
    if mm > m:
        ans += 1
print(ans)

Fixed submission:
n = int(input())
A = list(map(int,input().split()))
A.sort()
ans = 1
m = A[0]
for i in range(n-1):
    if A[i+1] <= 2*m:
        ans += 1
    else:
        ans = 1
    m += A[i+1]
print(ans)
Buggy python submission (verdict: Runtime Error):
n, m = map(int,input().split())
A = [list(map(int,input().split())) for i in range(n)]

import itertools

M = [[0] * (n+1) for i in range(n+1)]
for i in range(m):
    M[A[i][0]][A[i][1]] = 1
    M[A[i][1]][A[i][0]] = 1

B = list(itertools.permutations(range(2, n+1)))

#print(B)

ans = 0
for i in range(len(B)):
    pt = 0
    if M[1][B[i][0]] == 1:
        pt += 1
    else:
        continue

    for j in range(len(B[i])-1):
        if M[B[i][j]][B[i][j+1]] == 1:
            pt += 1
    # print(B[i],pt)
    if pt == n-1:
        ans += 1
print(ans)


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

import itertools

M = [[0] * (n+1) for i in range(n+1)]
for i in range(m):
    M[A[i][0]][A[i][1]] = 1
    M[A[i][1]][A[i][0]] = 1

B = list(itertools.permutations(range(2, n+1)))

#print(B)

ans = 0
for i in range(len(B)):
    pt = 0
    if M[1][B[i][0]] == 1:
        pt += 1
    else:
        continue

    for j in range(len(B[i])-1):
        if M[B[i][j]][B[i][j+1]] == 1:
            pt += 1
    # print(B[i],pt)
    if pt == n-1:
        ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
3
6 6 6

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

m = max(B)
no = 0

if m < 0:
    no = 1
elif m == 0:
    if A[0] % (n*(n+1)//2) > 0:
        no = 1
else:
    c = 0
    for i in range(n):
        if (m - B[i]) % n > 0:
            no = 1
        else:
            c += (m - B[i]) // n

    if c != m:
        no = 1
    if sum(A) != m * n*(n+1)//2:
        no = 1

if no==1:
    print("NO")
else:
    print("YES")
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
n, m = map(int,input().split())
Y = list(map(int,input().split()))

l = max(Y) + 1
X = [0] * l
for i in range(n):
    X[Y[i]] += 1

# print(X)
U = [[0] * m for i in range(2)]

for i in range(l):
    a = X[i] // 2
    U[0][i % m] += a

A = [0] * m
for i in range(l):
    A[i % m] += X[i]
# print(A)

for i in range(1, m//2 + 1):
    a = min(A[i], A[m-i-1])
    U[1][i] += a
    U[1][m-i-1] += a

U[1][i] = A[0]

# print(U)

ans = 0
for i in range(m):
    ans += min((A[i]-U[1][i]) // 2, U[0][i]) * 2 + U[1][i]

print(ans)

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

l = max(Y) + 1
X = [0] * l
for i in range(n):
    X[Y[i]] += 1

# print(X)
U = [[0] * m for i in range(2)]

for i in range(l):
    a = X[i] // 2
    U[0][i % m] += a

A = [0] * m
for i in range(l):
    A[i % m] += X[i]
# print(A)

for i in range(1, m//2 + 1):
    a = min(A[i], A[m-i])
    U[1][i] += a
    U[1][m-i] += a

U[1][0] = A[0]

# print(U)

ans = 0
for i in range(m):
    ans += min((A[i]-U[1][i]) // 2, U[0][i]) * 2 + U[1][i]

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

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

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

# for i in range(1, n):
#     lcms = [0] * 2
#     for j in range(2):
#         lcms[j] = lcm(A[i][j], A[i-1][j])
#     print("lcms", lcms)
#     st = 0
#     op = 1
#     if lcms[0] > lcms[1]:
#         st = 1
#         op = 0
#     new_1 = (lcms[st] // A[i][st]) * A[i][op]
#     print(new_1)
#     if new_1 >= A[i-1][op]:
#         A[i][op] = new_1
#         A[i][st] = lcms[0]
#     else:
#         new_0 = lcms[op] // A[i][op] * A[i][st]
#         A[i][st] = new_0
#         A[i][op] = lcms[op]
#     print(A[i])

# print(sum(A[-1]))

for i in range(1, n):
    s = A[i][0]
    t = A[i][1]
    while not (A[i][0] >= A[i-1][0] and A[i][1] >= A[i-1][1]):
        A[i][0] += s
        A[i][1] += t
        # print(A[i-1], A[i])

print(sum(A[-1]))

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

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

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

# for i in range(1, n):
#     lcms = [0] * 2
#     for j in range(2):
#         lcms[j] = lcm(A[i][j], A[i-1][j])
#     print("lcms", lcms)
#     st = 0
#     op = 1
#     if lcms[0] > lcms[1]:
#         st = 1
#         op = 0
#     new_1 = (lcms[st] // A[i][st]) * A[i][op]
#     print(new_1)
#     if new_1 >= A[i-1][op]:
#         A[i][op] = new_1
#         A[i][st] = lcms[0]
#     else:
#         new_0 = lcms[op] // A[i][op] * A[i][st]
#         A[i][st] = new_0
#         A[i][op] = lcms[op]
#     print(A[i])

# print(sum(A[-1]))

for i in range(1, n):
    s = -(-A[i-1][0] // A[i][0])
    t = -(-A[i-1][1] // A[i][1])
    # print(i,s,t)
    for j in range(2):
        A[i][j] *= max(s, t)
    # print(A)
    
print(sum(A[-1]))
Buggy python submission (verdict: Runtime Error):
s = input() + "0"
def d():
    for i in range(len(s)-1):
        if s[i] == s[i+1]:
            return str(i+1) + " " + str(i+2)
        elif i <= len(s)-2 and s[i] == s[i+2]:
            return str(i+1) + " " + str(i+3)
    return "-1 -1"
print(d())

Fixed submission:
s = input()
n = len(s)
s += "0"
def d():
    for i in range(n-1):
        if s[i] == s[i+1]:
            return str(i+1) + " " + str(i+2)
        elif s[i] == s[i+2]:
            return str(i+1) + " " + str(i+3)
    return "-1 -1"
print(d())
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(int(2e6))

def dfs(u, p = 0):
  vis[u] = True
  for v in g[u]:
    if v != p:
      dfs(v, u)

n, m = map(int, input().split())
g = [list() for i in range(n + 1)]
for i in range(m):
  u, v = map(int, input().split())
  g[u].append(v)
  g[v].append(u)
c = 0
vis = [False] * (n + 1)
for i in range(1, n + 1):
  if not vis[i]:
    c += 1
    dfs(i)
print(c - 1 if c else 0)


Fixed submission:
import sys
sys.setrecursionlimit(int(2e6))

def dfs(u, p = 0):
  vis[u] = True
  for v in g[u]:
    if not vis[v]:
      dfs(v, u)

n, m = map(int, input().split())
assert 2 <= n <= int(1e5)
assert 1 <= m <= int(1e5)
g = [list() for i in range(n + 1)]
for i in range(m):
  u, v = map(int, input().split())
  assert 1 <= u <= int(1e5)
  assert 1 <= v <= int(1e5)
  assert u < v
  g[u].append(v)
  g[v].append(u)
c = 0
vis = [False] * (n + 1)
for i in range(1, n + 1):
  if not vis[i]:
    c += 1
    dfs(i)
print(c - 1)

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(int(2e6))

def dfs(u, p = 0):
  for v in g[u]:
    if v != p:
      dfs(v, u)
  g[u] = None

n, m = map(int, input().split())
g = [list() for i in range(n + 1)]
for i in range(m):
  u, v = map(int, input().split())
  g[u].append(v)
  g[v].append(u)
c = 0
for i in range(1, n + 1):
  if g[i] is not None:
    c += 1
    dfs(i)
print(c - 1 if c else 0)


Fixed submission:
import sys
sys.setrecursionlimit(int(2e6))

def dfs(u, p = 0):
  vis[u] = True
  for v in g[u]:
    if not vis[v]:
      dfs(v, u)

n, m = map(int, input().split())
assert 2 <= n <= int(1e5)
assert 1 <= m <= int(1e5)
g = [list() for i in range(n + 1)]
for i in range(m):
  u, v = map(int, input().split())
  assert 1 <= u <= int(1e5)
  assert 1 <= v <= int(1e5)
  assert u < v
  g[u].append(v)
  g[v].append(u)
c = 0
vis = [False] * (n + 1)
for i in range(1, n + 1):
  if not vis[i]:
    c += 1
    dfs(i)
print(c - 1)

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(int(1e6))

def dfs(u, p = 0):
  for v in g[u]:
    if v != p:
      dfs(v, u)
  g[u] = None


n, m = map(int, input().split())
g = [list() for i in range(n + 1)]
for i in range(m):
  u, v = map(int, input().split())
  g[u].append(v)
  g[v].append(u)
c = 0
for i in range(1, n + 1):
  if g[i] is not None:
    c += 1
    dfs(i)
print(c - 1 if c else 0)


Fixed submission:
import sys
sys.setrecursionlimit(int(2e6))

def dfs(u, p = 0):
  vis[u] = True
  for v in g[u]:
    if not vis[v]:
      dfs(v, u)

n, m = map(int, input().split())
assert 2 <= n <= int(1e5)
assert 1 <= m <= int(1e5)
g = [list() for i in range(n + 1)]
for i in range(m):
  u, v = map(int, input().split())
  assert 1 <= u <= int(1e5)
  assert 1 <= v <= int(1e5)
  assert u < v
  g[u].append(v)
  g[v].append(u)
c = 0
vis = [False] * (n + 1)
for i in range(1, n + 1):
  if not vis[i]:
    c += 1
    dfs(i)
print(c - 1)
Buggy python submission (verdict: Runtime Error):
n=int(input())
s=input()
t=input()
i=0
while i<n:
    print(s[i]+t[i],end="")
    i+=1

Fixed submission:
n=int(input())
s,t=input().split()
i=0
while i<n:
    print(s[i]+t[i],end="")
    i+=1
Buggy python submission (verdict: Runtime Error):
print(r*r*3)


Fixed submission:
r=int(input())
ans=r*r*3
print(ans)
Buggy python submission (verdict: Runtime Error):


def solve(N,X,M):
    memo = [-1]*(M+3)
    acc = [0]*(M+4)
    x = X
    for i in range(M):
        if memo[x] >= 0:
            break
        acc[i+1] = acc[i]+x
        memo[x] = i
        x = (x*x)%M


    end = i
    start = memo[x]
    cycle = end - start

    if N < end:
        return acc[N]

    cycle_sum = acc[end]-acc[start]

    res = acc[start]

    N -= start
    res += (N//cycle)*cycle_sum
    res += acc[start+(N%cycle)]-acc[start]
    return res


N,X,M = map(int,input().split())
print(solve(N,X,M))


Fixed submission:


def solve(N,X,M):
    if X == 0:
        return 0
    memo = [-1]*(M+3)
    acc = [0]*(M+4)
    x = X
    for i in range(M):
        if memo[x] >= 0:
            break
        acc[i+1] = acc[i]+x
        memo[x] = i
        x = (x*x)%M


    end = i
    start = memo[x]
    cycle = end - start

    if N < end:
        return acc[N]

    cycle_sum = acc[end]-acc[start]

    res = acc[start]

    N -= start
    res += (N//cycle)*cycle_sum
    res += acc[start+(N%cycle)]-acc[start]
    return res


N,X,M = map(int,input().split())
print(solve(N,X,M))

Buggy python submission (verdict: Runtime Error):


def solve(N,X,M):
    memo = [-1]*M
    acc = [0]*(M+1)
    x = X%M
    for i in range(M):
        if memo[x] >= 0:
            break
        acc[i+1] = acc[i]+x
        memo[x] = i
        x = (x*x)%M


    end = i
    start = memo[x]
    cycle = end - start

    if N < end:
        return acc[N]+(X - X%M)

    cycle_sum = acc[end]-acc[start]

    res = acc[start]+(X - X%M)

    N -= start
    res += (N//cycle)*cycle_sum
    res += acc[start+(N%cycle)]-acc[start]
    return res

N,X,M = map(int,input().split())
print(solve(N,X,M))


Fixed submission:


def solve(N,X,M):
    if X == 0:
        return 0
    memo = [-1]*(M+3)
    acc = [0]*(M+4)
    x = X
    for i in range(M):
        if memo[x] >= 0:
            break
        acc[i+1] = acc[i]+x
        memo[x] = i
        x = (x*x)%M


    end = i
    start = memo[x]
    cycle = end - start

    if N < end:
        return acc[N]

    cycle_sum = acc[end]-acc[start]

    res = acc[start]

    N -= start
    res += (N//cycle)*cycle_sum
    res += acc[start+(N%cycle)]-acc[start]
    return res


N,X,M = map(int,input().split())
print(solve(N,X,M))
Buggy python submission (verdict: Runtime Error):
def floor_linear_sum(n,m,a,b):
    """
    returns sum((a*i+b)//m for i in range(n))
    """
    res = 0
    while True:
        if a >= m:
            res += (n-1)*n*(a//m)//2
            a %= m
        if b >= m:
            res += n * (b//m)
            b %= m

        y_max = (a*n+b)//m
        if y_max == 0:
            return res
        nx_max = b - y_max*m
        res += (n + nx_max//a)*y_max
        n,m,a,b = y_max, a, m, nx_max%a

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

T = readline()
m = map(int,read().split())
for t in zip(m,m,m,m):
    print(solve(*t))

Fixed submission:
def floor_linear_sum(n,m,a,b):
    res = 0
    while True:
        if a >= m:
            res += (n-1)*n*(a//m)//2
            a %= m
        if b >= m:
            res += n * (b//m)
            b %= m

        y_max = (a*n+b)//m
        if y_max == 0:
            return res
        x_max = y_max*m-b
        res += (n - (x_max + a - 1)//a)*y_max
        n,m,a,b = y_max, a, m, (a-x_max)%a

T = int(input())
for _ in range(T):
    print(floor_linear_sum(*map(int,input().split())))