Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import heapq

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

heapq.heapify(a) # in-place

for _ in range(m):
    temp = []
    b, c = map(int, input().split())
    for i in range(b):
        temp.append(heapq.heappop(a))
        if c > temp[-1]:
            temp[-1] = c
        else:
            break
    for j in temp:
        heapq.heappush(a, j)

print(sum(a))

### FIXED CODE ###

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

bc = []

for _ in range(m):
    b, c = map(int, input().split())
    bc.append((b, c))

bc = sorted(bc, key=lambda x: x[1], reverse=True)

cnt = 0

for b, c in bc:
    cnt += b
    a += [c] * b
    if cnt >= n:
        break

print(sum(sorted(a,reverse=True)[:n]))
### BUGGY CODE ###

import sys
from math import factorial

input = sys.stdin.readline
n,k = map(int,input().split())
a = list(map(int,input().split()))

mod = 10**9 + 7

a.sort()

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

ans = 0

dp = [1]
for i in range(1,n+1):
    dp.append(dp[-1]*i%mod)

def comb(n,k):
    return factorial(n) // factorial(k) // factorial(n-k) % mod
    #return dp[n] // dp[k] // dp[n-k]

comb1 = comb(n,k)

for i in range(n-1):
    if i+1 < k and n-i-1 < k:
        ans += li[i] * comb1
    elif i+1 < k:
        ans += li[i] * (comb1 - comb(n-i-1,k))
    elif n-i-1 < k:
        ans += li[i] * (comb1 - comb(i+1,k))
    else:
        ans += li[i] * (comb1 - comb(n-i-1,k) - comb(i+1,k))

print(ans%mod)


### FIXED CODE ###

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

mod = 10**9 + 7

