Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
N,M=map(int,input().split())
AB=list()
memo=[False]*N
G=defaultdict(list)
def dfs(G,i):
    memo[i]=True
    for j in G[i]:
        if memo[j]==False:
            dfs(G,j)
count=0
for i in range(M):
    AB=list(map(int,input().split()))
    G[AB[1]-1].append(AB[0]-1)
    G[AB[0]-1].append(AB[1]-1)
for i in range(N):
    if memo[i]==False:
        dfs(G,i)
        count+=1
print(count-1)

Fixed submission:
K=int(input())
print("ACL"*K)
Buggy python submission (verdict: Time Limit Exceeded):
def listseki(A,start,end):
    ans=1
    for i in range(start,end+1):
        ans*=A[i]
    return ans
N,K=map(int,input().split())
A=list(map(int,input().split()))
oldseki=listseki(A,0,K-1)
for i in range(1,N-K+1):
    nowseki=listseki(A,i,i+K-1)
    if nowseki>oldseki:
        print("Yes")
    else:
        print("No")
    oldseki=nowseki

Fixed submission:
def listseki(A,start,end):
    ans=A[end]/A[start-1]
    return ans
N,K=map(int,input().split())
A=list(map(int,input().split()))
for i in range(1,N-K+1):
    nowseki=listseki(A,i,i+K-1)
    if nowseki>1:
        print("Yes")
    else:
        print("No")
Buggy python submission (verdict: Runtime Error):
def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]
N=int(input())
A=list(map(int,input().split()))
Q=int(input())
BC=[]
for i in range(Q):
    BC.append(list(map(int,input().split())))
for i in BC:
    if i[0] in A:
        indexlist=my_index_multi(A,i[0])
        for j in indexlist:
            A[j]=i[1]
    print(sum(A))

Fixed submission:
def num2alpha(num):
    if num<=26:
        return chr(64+num)
    elif num%26==0:
        return num2alpha(num//26-1)+chr(90)
    else:
        return num2alpha(num//26)+chr(64+num%26)
N=int(input())
print(num2alpha(N).lower())

Buggy python submission (verdict: Runtime Error):
def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]
N=int(input())
A=list(map(int,input().split()))
Q=int(input())
BC=[]
for i in range(Q):
    BC.append(list(map(int,input().split())))
for i in BC:
    if i[0] in A:
        indexlist=my_index_multi(A,i[0])
        for j in indexlist:
            A[j]=i[1]
    print(sum(A))

Fixed submission:
def num2alpha(num):
    if num<=26:
        return chr(64+num)
    elif num%26==0:
        return num2alpha(num//26-1)+chr(90)
    else:
        return num2alpha(num//26)+chr(64+num%26)
N=int(input())
print(num2alpha(N).lower())
Buggy python submission (verdict: Time Limit Exceeded):
def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]
N=int(input())
A=list(map(int,input().split()))
Q=int(input())
BC=[]
for i in range(Q):
    BC.append(list(map(int,input().split())))
for i in BC:
    if i[0] in A:
        indexlist=my_index_multi(A,i[0])
        for j in indexlist:
            A[j]=i[1]
    print(sum(A))

Fixed submission:
import collections
def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]
N=int(input())
A=list(map(int,input().split()))
goukei=sum(A)
Q=int(input())
BC=[]
for i in range(Q):
    BC.append(list(map(int,input().split())))
c = collections.Counter(A)
for i in BC:
    goukei+=c[i[0]]*(i[1]-i[0])
    c[i[1]]=c[i[0]]+c[i[1]]
    c[i[0]]=0
    print(goukei)

Buggy python submission (verdict: Time Limit Exceeded):
def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]
N=int(input())
A=list(map(int,input().split()))
Q=int(input())
BC=[]
for i in range(Q):
    BC.append(list(map(int,input().split())))
for i in BC:
    indexlist=my_index_multi(A,i[0])
    for j in indexlist:
        A[j]=i[1]
    print(sum(A))

Fixed submission:
import collections
def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]
N=int(input())
A=list(map(int,input().split()))
goukei=sum(A)
Q=int(input())
BC=[]
for i in range(Q):
    BC.append(list(map(int,input().split())))
c = collections.Counter(A)
for i in BC:
    goukei+=c[i[0]]*(i[1]-i[0])
    c[i[1]]=c[i[0]]+c[i[1]]
    c[i[0]]=0
    print(goukei)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=list(map(int,input().split()))
