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

n = int(input())

ans = set()


for i in range(n):
    ans = ans ^ {input()}

print(len(ans))


### FIXED CODE ###

n = int(input())

ans = [input() for i in range(n)]

ans.sort()

s = sorted(set(ans))
t = 0
cnt = 0

result = 0
for i in range(n):
    temp = s[t]
    if ans[i] == temp:
        cnt += 1
    else:
        if cnt % 2 == 1:
            result += 1
        cnt = 1
        t += 1
else:
    if cnt % 2 == 1:
        result += 1
        
    
    

print(result)
### BUGGY CODE ###

#%%
n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [10**9] * (n+1)
dp[0] = 0
dp[1] = 0
for i in range(2, n+1):
    for j in range(1, k+1):
        if i-j-1>=0: 
            dp[i] = min(dp[i], dp[i-j] + abs(h[i-1] - h[i-j-1]))
        else:
            pass
print(dp[-1])

### FIXED CODE ###

#%%
n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [10**9] * (n+1)
dp[0] = 0
dp[1] = 0
for i in range(2, n+1):
    for j in range(1, k+1):
        if i-j-1>=0: 
            dp[i] = min(dp[i], dp[i-j] + abs(h[i-1] - h[i-j-1]))
        else:
            pass
print(dp[-1])
### BUGGY CODE ###

n, m = map(int, input().split())
A = sorted(map(int, input().split()))
for _ in range(m):
    A[-1]=A[-1]//2
    A.sort()

print(sum(A))


### FIXED CODE ###

import heapq
n, m = map(int, input().split())
A = sorted(map(lambda x: -int(x), input().split()))
for _ in range(m):
    a = heapq.heappop(A)
    a = -(-a//2)
    heapq.heappush(A, a)

print(-sum(A))
### BUGGY CODE ###

import numpy as np

N, M, Q = map(int, input().split())
result = np.zeros((N,N), dtype=int)

for m in range(M):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    result[:l+1, r:] += 1    

for _ in range(Q):
    p, q = map(int, input().split())
    
    print(result[p-1][q-1])

### FIXED CODE ###

import sys
import itertools
input = sys.stdin.readline
sys.setrecursionlimit(100000)


def read_values():
    return map(int, input().split())


def read_index():
    return map(lambda x: x - 1, map(int, input().split()))


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


def functional(N, mod):
    F = [1] * (N + 1)
    for i in range(N):
        F[i + 1] = (i + 1) * F[i] % mod
    return F


def main():
    N, M, Q = read_values()
    S = [[0 for _ in range(N + 1)] for __ in range(N + 1)]
    
    for _ in range(M):
        l, r = read_values()
        S[l][r] += 1

    for l in range(N):
        for r in range(N):
            S[l + 1][r + 1] += S[l + 1][r] + S[l][r + 1] - S[l][r] 

    res = [0] * Q
    for i in range(Q):
        p, q = read_values()
        res[i] = str(S[q][q] - S[p - 1][q] - S[q][p - 1] + S[p - 1][p - 1])
    print("\n".join(res))


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

import sys
import numpy as np

read = lambda : sys.stdin.readline().rstrip('\n')
tint = lambda x: [int(x) for x in x.split()]
ttuple = lambda x: tuple(int(x) for x in x.split())

def main():
    n, k = tint(read())
    stones = ttuple(read())
    inf = 10**9
    dp = np.array([inf]*n)
    dp[0] = 0
    for i in range(n):
        for t in range(1, k+1):
            step = i+t
            if step < n:
                dp[step] = min(dp[step], dp[i]+abs(stones[i]-stones[step]))
    print(dp[-1])


if __name__ == '__main__':    
    main()


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    h = tuple(map(int, input().split()))
    INF = 10 ** 9
    dp = [INF] * n
    dp[0] = 0
    for i in range(n):
        for j in range(1, k + 1):
            i_j = i + j
            if i_j < n:
                x = dp[i] + abs(h[i] - h[i_j])
                if dp[i_j] > x:
                    dp[i_j] = x
    print(dp[-1])


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

# -*- coding: utf-8 -*-
from sys import exit
n, y  = map(int, input().split())
for i in range(n+1):
    for j in range(n+1-i):
        for k in range(n+1-j):
            if 10000*i+5000*j+1000*k == y and i+j+k == n:
                print(i, j, k)
                exit()
print(-1, -1, -1)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from sys import exit
n, y  = map(int, input().split())
for i in range(n+1):
    for j in range(n+1-i):
        if 10000*i+5000*j+1000*(n-i-j) == y:
            print(i, j, n-i-j)
            exit()
print(-1, -1, -1)
### BUGGY CODE ###

N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())), reverse=True)