a.sort(reverse = True)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """

    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

comb = Combination(100010)
ans = 0

for i in range(n-k+1):
    ans += a[i] * comb(n-i-1, k-1)
    ans %= mod

a = a[::-1]

for i in range(n-k+1):
    ans -= a[i] * comb(n-i-1, k-1)
    ans %= mod

print(ans)
### BUGGY CODE ###

from heapq import heapify, heappop, heappush
import sys
sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, D, A = inpl()
XH = [inpl() for _ in range(N)]
XH.sort()
MONSTER = 1
END = 2
q = [ (XH[i][0], MONSTER, XH[i][1]) for i in range(N)]
heapify(q)
ans = 0
d = 0
while q:
    x, s, h = heappop(q)
    if s == MONSTER:
        h -= d
        if h <= 0:
            continue
        else:
            k = (h-1)//A + 1
            ans += k
            heappush(q, (x+2*D,END,k*A))
            d += k*A
    else: # END
        d -= h
print(ans)

### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
Xmax = 10**10
N, D, A = inpl()
XH = [inpl() for _ in range(N)]
XH.sort()
XH.append([Xmax,0])
ans = 0
d = 0
i = j = 0
R = []
while True:
    if j >= len(R) or XH[i][0] <= R[j][0]:
        x, h = XH[i]
        i += 1
        if x >= Xmax:
            break
        h -= d
        if h <= 0:
            continue
        else:
            k = (h-1)//A + 1
            R.append((x+2*D, k*A))
            d += k*A
            ans += k
    else:
        x, h = R[j]
        j += 1
        d -= h
print(ans)
### BUGGY CODE ###

H, W, M = map(int, input().split())
row=[0]*H
col=[0]*W

mat=[[0 for i in range(W)] for j in range(H)]

for i in range(M):
  h, w = map(int, input().split())
  h-=1
  w-=1
  row[h]+=1
  col[w]+=1
  mat[h][w]+=1

r=max(row)
c=max(col)

rr=[i for i in range(H) if row[i]==r]
cc=[i for i in range(W) if col[i]==c]

x=sum([sum([mat[i][j] for j in cc]) for i in rr])

if x==len(rr)*len(cc):
  print(r+c-1)
else:
  print(r+c)

### FIXED CODE ###

H, W, M = map(int, input().split())
row=[0]*H
col=[0]*W

mat=[]

for i in range(M):
  h, w = map(int, input().split())
  row[h-1]+=1
  col[w-1]+=1
  mat.append((h-1,w-1))
  
r=max(row)
c=max(col)

rr=[1 if row[i]==r else 0 for i in range(H)]
cc=[1 if col[i]==c else 0 for i in range(W)]

x=0
for k in mat:
  if rr[k[0]]==1 and cc[k[1]]==1:
    x+=1

if sum(rr)*sum(cc)==x:
  print(r+c-1)
else:
  print(r+c)
### BUGGY CODE ###

N, S = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353

def main():
  dp = [0]*(S+1)
  dp[0] = 1
  for i in range(1, N+1):
    p = [0]*(S+1)
    dp, p = p, dp
    for j in range(0, S+1):
      dp[j] += 2*p[j]
      dp[j] %= MOD
      if j-A[i-1] >= 0:
        dp[j] += p[j-A[i-1]]
        dp[j] %= MOD
  print(dp[S])

if __name__ == "__main__":
  main()

### FIXED CODE ###

N, S = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353

def main():
  dp = [0]*(S+1)
  dp[0] = 1
  for i in range(1, N+1):
    p = [0]*(S+1)
    dp, p = p, dp
    for j in range(0, S+1):
      dp[j] += 2*p[j]
      dp[j] %= MOD
      if j-A[i-1] >= 0:
        dp[j] += p[j-A[i-1]]
        dp[j] %= MOD
  print(dp[S])

if __name__ == "__main__":
  main()
### BUGGY CODE ###

N = int(input())
S = list(input())
black = 0
white = 0
black2 = 0
white2 = 0
k = 0
ans = 0
for i in range(N - 1):
    if S[i] == "#" and S[i + 1] == ".":
        if k == 0:
            black = S[:i + 1].count("#")
            white = S[i + 1:].count(".")
            ans += min(black, white)
            k = 1
        elif k == 1:
            black2 = S[:i + 1].count("#")
            white2 = S[i + 1:].count(".")
            ans += min(black2 - black, white - white2)
            black = black2
            white = white2
print(ans)

### FIXED CODE ###

N = int(input())
S = list(input())
S.insert(0,0)
# b = S.count("#")
w = S.count(".")
black = 0
white = w
ans = 2e5
for i in range(N+1):
    if S[i] == "#":
        black += 1
    elif S[i] == ".":
        white -= 1
    # print(black,white)
    ans = min(black + white, ans)
print(ans)
### BUGGY CODE ###

r1, c1, r2, c2 = map(int, input().split())

# Combination calculation
p = 10 ** 9 + 7
N = r2 + c2 + 2
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

def comb(n, r):
    return fact[n] * factinv[r] * factinv[n - r] % p

def f(i, j):
    return comb(i + j, i)

def g(i, j):
    return f(i + 1, j + 1) - 1

ans = g(r2, c2) - g(r2, c1 - 1) - g(r1 - 1, c2) + g(r1 - 1, c1 - 1)

print(ans)

### FIXED CODE ###

def solve():
    r1, c1, r2, c2 = map(int, input().split())
    
    p = 10 ** 9 + 7
    N = r2 + c2 + 2
    fact = [1, 1]
    for i in range(2, N + 1):
        fact.append((fact[-1] * i) % p)
    
    def comb(n, r):
        a = fact[n]
        b = pow(fact[r], p - 2, p)
        c = pow(fact[n-r], p - 2, p)
        return a * b * c % p
    
    def f(i, j):
        return comb(i + j, i)
    
    def g(i, j):
        return f(i + 1, j + 1) - 1
    
    ans = g(r2, c2) - g(r2, c1 - 1) - g(r1 - 1, c2) + g(r1 - 1, c1 - 1)
    
    print(ans % p)

solve()
### BUGGY CODE ###

N,A,B=map(int,input().split())
n=0
while True:
    N-=A
    if N<=0:
        print(n+(A+N))
        break
    n+=A
    N-=B
    if N<=0:
        print(n)
        break

### FIXED CODE ###

N,A,B=map(int,input().split())
n=0
x=N//(A+B)
y=N%(A+B)-A
if y>0:
    print((x+1)*A)
else:
    print((x+1)*A+y)
### BUGGY CODE ###

number = int(input())
lower = list(map(int, input().split()))

time = 0
max = 0

def down(i):
    global max
    global time

    if max > (number-i+1):
        return

    for j in range(i, number-1):
        if lower[j] >= lower[j+1]:
            time += 1
        else:
            return


for i in range(len(lower)):
    down(i)
    if max < time:
        max = time
    time = 0

print(max)


### FIXED CODE ###

number = int(input())
lower = list(map(int, input().split()))

time = 0
max = 0

def down(i):
    global time
    for j in range(i, number-1):
        if lower[j] >= lower[j+1]:
            time += 1
        else:
            return j+1

    return 0

now = 0
for i in range(len(lower)):

    if now > i:
        continue

    if max > (number-i+1):
        break

    now = down(i)

    if max < time:
        max = time
    time = 0



print(max)
### BUGGY CODE ###

import numpy as np

n, m = [int(i) for i in input().split()]

connected_1 = []
connected_n = []
for i in range(m):
    a, b = [int(i) for i in input().split()]
    
    if a == 1:
        connected_1.append(b)
        
    if b == n:
        connected_n.append(a)

        
for i in range(len(connected_1)):
    if connected_1[i] in connected_n:
        print("POSSIBLE")
        break
    if i == len(connected_1)-1:
        print("IMPOSSIBLE")
    

### FIXED CODE ###

import numpy as np

n, m = [int(i) for i in input().split()]

connected_1 = {}

for i in range(m):
    a, b = [int(i) for i in input().split()]
    
    if a == 1:
        if connected_1.get(b) is None:
            connected_1[b] = 1
        elif connected_1[b] ==1:
            print("POSSIBLE")
            break
        
        
    if b == n:
        if connected_1.get(a) is None:
            connected_1[a] = 1
        elif connected_1[a] ==1:
            print("POSSIBLE")
            break
        
       
        
    if i==m-1:
        print("IMPOSSIBLE")
### BUGGY CODE ###

import numpy as np
import copy

N, W= map(int, raw_input().split())
dp = np.zeros(W+1)

for i in range(N):
   w, v = map(int, raw_input().split())
   dp_temp = copy.deepcopy(dp)
   for j in range(W+1):
      dp_pre = dp[j]
      if j-w > -1:
         dp_update = dp[j-w] + v
      else:
         dp_update = 0
      dp_temp[j] = max(dp_pre, dp_update)

   dp = dp_temp

print int(dp[-1])

### FIXED CODE ###

def main():

    N, W = map(int, raw_input().split())
    dp = [0]*(W+1)
 
    for i in xrange(N):
        w, v = map(int, raw_input().split())
        for j in xrange(W, w-1, -1):
            x = dp[j-w] + v
            if x > dp[j]:
                dp[j] = x
 
    print dp[-1]

main()
### BUGGY CODE ###

N,W = map(int, input().split())

INF = 10**10
vsum = 1000*N
dp = [INF for i in range(vsum+1)]
dp[0] = 0


for _ in range(N):
    w,v = map(int,input().split())
    dp1 = [d for d in dp]
    for i,d in enumerate(dp):
        if d == INF:
            continue
        else:
            if i + v <= vsum:
                dp[i+v] = min(dp1[i+v], dp1[i]+w)
    
ans = 0
for i,d in enumerate(dp):
    if d <= W:
        ans = i

print(ans)

### FIXED CODE ###

import numpy as np
N,W = map(int, input().split())
INF =  10**10
V_max = 100001
N_max = 101
# dp = np.ones((N_max,V_max), dtype=np.int64)*INF
dp = np.ones(V_max,dtype=np.int64)*INF
dp[0] = 0
for i in range(N):
    a = np.ones(V_max)*INF
    w,v = map(int,input().split())
    # np.minimum(dp[i][:-v]+w,dp[i][v:],out=dp[i+1][v:])
    np.minimum(dp[:-v]+w,dp[v:],out=dp[v:])
ans = 0
for i,d in enumerate(dp):
    if d<=W:
        ans = i
print(ans)
### BUGGY CODE ###

from itertools import combinations
from fractions import gcd

ans=0
aaa=0

a,b=map(int,input().split())
c=gcd(a,b)
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)

    # divisors.sort()
    return divisors
s=make_divisors(c)
#print(s)
for i in s:
    aaa=0
    if i%2==0:
        aaa=1
    if i>=3 and i%2==1:
        for j in range(2,i):
            #print(i,j)
            if i%j==0:
                aaa=1
                break
            else:
                aab=0
    if aaa==0:
        ans+=1
if c%2==0:
	ans+=1
print(ans)
 


### FIXED CODE ###

from itertools import combinations
from fractions import gcd

#coding:utf8
import random

def is_prime3(q,k=50):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True
ans=0

a,b=map(int,input().split())
c=gcd(a,b)
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)

    # divisors.sort()
    return divisors
s=make_divisors(c)
for i in s:
    ans=ans+is_prime3(i)
print(ans+1)
### BUGGY CODE ###

def exp_val(n):
    return (n+1)/2

def dice_in_line():
    K,N=map(int,input().split())
    p_n=list(map(int,input().split()))
    exp=[]
    for i in p_n:
        exp.append(exp_val(int(i)))
    exp_sum=[]
    for i in range(K-N+1):
        exp_sum.append(sum(exp[i:i+N]))
    print(max(exp_sum))

dice_in_line()

### FIXED CODE ###

def dice_in_line():
    N,K=map(int,input().split())
    p_n=list(map(int,input().split()))
    max=x=sum(p_n[:K])
    for i in range(N-K):
        x+=(p_n[K+i]-p_n[i])
        if max<x:
            max=x
    print((max+K)/2)

dice_in_line()
### BUGGY CODE ###

N, M= map(int, input().split())
A = list(map(int,input().split()))
for m in range(M):
    A.sort()
    A[-1]=A[-1]//2
print(sum(A))

### FIXED CODE ###

N, M= map(int, input().split())
A = list(map(int,input().split()))
A=[-1*a for a in A]
import heapq
import math
hq=heapq.heapify(A)
for m in range(M):
    X=heapq.heappop(A)
    heapq.heappush(A,math.ceil(X/2))
print(sum(A)*-1)
### BUGGY CODE ###

s = list(map(int,input().split()))
n=s[0]
s = list(map(int, input().split()))
ans=1
if 0 in s:
    print(0)
else:
    for i in s:
        ans*=i
    if ans>10**18:
        print(-1)
    else:
        print(ans)

### FIXED CODE ###

s = list(map(int, input().split()))
s = list(map(int, input().split()))
ans = 1
if 0 in s:
    print(0)
else:
    for i in s:
        ans *= i
        if ans > 10**18:
            break
    if ans > 10**18:
        print(-1)
    else:
        print(ans)
### BUGGY CODE ###

def lcs(X, Y):
    m, n = len(X), len(Y)
    memo = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                memo[i][j] = memo[i - 1][j - 1] + 1
            else:
                memo[i][j] = max(memo[i][j - 1], memo[i - 1][j])
    return memo[m][n]

n = int(input())
for _ in range(n):
    X, Y = input(), input()
    print(lcs(X, Y))

### FIXED CODE ###

def lcs(X, Y):
    costs = [0]
    for c in Y:
        for i in range(len(costs) - 1, -1, -1):
            tmp = X.find(c, costs[i])
            if tmp + 1:
                if i + 1 < len(costs):
                    costs[i + 1] = min(costs[i + 1], tmp + 1)
                else:
                    costs.append(tmp + 1)
    return len(costs) - 1

n = int(input())
for _ in range(n):
    X, Y = (input() for _ in range(2))
    print(lcs(X, Y))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc077/tasks/arc084_a

"""
import sys
from sys import stdin
from bisect import bisect_left, bisect_right
input = stdin.readline