Q=int(input())
BC=[]
for i in range(Q):
    BC.append(list(map(int,input().split())))
for i in BC:
    for j in range(N):
        if A[j]==i[0]:
            A[j]=i[1]
    print(sum(A))

Fixed submission:
import collections
def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]
N=int(input())
A=list(map(int,input().split()))
goukei=sum(A)
Q=int(input())
BC=[]
for i in range(Q):
    BC.append(list(map(int,input().split())))
c = collections.Counter(A)
for i in BC:
    goukei+=c[i[0]]*(i[1]-i[0])
    c[i[1]]=c[i[0]]+c[i[1]]
    c[i[0]]=0
    print(goukei)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
N=int(input())
ans=1
numbers=input().split()
for j in range(N):
  num=int(numbers[j])
  ans=ans*num
  if ans==0:
    print(0)
    sys.exit()
if ans>1000000000000000000:
  print(-1)
  sys.exit()
print(ans)

Fixed submission:
import sys
N=int(input())
ans=1
numbers=input().split()
zero="0" in numbers
if zero:
  print(0)
  sys.exit()
for j in range(N):
  num=int(numbers[j])
  ans=ans*num
  if ans>1000000000000000000:
    print(-1)
    sys.exit()
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
LR=list(range(N+1))
for i in range(M):
    L,R=map(int,input().split())
    LR=list(set(list(range(L,R+1))) & set(LR))
print(len(LR))

Fixed submission:
N,M=map(int,input().split())
LR=set(range(N+1))
l=[]
r=[]
for i in range(M):
    L,R=map(int,input().split())
    l.append(L)
    r.append(R)
ans=min(r)-max(l)+1
if ans<0:
    ans=0
print(ans)
Buggy python submission (verdict: Runtime Error):
import math
A,B,K=map(int,input().split())
anslist=[]
for i in range(1,max(A,B)):
    if (A%i==0)&(B%i==0):
        anslist.append(i)
print(anslist[0-K])

Fixed submission:
import math
A,B,K=map(int,input().split())
anslist=[]
for i in range(1,max(A,B)+1):
    if (A%i==0)&(B%i==0):
        anslist.append(i)
print(anslist[0-K])
Buggy python submission (verdict: Runtime Error):
N,K=map(int,input().split())
h=list(map(int,input().split()))
dp=[1000000000000000]*N
dp[0]=0
for i in range(N-1):
    for j in range(1,K+1):
        try:
            dp[i+j]=min(dp[i+j],dp[i]+abs(h[i+j]-h[i]))
        except:
            break
print(dp[N-1])

Fixed submission:
N=int(input())
h=list(map(int,input().split()))
dp=[0]*N
dp[1]=abs(h[1]-h[0])
for i in range(2,N):
    dp[i]=min(dp[i-2]+abs(h[i]-h[i-2]),dp[i-1]+abs(h[i]-h[i-1]))
print(dp[N-1])
Buggy python submission (verdict: Time Limit Exceeded):
def change(A,B,C):
    move=True
    a=A
    b=B
    c=C
    A=b+c
    B=a+c
    C=a+b
    if B-A==b-a:
        move=False
    return A,B,C,move
A,B,C,K=map(int,input().split())
ans=A-B
for i in range(K):
    A,B,C,move=change(A,B,C)
    ans=A-B
    if abs(ans)>1000000000000000000:
        print("Unfair")
        break
    elif not(move):
        print(ans)
        break
else:
    print(ans)

Fixed submission:
A,B,C,K=map(int,input().split())
if K%2==0:
    ans=A-B
else:
    ans=B-A
if ans>1000000000000000000:
    ans="Unfair"
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
def change(A,B,C):
    move=True
    a=A
    b=B
    c=C
    A=b+c
    B=a+c
    C=a+b
    if (a==A)&(b==B)&(c==C):
        move=False
    return A,B,C,move
A,B,C,K=map(int,input().split())
ans=A-B
for i in range(K):
    A,B,C,move=change(A,B,C)
    ans=A-B
    if abs(ans)>1000000000000000000:
        print("Unfair")
        break
    elif not(move):
        print(ans)
        break
    elif A==B:
        print(0)
        break
else:
    print(ans)

Fixed submission:
A,B,C,K=map(int,input().split())
if K%2==0:
    ans=A-B
else:
    ans=B-A
if ans>1000000000000000000:
    ans="Unfair"
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
K,S=map(int,input().split())
count=0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x+y+z==S:
                count+=1
print(count)

