Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
# import sys
# sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

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

from math import ceilf
from fractions import gcd

def solve():
    a, b, c, d = MI()

    e = b // c
    f = ceil(a / c)
    c2 = e - f + 1
    g = b // d
    h = ceil(a / d)
    d2 = g - h + 1

    cd = lcm(c, d)
    cdr = b // cd
    cdl = ceil(a / cd)
    cd2 = cdr - cdl + 1
    # print(c2, d2, cd2)
    print(b - a + 1 - c2 - d2 + cd2)


if __name__ == '__main__':
    solve()


Fixed submission:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def printlist(lst, k='\n'): return k.join(list(map(str, lst)))
INF = float('inf')

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

def f(x, c, d):
    r = x
    r -= x // c
    r -= x // d
    r += x // lcm(c, d)
    return r

def f2(n, C, D):
    return n - n//C - n//D + n//lcm(C, D)

def solve():
    a, b, c, d = MI()

    # g = lcm(c, d)
    # bb = b - (b // c) - (b // d) + (b // g)
    # a = a - 1
    # aa = a - (a // c) - (a // d) + (a // g)
    # print(bb - aa)
    print(f(b, c, d) - f(a-1, c, d))
    # print(f2(b, c, d) - f2(a-1, c, d))


if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    N = II()
    X = [0] * N
    Y = [0] * N
    for i in range(N):
        x, y = MI()
        X[i], Y[i] = x, y

    dct = defaultdict(int)
    for i in range(N):
        for j in range(N):
            if i == j: continue
            xi, yi = X[i], Y[i]
            xj, yj = X[j], Y[j]

            dct[(xi-xj, yi-yj)] += 1
    # print(dct)
    print(N - max(dct.values()))


if __name__ == '__main__':
    solve()



Fixed submission:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    N = II()
    X = [0] * N
    Y = [0] * N
    for i in range(N):
        x, y = MI()
        X[i], Y[i] = x, y

    dct = defaultdict(int)
    for i in range(N):
        for j in range(N):
            if i == j: continue
            xi, yi = X[i], Y[i]
            xj, yj = X[j], Y[j]

            dct[(xi-xj, yi-yj)] += 1
    # print(dct)
    mx = 0
    for d in dct.values():
        mx = max(mx, d)
    print(N - mx)


if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Runtime Error):
import sys
 
sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7
 
 
def input():
    return sys.stdin.readline().strip()
 
 
def main():
    N, M = map(int, input().split())
    dp = [0] * (N + 1)
    safe = [True] * (N + 1)
    for _ in range(M):
        a = int(input())
        safe[a] = False
 
    dp[0] = 1
    for i in range(1, N + 1):
        if i == 1 and safe[i]:
            dp[i] = dp[i - 1]
        else:
            if safe[i]:
                dp[i] = dp[i - 1] + dp[i - 2]
                dp[i] %= MOD
 
    print(dp[-1])
 
 
if __name__ == "__main__":
    main()

Fixed submission:
p, q, r = map(int, input().split())
print(min(p+q, min(q+r, r+p)))
Buggy python submission (verdict: Time Limit Exceeded):
# import sys
# sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def logical_and(lst, l, r):
    res = []
    for i in range(l, r+1):
        if i in lst:
            res.append(i)
    return res

def solve():
    n, m = MI()

    l, r = MI()
    ans = list(range(l, r+1))
    for _ in range(m-1):
        l, r = MI()
        ans = logical_and(ans, l, r)
    print(len(ans))


if __name__ == '__main__':
    solve()


Fixed submission:
# import sys
# sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def solve():
    n, m = MI()

    maxl, minr = MI()
    for _ in range(m-1):
        l, r = MI()
        if maxl < l:
            maxl = l
        if r < minr:
            minr = r
    if maxl <= minr:
        print(minr - maxl + 1)
    else:
        print(0)

if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SMI(): return input().split()
def SLI(): return list(input())

def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')

# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate
# from fractions import gcd

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return sorted(divisors, reverse=True)

def solve():
    N = II()
    A = LI()

    p = 1
    l = 1
    for a in A:
        l = lcm(p, a)
        p = a

    div = make_divisors(l)

    for d in div:
        no = 1
        for a in A:
            if a % d == 0:
                continue
            else:
                no -= 1
                if no < 0:
                    break
        else:
            print(d)
            return
    print(1)