ans = 0
for b in B:
    a_num = 0
    c_num = 0
    for a in A:
        if a < b:
            a_num += 1
        else:
            break
    for c in C:
        if b < c:
            c_num += 1
        else:
            break
    ans += a_num * c_num

print(ans)


### FIXED CODE ###

import bisect

N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

ans = 0
for b in B:
    a_num = bisect.bisect_left(A, b)
    c_num = N - bisect.bisect_right(C, b)
    ans += a_num * c_num

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

def f(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


B=[0]*(10**6+10)
n=int(input())
A=list(map(int,input().split()))
for i in range(n):
  if A[i]==1:
    continue
  D=f(A[i])
  for j in range(len(D)):
    B[D[j][0]]+=1
f=0
for i in range(10**6+5):
  if B[i]>1:
    f=1
if f==0:
  print("pairwise coprime")
  exit()
for i in range(10**6+5):
  if B[i]>=n:
    f=0
if f==1:
  print("setwise coprime")
else:
  print("not coprime")

### FIXED CODE ###

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

P=primes(10**6)

def f(n):
    arr = []
    temp = n
    j=0
    while P[j]**2<=temp:
        i=P[j]
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
        j=j+1

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


B=[0]*(10**6+10)
n=int(input())
A=list(map(int,input().split()))
for i in range(n):
  if A[i]==1:
    continue
  D=f(A[i])
  for j in range(len(D)):
    B[D[j][0]]+=1
f=0
for i in range(10**6+5):
  if B[i]>1:
    f=1
if f==0:
  print("pairwise coprime")
  exit()
for i in range(10**6+5):
  if B[i]>=n:
    f=0
if f==1:
  print("setwise coprime")
else:
  print("not coprime")
### BUGGY CODE ###

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

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

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

        if x == y:
            return

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

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

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

import sys
input = sys.stdin.readline
n,m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(m)]
uf = UnionFind(n)
for i in range(m):
    uf.union(a[i][0]-1,a[i][1]-1)
x = list(uf.all_group_members().values())
#print(x)
ans = 0
for i in range(len(x)):
    ans = max(ans,len(x[i]))
print(ans)


### FIXED CODE ###

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

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

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

        if x == y:
            return

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

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

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


n,m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(m)]
uf = UnionFind(n)
for i in range(m):
    uf.union(a[i][0]-1,a[i][1]-1)
ans = 0
x = uf.parents
for i in range(n):
    if x[i]<0:
        #print(i)
        ans = max(ans,uf.size(i))
print(ans)
### BUGGY CODE ###

import itertools
n = int(input())
l = list(map(int,input().split()))
ans = 0
for i in itertools.combinations(l,3):
  if i[0]<i[1]+i[2] and i[1]<i[2]+i[0] and i[2]<i[0]+i[1]:
    ans+=1
print(ans)

### FIXED CODE ###

import bisect
n = int(input())
l = list(map(int,input().split()))
l.sort()
ans = 0
for b in range(n):
  for a in range(b):
    ans += bisect.bisect_left(l,l[a]+l[b])-(b+1)
print(ans)
### BUGGY CODE ###