Fixed submission:
K,S=map(int,input().split())
count=0
for x in range(K+1):
    for y in range(K+1):
        if 0<=S-x-y<=K:
            count+=1
print(count)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))
mod = 1000000007
sum = 0
for i in range(N-1):
    for j in range(i+1,N):
        add = (A[i]*A[j]) % mod
        sum = sum + add
        sum = sum % mod
print(sum)


Fixed submission:
N = int(input())
A = list(map(int,input().split()))
mod = 1000000007
sum_A = (sum(A)**2) % mod
B = list(map(lambda x: (x**2)% mod,A))
sum_B = sum(B) % mod
print(((sum_A-sum_B)*500000004)%mod)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = []
c = input()
S.extend(c)

if "W" in S and "R" in S:
    for i in range(N):
        S_r = S[::-1]
        min_W = S.index("W")
        max_R = N - 1 - S_r.index("R")
        if min_W>max_R:
            print(i)
            break
        S[min_W],S[max_R] = S[max_R],S[min_W]
else:
    print(0)

Fixed submission:
N = int(input())
S = []
c = input()
S.extend(c)

if "W" in S and "R" in S:
    t = S.count("R")
    S = S[:t]
    r = S.count("W")
    print(r)
else:
    print(0)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = []
c = input()
S.extend(c)
if "W" in S and "R" in S:
    for i in range(N):
        min_W = S.index("W")
        max_R = N - 1 - S[::-1].index("R")
        S[::-1]
        if min_W>max_R:
            print(i)
            break
        S[min_W],S[max_R] = S[max_R],S[min_W]
else:
    print(0)

Fixed submission:
N = int(input())
S = []
c = input()
S.extend(c)

if "W" in S and "R" in S:
    t = S.count("R")
    S = S[:t]
    r = S.count("W")
    print(r)
else:
    print(0)
Buggy python submission (verdict: Runtime Error):

N = int(input())
X = int(input(), 2)
m = [-1]
p = [-1]
# したからi番目を反転
def reverse_x(i,x):
    a = 1<<i
    b = x^a
    return b
def f(n):
    def popcount(n):
        c = bin(n).count("1")
        return c
    count = 0
    if n % popcount(n) in m:
        count = p[m.index(n%popcount(n))]
        n = 0
    else:
        m.append(n % popcount(n))
    while n != 0:
        n = n % popcount(n)
        count += 1
    p.append(count)
    return count
for i in range(N):
    print(f(reverse_x(N-i-1,X)))


Fixed submission:
L,R,d = map(int,input().split())
count = 0
for i in range(L,R+1):
    if i % d == 0:
        count += 1
print(count)
Buggy python submission (verdict: Runtime Error):
import random
D = int(input())
c = list(map(int,input().split()))
s = []
for i in range(D):
    s.append(list(map(int,input().split())))
t = [0]*D
def my_index(l,x,d,default=False):
    if x in l:
        return l.index(x)
    else:
        return d
def last(d,i):
    a= t[:d]
    a.reverse()
    day = -1*(my_index(a,i,d))+d
    return day
score = 0
score_v=0
for i in range(50):
    t_old = t
    d_change = random.randint(1,D)
    q_change = random.randint(1,26)
    t[d_change]=q_change
    for d in range(1,D+1):
        score_v += s[d-1][t[d-1]-1]
        for i in range(1,27):
            score_v -= c[i-1]*(d-last(d,i))
            if score_v>score:
                score=score_v
            else:
                t = t_old
for i in range(D):
    print(t[i])

Fixed submission:
import random
D = int(input())
c = list(map(int,input().split()))
s = []
for i in range(D):
    s.append(list(map(int,input().split())))
t = [1]*D
def my_index(l,x,d,default=False):
    if x in l:
        return l.index(x)
    else:
        return d
def last(d,i):
    a= t[:d]
    a.reverse()
    day = -1*(my_index(a,i,d))+d
    return day
score = 0
for i in range(40):
    score_v=0
    t_old = t
    d_change = random.randint(0,D-1)
    q_change = random.randint(1,26)
    t[d_change]=q_change
    for d in range(1,D+1):
        score_v += s[d-1][t[d-1]-1]
        for i in range(1,27):
            score_v -= c[i-1]*(d-last(d,i))
    if score_v>score:
        score=score_v
    else:
        t = t_old
for i in range(D):
    print(t[i])