def main(args):
    N = int(input())
    A = [int(x) for x in input().split()]
    B = [int(x) for x in input().split()]
    C = [int(x) for x in input().split()]

    A.sort()
    B.sort()
    C.sort()

    lut = {}
    for b in B:
        j = bisect_right(C, b)
        lut[b] = j


    ans = 0

    for a in A:
        i = bisect_right(B, a)
        if i == N:
            continue
        for b in B[i:]:
            # j = bisect_right(C, b)
            j = lut[b]
            if j == N:
                continue
            ans += (N-j)

    print(ans)



if __name__ == '__main__':
    main(sys.argv[1:])
    


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc077/tasks/arc084_a

"""
import sys
from sys import stdin
from bisect import bisect_left, bisect_right
input = stdin.readline


def main(args):
    N = int(input())
    A = [int(x) for x in input().split()]
    B = [int(x) for x in input().split()]
    C = [int(x) for x in input().split()]
    A.sort()
    B.sort()
    C.sort()

    lut_A = {}
    lut_C = {}
    for b in B:
        i = bisect_left(A, b)
        lut_A[b] = i
        j = bisect_right(C, b)
        lut_C[b] = N - j


    ans = 0
    for b in B:
        i = lut_A[b]
        j = lut_C[b]
        ans += i * j

    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])
### BUGGY CODE ###

N, K = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a)

if N == 1:
	if a[0] >= K:
		print(0)
	else:
		print(1)

else:
	def check(i):
		if a[i] >= K:
			return True
		if i == 0:
			b = a[1:]
		elif i == N - 1:
			b = a[:N - 1]
		else:
			b = a[:i] + a[i+1:]
		#print(b)
		#ok = False
		dp = [[False] * K for _ in range(N - 1)]
		if b[0] < K:
			dp[0][b[0]] = True
		if K - a[i] <= b[0] < K:
			return True
		for j in range(1, N - 1):
			for k in range(1, K):
				#if b[j] == K:
				#	return True
				#elif dp[j - 1][k] == True:
				if dp[j - 1][k] == True:
					dp[j][k] = True
				elif k > b[j]:
					if dp[j - 1][k - b[j]] == True:
						dp[j][k] = True

				if dp[j][k] == True and K - a[i] <= k < K:
					return True

		return False


	def bi_search(lower, upper):
		#print(lower, upper)
		mid = (lower + upper) // 2
		#print(mid)
		if mid == 0 and check(mid) == True:
			return 0
		elif mid == N - 2 and check(mid + 1) == False:
			return N
		elif check(mid) == False and check(mid + 1) == True:
			#print("hoge")
			return mid + 1
		elif check(mid) == True:
			return bi_search(lower, mid)
		else:
			return bi_search(mid + 1, upper)


	print(bi_search(0, N - 1))


### FIXED CODE ###

import sys

n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
#print(a)
fr = 0
ba = n+1

def check(mi):
    x = a[mi-1]
    if x >= k:
        return True
    #print(mi)
    dp = [False] * (k+1)
    dp[0] = True
    for i in range(n):
        if i == mi-1:
            continue
        y = a[i]
        for j in range(k, -1, -1):
            if j >= y:
                dp[j] = dp[j] | dp[j-y]

    if sum(dp[k-x:k]):
        return True
    else:
        return False

if check(1):
    print(0)
    sys.exit()

if not check(n):
    print(n)
    sys.exit()

while ba-fr > 1:
    mi = (ba+fr+1) // 2
    if check(mi):
        ba = mi
    else:
        fr = mi

print(fr)
### BUGGY CODE ###

import sys
import math
from collections import deque
import copy

H, W = map(int, input().split())
maps2 = deque([deque(["#" for _ in range(W + 2)])])
MAX = 0

for _ in range(H):
    temp = deque(input())
    temp.appendleft("#")
    temp.append("#")
    maps2.append(temp)
maps2.append(deque(["#" for _ in range(W + 2)]))

for i in range(1, H + 1):
    for l in range(1, W + 1):
        maps = copy.deepcopy(maps2)
        if maps2[i][l] != "#":
            pos = [[i, l, 0]]
            while len(pos) > 0:

                y, x, depth = pos.pop(0)
                if depth > MAX:
                    MAX = depth
                maps[y][x] = "$"

                if maps[y + 1][x] == ".":
                    pos.append([y + 1, x, depth + 1])
                if maps[y][x + 1] == ".":
                    pos.append([y, x + 1, depth + 1])
                if maps[y - 1][x] == ".":
                    pos.append([y - 1, x, depth + 1])
                if maps[y][x - 1] == ".":
                    pos.append([y, x - 1, depth + 1])
print(MAX)


### FIXED CODE ###

import sys
import math
from collections import deque
import copy

H, W = map(int, input().split())
maps2 = deque([deque(["#" for _ in range(W + 2)])])
MAX = 0

for _ in range(H):
    temp = deque(input())
    temp.appendleft("#")
    temp.append("#")
    maps2.append(temp)
maps2.append(deque(["#" for _ in range(W + 2)]))

for i in range(1, H + 1):
    for l in range(1, W + 1):
        if maps2[i][l] != "#":
            maps = copy.deepcopy(maps2)
            pos = [[i, l, 0]]
            maps[i][l] = "a"
            while len(pos) > 0:

                y, x, depth = pos.pop(0)
                if depth > MAX:
                    MAX = depth

                if maps[y + 1][x] == ".":
                    pos.append([y + 1, x, depth + 1])
                    maps[y + 1][x] = "a"
                if maps[y][x + 1] == ".":
                    pos.append([y, x + 1, depth + 1])
                    maps[y][x + 1] = "a"
                if maps[y - 1][x] == ".":
                    pos.append([y - 1, x, depth + 1])
                    maps[y - 1][x] = "a"
                if maps[y][x - 1] == ".":
                    pos.append([y, x - 1, depth + 1])
                    maps[y][x - 1] = "a"
print(MAX)
### BUGGY CODE ###

""" E
    https://atcoder.jp/contests/abc173/tasks/abc173_e