n = int(input())
s = [0] * n
for i in range(n):
    s[i] = input()

li = []
ans = []
for i in range(n):
    if s[i] in ans:
        li[ans.index(s[i])][1] += 1
    else:
        li.append([s[i], 1])
        ans.append(s[i])
            
                
li.sort(key = lambda x: x[0])
li.sort(key = lambda x: x[1] , reverse = True)

a = li[0][1]
for i in range(len(li)):
    if a == li[i][1]:
        print(li[i][0])
    else:
        break

### FIXED CODE ###

n = int(input())
s = [input() for i in range(n)]

dic = {}
for i in range(n):
    if s[i] in dic:
        dic[s[i]] += 1
    else:
        dic[s[i]] = 1

max_dic = max(dic.values())
ans = [i for i, j in dic.items() if j == max_dic]
ans.sort()

for i in range(len(ans)):
    print(ans[i])
### BUGGY CODE ###

from collections import deque
H,W,K= map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
sx-=1;sy-=1;gx-=1;gy-=1 #0index
Pond = []
for i in range(H):
  temp = str(input())
  temp = list(temp)
  Pond.append(temp)
#print(Pond)
INF = float("inf")
reach = [[INF for _ in range(W)] for _ in range(H)]
reach[sx][sy] = 0
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
Q = deque([(sx,sy)])
while Q:
  x,y = Q.popleft()
  #print(x,y)
  #step = reach[x][y]
  for j in range(4):
    for i in range(1,K+1):
      fac = i
      nx = x+fac*dxdy[j][0]
      ny = y+fac*dxdy[j][1]
      #print(nx,ny)
      if 0<=nx<H and 0<=ny<W:
        if Pond[nx][ny] == "@": #一回蓮があったらその向きはもう無理
          break
        if reach[x][y]+1 < reach[nx][ny]:
          reach[nx][ny] = min(reach[x][y]+1,reach[nx][ny])
          Q.append((nx,ny))
        if nx == gx and ny == gy:
          #print(reach)
          print(reach[nx][ny])
          exit()
print(-1)
                 
  
  

### FIXED CODE ###

from collections import deque
H,W,K= map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
sx-=1;sy-=1;gx-=1;gy-=1 #0index
Pond = []
for i in range(H):
  temp = str(input())
  temp = list(temp)
  Pond.append(temp)
#print(Pond)
INF = float("inf")
reach = [[INF for _ in range(W)] for _ in range(H)]
reach[sx][sy] = 0
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
Q = deque([(sx,sy)])
while Q:
  x,y = Q.popleft()
  #print(x,y)
  #step = reach[x][y]
  for j in range(4):
    for i in range(1,K+1):
      fac = i
      nx = x+fac*dxdy[j][0]
      ny = y+fac*dxdy[j][1]
      #print(nx,ny)
      if nx<0 or nx>=H or ny<0 or ny>= W or Pond[nx][ny] == "@":
        break
      if reach[x][y]+1 > reach[nx][ny]: #すでに余裕をもって到達済み
        break
      if reach[x][y]+1 < reach[nx][ny]:
        reach[nx][ny] = min(reach[x][y]+1,reach[nx][ny])
        Q.append((nx,ny))
      if nx == gx and ny == gy:
        #print(reach)
        print(reach[nx][ny])
        exit()
print(-1)
### BUGGY CODE ###

import itertools
x,y,z,k = list(map(int, input().split())) 
a = sorted(list(map(int, input().split())),reverse=True)
b = sorted(list(map(int, input().split())),reverse=True)
c = sorted(list(map(int, input().split())),reverse=True)

del a[min(k,x):]
del b[min(k,y):]
del c[min(k,z):]

ab = sorted([i + j for (i, j) in list(itertools.product(a, b))],reverse=True)
del ab[min(k,x*y):]

abc = sorted([ij + h for (ij, h) in list(itertools.product(ab, c))],reverse=True)