Buggy python submission (verdict: Runtime Error):
N,M,K=map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
sum_A=0
sum_B=0
for i in range(min(N,M)):
    sum_A +=A[i]
    sum_B +=B[i]
    if sum_A>K:
        del A[i:]
    if sum_B>K:
        del B[i:]
    if sum_A>K and sum_A>K:
        break
while sum(A)+sum(B)>K:
    if A[-1]>B[-1]:
        del A[-1]
    elif A[-1]<B[-1]:
        del B[-1]
    elif A[-1] == B[-1]:
        del A[-1]
        del B[-1]
        if sum(A)+sum(B)<=K:
            A.append(1)
print(len(A)+len(B))


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

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

Buggy python submission (verdict: Time Limit Exceeded):
N,M,K=map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
sum_A=0
sum_B=0
for i in range(N):
    sum_A +=A[i]
    if sum_A>K:
        del A[i:]
        break
for i in range(M):
    sum_B +=B[i]
    if sum_B>K:
        del B[i:]
        break
while sum(A)+sum(B)>K:
    if A[-1]>B[-1]:
        del A[-1]
    elif A[-1]<B[-1]:
        del B[-1]
    elif A[-1] == B[-1]:
        del A[-1]
        del B[-1]
        if sum(A)+sum(B)<=K:
            A.append(1)
print(len(A)+len(B))

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

a, b = [0], [0]
for i in range(N):
	a.append(a[i] + A[i])
for i in range(M):
	b.append(b[i] + B[i])
ans, j = 0, M
for i in range(N + 1):
	if a[i] > K:
 		break
	while b[j] > K - a[i]:
		j -= 1
	ans = max(ans, i + j)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A= list(map(int,input().split()))
p = 1
for i in range(N):
    p = p * A[i]
if p > 10**18:
    p = -1
print(p)

Fixed submission:
N = int(input())
A = list(map(int,input().split()))
p = 1
if A.count(0)>0:
    p = 0
for i in range(N):
    p = p * A[i]
    if p > 10**18:
        p=-1
        break
    if p == 0:
        break
print(p)
Buggy python submission (verdict: Runtime Error):
N,M = map(int,input().split())
A = list(map(int,input().split()))
A = sorted(A, reverse=True)
if A[M-1]<(Sum(A)/(4*M)):
  print("No")
else:
  print("Yes")

Fixed submission:
N,M = map(int,input().split())
A = list(map(int,input().split()))
A = sorted(A, reverse=True)
if A[M-1]<(sum(A)/(4*M)):
    print("No")
else:
    print("Yes")
Buggy python submission (verdict: Runtime Error):
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t, n, ma = -1;
    ll ans = 0;
    cin >> n;
    while(n--){
        cin >> t;
        ma = max(ma, t);
        ans += (ma - t);
    }
    cout << ans;
    return 0;
}


Fixed submission:
n = int(input())
a = [int(x) for x in input().split()]
ma = 0
ans = 0
for i in a:
    ma = max(ma, i)
    ans += (ma - i)
print(ans)
Buggy python submission (verdict: Runtime Error):
N, K = input().split()
K = int(K)
count = 1  # 最初は必ず含む
l = []
l_true = []
S = 0
S1 = 1
for i in range(int(N)):
    l.append(int(input()))
for S1 in range(int(N)):
   for i in range(int(N)):
       if abs(l[S] - l[S1]) <= K:
            l_true.append(A2)
            count += 1
            S += 1
            S1 += 1
        else:
            pass


print(count)

Fixed submission:
K = input()
ALC = ""
for i in range(int(K)):
    ALC += "ACL"
print(ALC)
Buggy python submission (verdict: Runtime Error):
a, op, b = input().split()
a, b = map(int())
if op = "+":
  print(a + b)
elif op = "-":
  print(a - b)
else:
  pass

Fixed submission:
a, op, b = input().split()
a = int(a)
b = int(b)
if op == "+":
    print(a + b)
elif op == "-":
    print(a - b)
else:
    pass
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split(" "))
a=list(map(int,input().split(" ")))

sum=1

for i in range(k-1):
    sum*=a[i]

hoge=[0 for i in range(n)]

for i in range(k-1,n):
    sum*=a[i]
    hoge[i]=sum
    sum=sum//a[i-k+1]

for i in range(k,n):
    #print(hoge[i-1],hoge[i],end=" ")
    if hoge[i-1]<hoge[i]:
        print("Yes")
    else:
        print("No")


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


for i in range(k,n):
    #print(hoge[i-1],hoge[i],end=" ")
    if a[i-k]<a[i]:
        print("Yes")
    else:
        print("No")