if __name__ == '__main__':
    solve()


Fixed submission:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SMI(): return input().split()
def SLI(): return list(input())

def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')

# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

from fractions import gcd

def solve():
    N = II()
    A = LI()

    # 左から累積和的gcd
    L = [1] * N
    L[0] = A[0]
    for i in range(1, N):
        L[i] = gcd(A[i], L[i-1])

    # 右から累積和的gcd
    R = [1] * N
    R[-1] = A[-1]
    for i in range(N-2, -1, -1):
        R[i] = gcd(A[i], R[i+1])

    # print(L)
    # print(R)
    ans = 1
    for i, a in enumerate(A):
        l = i - 1
        r = i + 1
        if l < 0:
            ans = max(ans, R[r])
        elif r >= N:
            ans = max(ans, L[l])
        else:
            ans = max(ans, gcd(L[l], R[r]))
    print(ans)

if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')

def solve():
    n, q = MI()
    S = input()
    for _ in range(q):
        l, r = MI1()
        s = S[l:r+1]
        # print(s, s.count('AC'))
        print(s.count('AC'))

if __name__ == '__main__':
    solve()


Fixed submission:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')

def solve():
    n, q = MI()
    S = input()
    ats = [0]
    cnt = 0
    for i in range(n-1):
        j = i + 2
        s = S[i:j]
        # print(s)
        if s == 'AC':
            cnt += 1
        ats.append(cnt)
    # print(ats)
    for _ in range(q):
        l, r = MI1()
        # print(S[l:r+1])
        print(ats[r] - ats[l])


if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')

def solve():
    n, q = MI()
    S = input()
    for _ in range(q):
        l, r = MI1()
        s = S[l:r+1]
        # print(s, s.count('AC'))
        print(s.count('AC'))

if __name__ == '__main__':
    solve()


Fixed submission:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')

def solve():
    n, q = MI()
    S = input()
    ats = [0]
    cnt = 0
    for i in range(n-1):
        j = i + 2
        s = S[i:j]
        # print(s)
        if s == 'AC':
            cnt += 1
        ats.append(cnt)
    # print(ats)
    for _ in range(q):
        l, r = MI1()
        # print(S[l:r+1])
        print(ats[r] - ats[l])


if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

def solve():
    n, k = MI()
    H = LI()

    dp = [INF] * n
    dp[0] = 0
    def f(a, b):
        return abs(a - b)
    for i in range(n):
        for j in range(1, k+1):
            if i + j < n:
                dp[i+j] = min(dp[i+j], dp[i] + f(H[i], H[i+j]))
    print(dp[i])


if __name__ == '__main__':
    solve()


Fixed submission:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

def solve():
    n, k = MI()
    H = LI()

    dp = [INF] * n
    dp[0] = 0
    def f(a, b):
        return abs(a - b)
    for i in range(n):
        for j in range(1, k+1):
            if i + j < n:
                dp[i+j] = min(dp[i+j], dp[i] + f(H[i], H[i+j]))
    print(dp[i])


if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')

def solve():
    S = list(input())
    T = list(input())

    ds = {}
    dt = {}
    ids = ''
    idt = ''
    cids = 0
    cidt = 0
    for i in range(len(S)):
        # S
        s = S[i]
        if s in ds:     # 出現済みの文字なら、その文字のIDを追加する
            idss = ds[s]
            ids = ids + str(idss)
        else:           # 新たに出現した文字なら、新しいIDを追加し、メモしておく
            cids += 1
            ds[s] = cids
            ids = ids + str(cids)

        # T
        t = T[i]
        if t in dt:
            idst = dt[t]
            idt = idt + str(idst)
        else:
            cidt += 1
            dt[t] = cidt
            idt = idt + str(cidt)

        if ids != idt:
            print('No')
            return

    print('Yes')



if __name__ == '__main__':
    solve()


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

L = sorted(L)[::-1]

s = '{}{}+{}'.format(L[0], L[1], L[2])
print(eval(s))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right
def comb(n, r):
    # if n - r < 0: return 0
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def solve():
    N = II()
    A = LI()
    A = sorted(A)[::-1]

    a = A[0]
    cal = 0
    B = 0
    for i, b in enumerate(A[1:]):
        c = comb(a, b)
        if cal < c:
            B = b
            cal = c
    print(a, B)