for g in range(k):
  print(abc[g])

### FIXED CODE ###

import heapq
x,y,z,k = list(map(int, input().split())) 
a = sorted(list(map(int, input().split())),reverse=True)
b = sorted(list(map(int, input().split())),reverse=True)
c = sorted(list(map(int, input().split())),reverse=True)

ans = []
log = set()

total = (a[0] + b[0] + c[0]) * (-1)
heapq.heappush(ans, (total, 0, 0, 0))
log.add((0, 0, 0))

for i in range(k):
  (total, aa, bb, cc) = heapq.heappop(ans)
  print(total * (-1))
  if (aa+1, bb, cc) not in log:
    if aa+1 < x:
      total = (a[aa+1] + b[bb] + c[cc]) * (-1)
      heapq.heappush(ans, (total, aa+1, bb, cc))
      log.add((aa+1, bb, cc))
  if (aa, bb+1, cc) not in log:
    if bb+1 < y:
      total = (a[aa] + b[bb+1] + c[cc]) * (-1)
      heapq.heappush(ans, (total, aa, bb+1, cc))
      log.add((aa, bb+1, cc))
  if (aa, bb, cc+1) not in log:
    if cc+1 < z:
      total = (a[aa] + b[bb] + c[cc+1]) * (-1)
      heapq.heappush(ans, (total, aa, bb, cc+1))
      log.add((aa, bb, cc+1))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
total=sum(A)
for i in range(Q):
    B, C = map(int, input().split())
    x=A.count(B)
    if x>0:
        for j in range(0,x):
            y=A.index(B)
            total=total-A[y]+C
            A[y]=C
    print(total)



### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
total=sum(A)
A=Counter(A)
for i in range(Q):
    B, C = map(int, input().split())
    total=total-(A[B]*B)+(C*A[B])
    A[C] = A[C]+A[B]
    A[B]=0
    print(total)
### BUGGY CODE ###