Buggy python submission (verdict: Runtime Error):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod = 998244353
INF = 10**18
eps = 10**-7

n,k = map(int,readline().split())
LR = [list(map(int,readline().split())) for i in range(k)]



dp = [0]*(2*n+1)

imos = [0]*(2*n+1)
dp[1] = 1
for i in range(1,n+1):
    imos[i] = (imos[i-1]+imos[i])%mod
    dp[i] = (dp[i]+imos[i])%mod
    for (l,r) in LR:
        imos[i+l] += dp[i]
        imos[i+r+1] -= dp[i]

print(dp[n])




Fixed submission:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod = 998244353
INF = 10**18
eps = 10**-7

n,k = map(int,readline().split())
LR = [list(map(int,readline().split())) for i in range(k)]



dp = [0]*(2*n+10)

imos = [0]*(2*n+10)
dp[1] = 1
for i in range(1,n+1):
    imos[i] = (imos[i-1]+imos[i])%mod
    dp[i] = (dp[i]+imos[i])%mod
    for (l,r) in LR:
        imos[i+l] += dp[i]
        imos[i+r+1] -= dp[i]

print(dp[n])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod = 998244353
INF = 10**18
eps = 10**-7

n,k = map(int,readline().split())
vec = [0]*(n+1)
for i in range(k):
    l,r = map(int,readline().split())
    for j in range(l,r+1):
        vec[j] = 1

to = []

for i in range(1,n+1):
    if vec[i] == 1:
        to.append(i)

dp = [0]*(n+1)
dp[1] = 1
for i in range(1,n+1):
    for j in to:
        if (i+j > n):
            break
        dp[i+j] = (dp[i]+dp[i+j])%mod

print(dp[n])



Fixed submission:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod = 998244353
INF = 10**18
eps = 10**-7

n,k = map(int,readline().split())
LR = [list(map(int,readline().split())) for i in range(k)]



dp = [0]*(2*n+10)

imos = [0]*(2*n+10)
dp[1] = 1
for i in range(1,n+1):
    imos[i] = (imos[i-1]+imos[i])%mod
    dp[i] = (dp[i]+imos[i])%mod
    for (l,r) in LR:
        imos[i+l] += dp[i]
        imos[i+r+1] -= dp[i]

print(dp[n])
Buggy python submission (verdict: Runtime Error):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod = 998244353
INF = 10**18
eps = 10**-7

n,x,m = map(int,readline().split())

if n == 1:
    print(x)
    exit()

if n < 10**7:
    a = [0]*n
    a[0] = x
    for i in range(n-1):
        a[i+1] = a[i]**2%m
    print(sum(a))
    exit()

a = [0]*m
a[0] = x

for i in range(m-1):
    a[i+1] = a[i]**2%m

idx = [-1]*m

for i in range(m):
    if (idx[a[i]] == -1):
        idx[a[i]] = i
    else:
        idxx = idx[a[i]]
        now = i
        break