if __name__ == '__main__':
    solve()


Fixed submission:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
from bisect import bisect_left, bisect_right

def solve():
    N = II()
    A = LI()
    A = sorted(A)

    a = A[-1]
    mid = a / 2
    diff = INF
    b = -1
    for j in A[:-1]:
        d = abs(j - mid)
        if d < diff:
            b = j
            diff = d
    print(a, b)



if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Runtime Error):
# import sys
# sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

import fractions as math

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

def solve():
    n = II()
    T = [II() for _ in range(n)]

    t1 = T[0]
    for t2 in T[1:]:
        l = lcm(t1, t2)
        t1 = l
    print(l)


if __name__ == '__main__':
    solve()


Fixed submission:
# import sys
# sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

import fractions as math

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

def solve():
    n = II()
    T = [II() for _ in range(n)]

    t1 = T[0]
    l = t1
    for t2 in T[1:]:
        l = lcm(t1, t2)
        t1 = l
    print(l)


if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Runtime Error):
# import sys
# sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

import math

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

def solve():
    n = II()
    T = [II() for _ in range(n)]

    t1 = T[0]
    for t2 in T[1:]:
        l = lcm(t1, t2)
        t1 = l
    print(l)


if __name__ == '__main__':
    solve()


Fixed submission:
# import sys
# sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

import fractions as math

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

def solve():
    n = II()
    T = [II() for _ in range(n)]

    t1 = T[0]
    l = t1
    for t2 in T[1:]:
        l = lcm(t1, t2)
        t1 = l
    print(l)


if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Time Limit Exceeded):
#editorial
n,k=map(int,input().split())
*lr,=[tuple(map(int, input().split())) for _ in range(k)]
res =[0]*(2*n+3)
##############
diff=[0]*(2*n+3)
######
#res[0]=1

diff[0]=1
diff[1]=-1
mod=998244353

for i in range(n+1):
    res[i]=res[i-1]+diff[i]
    for li,ri in lr:
        diff[i+li]+=res[i]
        diff[i+ri+1]-=res[i]
    #print(res[:n+1])
    #print((diff[:n+1]))
print(res[n-1]%mod)
#print(res[:n+1])
#print((diff[:n+1]))
    

Fixed submission:
#editorial
n,k=map(int,input().split())
*lr,=[tuple(map(int, input().split())) for _ in range(k)]
res =[0]*(2*n+3)
##############
diff=[0]*(2*n+3)
######
#res[0]=1

diff[0]=1
diff[1]=-1
mod=998244353

for i in range(n+1):
    res[i]=res[i-1]+diff[i]
    res[i]%=mod
    diff[i]%=mod
    for li,ri in lr:
        diff[i+li]+=res[i]
        diff[i+ri+1]-=res[i]
    #print(res[:n+1])
    #print((diff[:n+1]))
print(res[n-1]%mod)
#print(res[:n+1])
#print((diff[:n+1]))
Buggy python submission (verdict: Runtime Error):
#周期m以下

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

used = [0]*(m+1)
used_list=[]
pre=x

flag0=False
s=-1;t=-1
for i in range(m+1):
    if pre==0:
        flag0=True
        break
    now=(pre*pre)%m
    if used[pre]:
        s=used[pre]
        break
    used[pre]=i
    used_list.append(pre)
    pre=now
    
l=len(used_list[s:])
ans=sum(used_list[:s])+sum(used_list[s:])*((n-s)//l)+sum(used_list[s:s+(n-s)%l])
if not flag0:
    print(ans)
else:
    print(sum(used_list))

Fixed submission:
#周期m以下

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

used = [0]*(m+1)
used_list=[]
pre=x

flag0=False
s=-1;t=-1
for i in range(m+1):
    if pre==0:
        flag0=True
        break
    now=(pre*pre)%m
    if used[pre]:
        s=used[pre]
        break
    used[pre]=i
    used_list.append(pre)
    pre=now
    
l=len(used_list[s:])
try:
    ans=sum(used_list[:s])+sum(used_list[s:])*((n-s)//l)+sum(used_list[s:s+(n-s)%l])
    if not flag0:
        print(ans)
    else:
        print(sum(used_list))
except:
    print(sum(used_list))