"""
import sys
import math
from functools import reduce

def readString():
    return sys.stdin.readline()

def readInteger():
    return int(readString())

def readStringSet(n):
    return sys.stdin.readline().split(" ")[:n]

def readIntegerSet(n):
    return list(map(int, readStringSet(n)))

def readIntegerMatrix(n, m):
    return reduce(lambda acc, _: acc + [readIntegerSet(m)], range(0, n), [])

def main(N, X, M):
    A = X
    l = [A]
    i = -1
    for _ in range(1, N):
        A = (A * A) % M
        try:
            i = l.index(A)
            break
        except ValueError:
            l.append(A)

    if i == -1:
        return sum(l)
    else:
        s1 = sum(l[:i])
        len_repeat = len(l) - i
        s2 = sum(l[i:])

        return s1 + int((N-i)/len_repeat) * s2 + sum(l[i:(N-i)%len_repeat+i])

if __name__ == "__main__":
    _N, _X, _M = readIntegerSet(3)

    print(main(_N, _X, _M))

### FIXED CODE ###

""" E
    https://atcoder.jp/contests/abc173/tasks/abc173_e
"""
import sys
import math
from functools import reduce

def readString():
    return sys.stdin.readline()

def readInteger():
    return int(readString())

def readStringSet(n):
    return sys.stdin.readline().split(" ")[:n]

def readIntegerSet(n):
    return list(map(int, readStringSet(n)))

def readIntegerMatrix(n, m):
    return reduce(lambda acc, _: acc + [readIntegerSet(m)], range(0, n), [])

def main(N, X, M):
    A = X
    m = {A: A}
    i = -1
    for j in range(1, M):
        A = (A * A) % M if M > 0 else 0
        if A in m:
            i = list(m.keys()).index(A)
            break
        else:
            m[A] = A

    if i == -1:
        return sum(m.values())
    else:
        l = list(m.values())
        s1 = sum(l[:i])
        len_repeat = len(l) - i
        s2 = sum(l[i:])

        return s1 + int((N-i)/len_repeat) * s2 + sum(l[i:(N-i)%len_repeat+i])

if __name__ == "__main__":
    _N, _X, _M = readIntegerSet(3)

    print(main(_N, _X, _M))