def main():
	N, M = map(int, input().split())
	INF = 2**30-1
	mat = [[] for _ in range(3*N)]
	for _ in range(M):
		u, v = map(int, input().split())
		mat[u-1].append([N+v-1, 1])
		mat[N+u-1].append([2*N+v-1, 1])
		mat[2*N+u-1].append([v-1, 1])

	S, T = map(int, input().split())
	queue = list(mat[S-1])
	visited = [False]*(3*N)
	visited[S-1] = True
	while queue:
		pos, d = queue.pop()
		if pos == T-1:
			print(d//3)
			return
		visited[pos] = True
		next_positions = mat[pos]
		for next_pos, next_d in next_positions:
			if visited[next_pos]:
				continue
			queue.append([next_pos, d+next_d])
		queue.sort(key=lambda x: x[1])
	print(-1)

if __name__ == '__main__':
	main()

### FIXED CODE ###

def main():
	N, M = map(int, input().split())
	INF = 2*31-1
	to = [[] for _ in range(N)]
	for _ in range(M):
		u, v = map(int, input().split())
		to[u-1].append(v-1)
	dist = [[INF, INF, INF] for _ in range(N)]

	S, T = map(int, input().split())
	queue = []
	for pos in to[S-1]:
		queue.append([pos, 1])
		dist[pos][1] = 1
	while queue:
		pos, l = queue.pop(0)
		next_positions = to[pos]
		for next_pos in next_positions:
			nl = (l+1)%3
			if dist[next_pos][nl] != INF:
				continue
			dist[next_pos][nl] = dist[pos][l]+1
			queue.append([next_pos, nl])
	ans = dist[T-1][0]
	if ans == INF:
		print(-1)
	else:
		print(ans//3)

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

A, B = map(int, input().split())
result = A
for i in range(A+1,B+1):
    result ^= i
print(result)

### FIXED CODE ###

A, B = map(int, input().split())
def calc(a):
    cnt = (a + 1) // 2
    ans = cnt % 2
    if a % 2 == 0:
        ans ^= a
    return ans
print(calc(A-1) ^ calc(B))







1
### BUGGY CODE ###

import math
import copy

MOD = 998244353

n = int(input())
xs = []
total = 0
for _ in range(n):
    t = int(input())
    xs.append(t)
    total += t

dp = [[0] * (total+1) for _ in range(n)]

dp[0][0] = 2
dp[0][xs[0]] = 1

curtotal = xs[0]
for i in range(1,n): # length of
    s = xs[i]
    curtotal += s
    for j in range (0,curtotal+1):
        dp[i][j] = (dp[i-1][j] * 2) % MOD
        if j - s >= 0:
            dp[i][j] = (dp[i][j] + dp[i-1][j-s]) % MOD


plus = 0
if total % 2 == 0:
    dp2 = [0] * (total // 2 + 1)
    dp2[0] = 1
    curtotal = 0
    for i in range(n):
        s = xs[i]
        curtotal += s
        prev = copy.copy(dp2)
        for j in range(0,min(len(dp2), curtotal+1)):
            if j-s >= 0:
                dp2[j] =  (dp2[j] + prev[j-s]) % MOD
                #print(i,j,s,dp2)
    plus = dp2[total//2]

#print(dp2)
minus = 0
for i in range(math.ceil(total/2), total+1):
    minus = (minus + dp[n-1][i]) % MOD


#print(3**n, minus, plus)
print(((3**n)%MOD - minus*3 + plus*3) % MOD)


### FIXED CODE ###

import math
import copy
import numpy as np

MOD = 998244353

n = int(input())
xxs = []
total = 0
for _ in range(n):
    t = int(input())
    xxs.append(t)
    total += t

xs = np.array(xxs)
dp = np.array([[0] * (total+1) for _ in range(n)])

dp[0][0] = 2
dp[0][xs[0]] = 1

curtotal = xs[0]
for i in range(1,n): # length of
    s = xs[i]
    curtotal += s
    dp[i] = (dp[i-1] * 2)
    dp[i][s:] += dp[i-1][:-s]
    dp[i] %= MOD

#print(dp)

plus = 0
if total % 2 == 0:
    dp2 = np.array([0] * (total // 2 + 1))
    dp2[0] = 1
    curtotal = 0
    for i in range(n):
        s = xs[i]
        curtotal += s
        prev = copy.copy(dp2)
        dp2[s:] += prev[:-s]
        dp2 %= MOD
    plus = dp2[total//2]

#print(dp2)
minus = 0
for i in range(math.ceil(total/2), total+1):
    minus = (minus + dp[n-1][i]) % MOD


#print(3**n, minus, plus)
print(((3**n)%MOD - minus*3 + plus*3) % MOD)
### BUGGY CODE ###

n = int(input())
p = list(map(int,input().split()))
c = 1
for i in range(1,n):
  tmp = min(p[:i])
  if(tmp >= p[i]):
    c = c + 1
      
print(c)

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
c = 1
tmp = p[0]
for i in range(1,n):
  tmp = min(tmp,p[i])
  if(tmp >= p[i]):
    c = c + 1
      
print(c)
### BUGGY CODE ###


n = int(input())

pr = []
i = 2
while(True):
    for p in pr:
        if(i % p == 0):break
    else:
        if(i >= n):
            print(i)
            exit()
        pr.append(i)
    i += 1


### FIXED CODE ###

import random

def is_prime(q,k=50):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        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

n = int(input())

i = n
while(not is_prime(i)):i += 1
print(i)
### BUGGY CODE ###

N,K = map(int, input().split())
lst = list(map(int, input().split()))
dp = [0 for i in range(N)]
for i in range(1,N):
    mn = 999999999999999999
    for j in range(max(i-K,0), i):
        mn = min(mn,dp[j] + abs(lst[i] - lst[j]))
    dp[i] = mn
print(dp[-1])

### FIXED CODE ###

N,K = map(int, input().split())
lst = list(map(int, input().split()))
dp = [0 for i in range(N)]
for i in range(1,N):
    mn = 999999999999999999
    for j in range(max(i-K,0), i):
        mn = min(mn,dp[j] + abs(lst[i] - lst[j]))
    dp[i] = mn
print(dp[-1])
### BUGGY CODE ###

n,x,m= list(map(int, input().strip().split()))
a=[0]*(m)
for i in range(m):
    a[i]=i*i%m
a=list(set(a))
t=0
b=[]
b.append(x)
for i in range(m+1):
        b.append(b[-1]**2%m)
        if len(b)>len(list(set(b))):
            break
l=len(b)
for i in range(l-1):
    if b[i]==b[l-1]:
        q=i
w=l-2-q+1
s=0
for i in range(q):
    s+=b[i]
t=0
for i in range(q,l-1):
    t+=b[i]
u=(n-q)//w
v=(n-q)%w
ans=0
for i in range(q,q+v):
    ans+=b[i]
ans+=s+u*t

print(ans)
    


### FIXED CODE ###

n,x,m= list(map(int, input().strip().split()))
t=0
b=[]
b.append(x)
for i in range(m+1):
        if b[-1]**2%m in b:
            b.append(b[-1]**2%m)
            break
        else:
            b.append(b[-1]**2%m)
        
l=len(b) 
for i in range(l-1):
    if b[i]==b[l-1]:
        q=i
w=l-2-q+1
s=0
for i in range(q):
    s+=b[i]
t=0
for i in range(q,l-1):
    t+=b[i]
u=(n-q)//w
v=(n-q)%w
ans=0
for i in range(q,q+v):
    ans+=b[i]
ans+=s+u*t

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

n,m = map(int,input().split())
a = []
b = []
for i in range(n):
	k,l = map(int,input().split())
	a.append(k)
	b.append(l)

ans = 0
for v in range(1,m+1):
	tmp = [i for i,x in enumerate(a) if x <= v]
	if len(tmp)!=0:
		b_list = [b[i] for i in tmp]
		max_index = tmp[b_list.index(max(b_list))]
		ans += b[max_index]
		del(a[max_index])
		del(b[max_index])
print(ans)

### FIXED CODE ###

import heapq
#標準入力受け取り
N, M = list(map(int, input().split()))
jobs = [[] for _ in range(M)]

for i in range(N):
    d, r = list(map(int, input().split()))
    if d-1 < M:
        jobs[d-1].append(-r)

#解法
rewards = 0
heap = []
for i in range(M):
	for reward in jobs[i]:
		heapq.heappush(heap,reward)

	if len(heap)>0:
		reward = heapq.heappop(heap)
		rewards += -reward

print(rewards)
### BUGGY CODE ###

R,G,B,n=map(int, input().split())
ans=0

for r in range(n+1):
    for g in range(n+1-r):
        b = n-r-g
        if b%B==0 and r%R==0 and g%G==0:
            ans+=1

print(ans)


### FIXED CODE ###

R,G,B,n=map(int, input().split())
ans=0

for r in range(n+1):
    if r%R==0:
        for g in range(n+1-r):
            b = n-r-g
            if b%B==0 and r%R==0 and g%G==0:
                ans+=1

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

#coding:utf-8
import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    s = input()
    K = II()
    subs = set()
    for i in range(len(s)):
        for j in range(i+1,len(s)+1):
            subs.add(s[i:j])
    subs = sorted(list(subs))
    print(subs[K-1])
    

if __name__ == '__main__':
    main()

### FIXED CODE ###

#coding:utf-8
import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    s = input()
    K = II()
    subs = set()
    for i in range(len(s)):
        for j in range(i+1,min(len(s)+1,i+6)):
            subs.add(s[i:j])
    subs = sorted(list(subs))
    print(subs[K-1])
    

if __name__ == '__main__':
    main()