d = sum(a[idxx:now])
l = now-idxx
ans = sum(a[:idxx])
n -= idxx
ans += d*(n//l)
n = n%l
ans += sum(a[idxx:idxx+n])
print(ans)







Fixed submission:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod = 998244353
INF = 10**18
eps = 10**-7

n,x,m = map(int,readline().split())

if n == 1:
    print(x)
    exit()

if n < 10**7:
    a = [0]*n
    a[0] = x
    for i in range(n-1):
        a[i+1] = a[i]**2%m
    print(sum(a))
    exit()



a = [0]*(m+10)
a[0] = x

for i in range(m+5):
    a[i+1] = a[i]**2%m

idx = [-1]*m

for i in range(m+5):
    if (idx[a[i]] == -1):
        idx[a[i]] = i
    else:
        idxx = idx[a[i]]
        now = i
        break

d = sum(a[idxx:now])
l = now-idxx
ans = sum(a[:idxx])
n -= idxx
ans += d*(n//l)
n = n%l
ans += sum(a[idxx:idxx+n])
print(ans)

Buggy python submission (verdict: Runtime Error):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod = 998244353
INF = 10**18
eps = 10**-7

n,x,m = map(int,readline().split())

if n < 10**7:
    a = [0]*n
    a[0] = x
    for i in range(n-1):
        a[i+1] = a[i]**2%m
    print(sum(a))
    exit()

a = [0]*m
a[0] = x

for i in range(m-1):
    a[i+1] = a[i]**2%m

idx = [-1]*m

for i in range(m):
    if (idx[a[i]] == -1):
        idx[a[i]] = i
    else:
        idxx = idx[a[i]]
        now = i
        break

d = sum(a[idxx:now])
l = now-idxx
ans = sum(a[:idxx])
n -= idxx
ans += d*(n//l)
n = n%l
ans += sum(a[idxx:idxx+n])
print(ans)







Fixed submission:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod = 998244353
INF = 10**18
eps = 10**-7

n,x,m = map(int,readline().split())

if n == 1:
    print(x)
    exit()

if n < 10**7:
    a = [0]*n
    a[0] = x
    for i in range(n-1):
        a[i+1] = a[i]**2%m
    print(sum(a))
    exit()



a = [0]*(m+10)
a[0] = x

for i in range(m+5):
    a[i+1] = a[i]**2%m

idx = [-1]*m

for i in range(m+5):
    if (idx[a[i]] == -1):
        idx[a[i]] = i
    else:
        idxx = idx[a[i]]
        now = i
        break

d = sum(a[idxx:now])
l = now-idxx
ans = sum(a[:idxx])
n -= idxx
ans += d*(n//l)
n = n%l
ans += sum(a[idxx:idxx+n])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N,S = map(int,input().split())
A = list(map(int,input().split()))
dp = [[0]*(S+2) for i in range(N+1)]
dp[0][0] = 1
mod = 998244353
for i,a in enumerate(A):
    for j in range(S+1):
        if j-a >= 0:
            dp[i+1][j] = (dp[i][j]*2+dp[i][j-a])%mod
        else:
            dp[i+1][j] = dp[i][j]*2%mod
print(dp[N][S])


Fixed submission:
N,S = map(int,input().split())
A = list(map(int,input().split()))
dp = [[0 for j in range(S+2)] for i in range(N+1)]
dp[0][0] = 1
mod = 998244353
for i,a in enumerate(A):
    for j in range(S+1):
        if j-a >= 0:
            dp[i+1][j] = (dp[i][j]*2+dp[i][j-a])%mod
        else:
            dp[i+1][j] = dp[i][j]*2%mod

print(dp[N][S])
Buggy python submission (verdict: Time Limit Exceeded):
# ダブリング
 
N,K = map(int,input().split())
A = [-1] + list(map(int,input().split()))
 
D = 60
 
to = [[-1 for i in range(N+1)] for j in range(D)]
to[0] = A
 
for i in range(1,D):
    for j in range(1,N+1):
        to[i][j] = to[i-1][to[i-1][j]]
 
ans = 1
for i in range(D):
    if K>>i&1:
        ans = to[i][ans]
 
print(ans)

Fixed submission:
N,K = map(int,input().split())
A = [-1] + list(map(int,input().split()))

visit = [False for i in range(N+1)]
now = 1
cnt = 0
while True:
    if visit[now]:
        break
    visit[now] = True
    now = A[now]
    cnt += 1
cnt2 = 0
visit2 = [False for i in range(N+1)]
while True:
    if visit2[now]:
        break
    visit2[now] = True
    now = A[now]
    cnt2 += 1

if cnt >= K:
    ans = 1
    for i in range(K):
        ans = A[ans]

else:
    K -= cnt
    K = K%cnt2
    ans = now
    for i in range(K):
        ans = A[ans]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
# ダブリング

N,K = map(int,input().split())
A = [-1] + list(map(int,input().split()))

D = 60

to = [[-1 for i in range(N+1)] for j in range(D)]
to[0] = A

for i in range(1,D):
    for j in range(1,N+1):
        to[i][j] = to[i-1][to[i-1][j]]

ans = 1
for i in range(D):
    if K>>i&1:
        ans = to[i][ans]

print(ans)


Fixed submission:
N,K = map(int,input().split())
A = [-1] + list(map(int,input().split()))

visit = [False for i in range(N+1)]
now = 1
cnt = 0
while True:
    if visit[now]:
        break
    visit[now] = True
    now = A[now]
    cnt += 1
cnt2 = 0
visit2 = [False for i in range(N+1)]
while True:
    if visit2[now]:
        break
    visit2[now] = True
    now = A[now]
    cnt2 += 1

if cnt >= K:
    ans = 1
    for i in range(K):
        ans = A[ans]

else:
    K -= cnt
    K = K%cnt2
    ans = now
    for i in range(K):
        ans = A[ans]
print(ans)