Harryxun/stf_run huggingface dataset:
from copy import deepcopy

N, M, K = map(int, input().split())
FRIENDS = [list(map(int, input().split())) for _ in range(M)]
BLOCKS = [list(map(int, input().split())) for _ in range(K)]

def search(i, friends):
    copied_friends = deepcopy(friends)
    res = []
    for a, b in friends:
        if a == i:
            copied_friends.remove([a, b])
            res.append(b)    
        if b == i:
            copied_friends.remove([a, b])
            res.append(a)
    
    return res, copied_friends

    
def find(i, j, friends):
    for a, b in friends:
        if a == i and b == j:
            return True
        if b == i and a == j:
            return True
    
    return False

    
def dfs(i, friends):
    if len(friends) == 0:
        return [i]

    targets, new_friends = search(i, friends)
    for t in targets:
        if targets.count(t) <= 1:
            targets += dfs(t, new_friends)
        
    return targets


results = []
for i in range(1, N+1):
    targets = list(set(dfs(i, FRIENDS)))
    targets = filter(lambda x: not find(x, i, FRIENDS), targets)
    targets = filter(lambda x: not find(x, i, BLOCKS), targets)

    results.append(len(list(targets)))

print(" ".join(map(str, results)))

### FIXED CODE ###

import math
N = int(input())
print(math.ceil(N/2))
a,*b,c = input().split()
print(a+len(b)+c)

### FIXED CODE ###

a = input()
print(a[0]+str(len(a)-2)+a[-1])
icase=3
if icase==0:
    x,y,z,k=map(int,input().split())
    a=list(map(int,input().split()))
    b=list(map(int,input().split()))
    c=list(map(int,input().split()))

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

kk=1

ix=0
iy=0
iz=0
ss=[]
s=a[ix]+b[iy]+c[iz]

xyz=[]
xyz.append((ix+1,iy,iz))
xyz.append((ix,iy+1,iz))
xyz.append((ix,iy,iz+1))

#print(ix,iy,iz,s)
#print(xyz)
ss.append(s)
while kk<k:
    kk+=1
    s1=0
    for ix,iy,iz in xyz:
        s2=a[ix]+b[iy]+c[iz]
        if s2>s1:
            s1=s2
            ixx,iyy,izz=ix,iy,iz
#    print("1:",ixx,iyy,izz,s2)
    xyz.remove((ixx,iyy,izz))
    if ixx<x-1 and ((ixx+1,iyy,izz) not in xyz): 
        xyz.append((ixx+1,iyy,izz))
    if iyy<y-1 and ((ixx,iyy+1,izz) not in xyz): 
        xyz.append((ixx,iyy+1,izz))
    if izz<z-1 and ((ixx,iyy,izz+1) not in xyz): 
        xyz.append((ixx,iyy,izz+1))
#    print(ixx,iyy,izz,s1)
#    print(xyz)
    ss.append(s1)

for kk in range(k):
    print(ss[kk])        


### FIXED CODE ###

icase=0
if icase==0:
    x,y,z,k=map(int,input().split())
    a=list(map(int,input().split()))
    b=list(map(int,input().split()))
    c=list(map(int,input().split()))

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

kk=1

ix=0
iy=0
iz=0
ss=[]
s=a[ix]+b[iy]+c[iz]

xyz=[]
xyz.append((ix+1,iy,iz))
xyz.append((ix,iy+1,iz))
xyz.append((ix,iy,iz+1))

#print(ix,iy,iz,s)
#print(xyz)
ss.append(s)
while kk<k:
    kk+=1
    s1=0
    for ix,iy,iz in xyz:
        s2=a[ix]+b[iy]+c[iz]
        if s2>s1:
            s1=s2
            ixx,iyy,izz=ix,iy,iz
#    print("1:",ixx,iyy,izz,s2)
    xyz.remove((ixx,iyy,izz))
    if ixx<x-1 and ((ixx+1,iyy,izz) not in xyz): 
        xyz.append((ixx+1,iyy,izz))
    if iyy<y-1 and ((ixx,iyy+1,izz) not in xyz): 
        xyz.append((ixx,iyy+1,izz))
    if izz<z-1 and ((ixx,iyy,izz+1) not in xyz): 
        xyz.append((ixx,iyy,izz+1))
#    print(ixx,iyy,izz,s1)
#    print(xyz)
    ss.append(s1)

for kk in range(k):
    print(ss[kk])
A, B, C = map(int, input().split())

if A[-1] == B[0] and B[-1] == C[0]:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

A, B, C = input().split()

if A[-1] == B[0] and B[-1] == C[0]:
    print('YES')
else:
    print('NO')
a,b=map(int.input(),split())
if a-b＊2<=0:
 print(0)
else:
 print(a-b＊2)
  


### FIXED CODE ###

a,b=map(int,input().split())
if a-b*2<=0:
  
  print(0)
else:
  print(a-b*2)
import math as m

def Div():
    N = int(input())
    c = 0
    k = N//2 + 1
    for i in range(2,k):
        if(prime(i)):
            for j in range(1,int(m.sqrt(N))+1):
                p = i ** j
                if(p>N):
                    break
                if(N%p==0):
                    N = N //p
                    c = c + 1
    
    return c

print(Div())

### FIXED CODE ###

from math import floor
A= input().split()
p = int(A[0])
q = round(float(A[1])*100)
t = p*q
t //= 100
print(t)
n = int(input())
a = list(map(int, input().split()))
res = 2020202020
for i in range(n):
  res = min(res, abs(a[:i] - a[i:]))
print(res)

### FIXED CODE ###

import itertools
n = int(input())
a = list(itertools.accumulate(list(map(int, input().split()))))
sum_a = a[-1]
res = 2020202020
for i in range(n):
  res = min(res, abs(sum_a - a[i]*2))
print(res)
n = int(input())
a = list(map(lambda x:int(x)-1,input()))
ans = 0
for i in range(n):
    if (n-1) & i == i:
        ans += a[i]
if ans % 2 == 1:
    print(1)
else:
    if a.count(1) != 0:
        print(0)
    else:
        ans = 0
        b = map(lambda x:x//2,a)
        for i in range(n):
            if (n-1) & i == i:
                ans += b[i]
        if ans % 2 == 1:
            print(2)
        else:
            print(0)

### FIXED CODE ###

n = int(input())
a = list(map(lambda x:int(x)-1,input()))
ans = 0
for i in range(n):
    if (n-1) & i == i:
        ans += a[i]
if ans % 2 == 1:
    print(1)
else:
    if a.count(1) != 0:
        print(0)
    else:
        ans = 0
        b = list(map(lambda x:x//2,a))
        for i in range(n):
            if (n-1) & i == i:
                ans += b[i]
        if ans % 2 == 1:
            print(2)
        else:
            print(0)
import numpy as np
sho_ls = []
amari_ls = []
a_ls = []
for _ in range(5):
    a = int(input())
    a_ls.append(a)
    sho, amari = divmod(a,10)
    sho_ls.append(sho)
    amari_ls.append(amari)

amari_ls_not0 = []
for i in range(5):
    if amari_ls[i] != 0:
        amari_ls_not0.append(amari_ls[i])

amari_min_not0 = min(amari_ls_not0)
arg_min = amari_ls.index(amari_min_not0)
ans = 0
for i in range(5):
    if i != arg_min:
        if amari_ls[i] != 0:
            plus = a_ls[i] + 10 - amari_ls[i]
            ans += plus
            
        else:
            plus = a_ls[i]
            ans += plus
plus = a_ls[arg_min]
ans += plus
print(ans)

### FIXED CODE ###

import numpy as np
sho_ls = []
amari_ls = []
a_ls = []
for _ in range(5):
    a = int(input())
    a_ls.append(a)
    sho, amari = divmod(a,10)
    sho_ls.append(sho)
    amari_ls.append(amari)

amari_ls_not0 = []
for i in range(5):
    if amari_ls[i] != 0:
        amari_ls_not0.append(amari_ls[i])

if amari_ls != [0,0,0,0,0]:
    amari_min_not0 = min(amari_ls_not0)
    arg_min = amari_ls.index(amari_min_not0)
else:
    arg_min = 0
ans = 0
for i in range(5):
    if i != arg_min:
        if amari_ls[i] != 0:
            plus = a_ls[i] + 10 - amari_ls[i]
            ans += plus
            
        else:
            plus = a_ls[i]
            ans += plus
plus = a_ls[arg_min]
ans += plus
print(ans)
a, b, c, k = map(int, input().split())

val_a = [1] * a
val_b = [0] * b
val_c = [-1] * c

val_a.extend(val_b)
val_a.extend(val_c)
print(val_a)

print(sum(val_a[:k]))


### FIXED CODE ###

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


if k <= a:
    print(k)
elif k <= a + b:
    print(a)
else:
    r = k - a - b
    print(a-r)
N = int(input())
if N == 1:
    print('Hello World')
else:
    a, b = map(int, input().split())
    print(a + b)


### FIXED CODE ###

# nの約数を求める
def divisor(n):
    d = []
    for i in range(int(n**(0.5)+1))[1:]:
        if n % i == 0:
            d.append(i)
            if i * i != n:
                d.append(int(n / i))
    return d


N, M = map(int, input().split())
# d はnの約数のベクター
d = divisor(M)
g = int(M / N)
d = [x for x in d if x <= g]
print(max(d))
S = list(input())
N = len(S)

counter = 0
i = 0
while(True):
    if not '0' in S or not '1' in S or S == []:
        break
    elif (S[i] == '1' and S[i+1] == '0') or (S[i] == '0' and S[i+1] == '1'):
        S.pop(i)
        S.pop(i)
        counter += 2
        i -= 1
    else:
        i += 1

print(counter)


### FIXED CODE ###

S = input()
N = len(S)

count0 = S.count('0')
count1 = S.count('1')
ans = 2 * min(count0, count1)
print(ans)
a,b,c=input().split()
print "YES" if a[-1] == b[0] and b[-1] == c[0] else "NO"

### FIXED CODE ###

a,b,c=input().split()
print("YES" if a[-1] == b[0] and b[-1] == c[0] else "NO")
import numpy as np


def solve(stdin):
    A, B, C, D, E, F = stdin
    if A == 1:
        raise
    conc = -1
    ans = (1, 2)
    for na in range(F // (100 * A) + 1):
        for nb in range(F // (100 * B) + 1):
            if na == nb == 0:
                continue
            G = F - na * 100 * A - nb * 100 * B
            for nc in range(G // C + 1):
                for nd in range(G // D + 1):
                    W = na * 100 * A + nb * 100 * B + nc * C + nd * D
                    if 0 < W <= F and nc * C + nd * D <= E * (na * A + nb * B):
                        conc2 = 100 * (nc * C + nd * D) / W
                        if conc < conc2 <= 100 * E / (100 + E):
                            ans = (W, nc * C + nd * D)
                            conc = conc2
    return ans


def main():
    stdin = np.fromstring(open(0).read(), dtype=np.int64, sep=' ')
    print(*solve(stdin))


def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()


if __name__ == '__main__':
    import sys
    if sys.argv[-1] == 'ONLINE_JUDGE':
        cc_export()
        exit(0)
    from my_module import solve
    main()


### FIXED CODE ###

import itertools
A, B, C, D, E, F = [int(_) for _ in input().split()]
W = [0] * (F+1)
S = [0] * (F+1)
for a, b in itertools.product(range(F // (100*A) + 1), range(F//(100*B) + 1)):
    if 100*A*a+100*B*b <= F:
        W[100*A*a+100*B*b] = min(E*(A*a+B*b), F-100*A*a-100*B*b)

for c, d in itertools.product(range(F // C + 1), range(F // D + 1)):
    if C*c+D*d <= F:
        S[C*c+D*d] = C*c+D*d
for i in range(F):
    if S[i+1] == 0:
        S[i+1] = S[i]
water = 100*A
sugar = 0
for i in range(1, F+1):
    if W[i] and S[W[i]]/i > sugar/water:
        sugar, water = S[W[i]], i
print(sugar+water, sugar)
N = int(input())
H = list(map(int, input().split()))
list = []
a = 0
for i in range(N-1):
  if H[i] >= H[i+1]:
    a += 1
    list.append(a)
  else:
    list.append(a)
    a = 0
list = sorted(list)
print(list[-1])
  

### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
list = []
a = 0
for i in range(N-1):
  if H[i] >= H[i+1]:
    a += 1
  else:
    list.append(a)
    a = 0
list.append(a)
list = sorted(list)
print(list[-1])
split())
print("Yes" if 2*max(a,b,c)==a+b+c else "No")

### FIXED CODE ###

a,b,c=map(int,input().split())
print("Yes" if 2*max(a,b,c)==a+b+c else "No")
p = [int(i) for i in m]
n = input()    
m = n.split()
P = [int(i) for i in m]
n = input()
list = [""]*p[1]
for i, value in enumerate(n):
    list[i%p[1]] =list[i%p[1]] + value
A = 0
for i in list:
    able = [True,True,True]
    for j in i:
        if j == "r":
            if able[2]:
                A = A + P[2]
                able = [True,True,False]
            else:
                able = [True,True,True]
        if j == "s":
            if able[0]:
                A = A + P[0]
                able = [False,True,True]
            else:
                able = [True,True,True]
        if j == "p":
            if able[1]:
                A = A + P[1]
                able = [True,False,True]
            else:
                able = [True,True,True]

print(A)

### FIXED CODE ###

n = input()    
m = n.split()
p = [int(i) for i in m]
n = input()    
m = n.split()
P = [int(i) for i in m]
n = input()
list = [""]*p[1]
for i, value in enumerate(n):
    list[i%p[1]] =list[i%p[1]] + value
A = 0
for i in list:
    able = [True,True,True]
    for j in i:
        if j == "r":
            if able[2]:
                A = A + P[2]
                able = [True,True,False]
            else:
                able = [True,True,True]
        if j == "s":
            if able[0]:
                A = A + P[0]
                able = [False,True,True]
            else:
                able = [True,True,True]
        if j == "p":
            if able[1]:
                A = A + P[1]
                able = [True,False,True]
            else:
                able = [True,True,True]

print(A)
n=int(input())
A=list(map(int,input().split()))
ma = max(A)
mid = ma / 2
l = 10000000000
for i in rage(n):
  l = min(l, abs(A[i]-mid))
print(ma, mid-l)

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
ma = max(A)
mid = ma / 2
l = 10000000000
f = 0
for i in range(n):
  if ((ma == A[i]) and (f==0)):
    f = 1
    continue
  if abs(l) > abs(A[i]-mid):
    l = A[i]-mid
print(ma, int(mid+l))
a=int(input())
b=int(input())
if a%2==0 or b%2==0:
  print('Even')
else:
  print('Odd')

### FIXED CODE ###

a,b=map(int,input().split())
if a%2==0 or b%2==0:
    print('Even')
else:
    print('Odd')
n,m,q = map(int,input().split())
arr = [list(map(int,input().split())) for x in range(q)]
ans = 0

for i1 in range(1,m+1):
  for i2 in range(i1,m+1):
    for i3 in range(i2,m+1):
      for i4 in range(i4,m+1):
        for i5 in range(i4,m+1):
          for i6 in range(i5,m+1):
            for i7 in range(6,m+1):
              for i8 in range(i7,m+1):
                for i9 in range(i8,m+1):
                  for i10 in range(i9,m+1):
                    tmp = 0
                    arrs = [0,i1,i2,i3,i4,i5,i6,i7,i8,i9,i10]
                    for a,b,c,d in arr:
                      if arrs[b] - arrs[a] == c:
                        tmp += d
                    ans = max(ans,tmp)
print(ans)

### FIXED CODE ###

n,m,q = map(int,input().split())
arr = [list(map(int,input().split())) for x in range(q)]
ans = 0

for i1 in range(1,m+1):
  for i2 in range(i1,m+1):
    for i3 in range(i2,m+1):
      for i4 in range(i3,m+1):
        for i5 in range(i4,m+1):
          for i6 in range(i5,m+1):
            for i7 in range(i6,m+1):
              for i8 in range(i7,m+1):
                for i9 in range(i8,m+1):
                  for i10 in range(i9,m+1):
                    tmp = 0
                    arrs = [0,i1,i2,i3,i4,i5,i6,i7,i8,i9,i10]
                    for a,b,c,d in arr:
                      if arrs[b] - arrs[a] == c:
                        tmp += d
                    ans = max(ans,tmp)
print(ans)
n = int(input())
a = list(map(int, input().split()))
 
result = 0
les = 0
while les == 0:
  for i in range(n):
    les += a[i] % 2
    a[i] = a[i]/2
  result += 1
  
result -= 1
print(result)

### FIXED CODE ###

print(input().count("1"))
import math
import sys
sys.setrecursionlimit(100000)

n = int(input())
s = int(input())

up = math.sqrt(n)

def colsum(num, base):
    if num < base:
        return num
    else:
        return num%base + colsum(num//base,base)

#s = n(n<b)
if s == n:
    print(n+1)
    exit()


#sqrt(n)まで探索
for i in range(2,int(up)+1):
    if s == colsum(n,i):
        print(i)
        exit()

#2桁しかあり得ない場合(sqrt(n)<b<n)
for j in range(2,int(up)+1):
#    if (n-s)%j == 0:
        b = (n-s)//j + 1
        if s == colsum(n,b) and b > 1:
            print(i)
            exit()

print(-1)

### FIXED CODE ###

import math
import sys

n = int(input())
s = int(input())

up = math.sqrt(n)

def colsum(num, base):
    if num < base:
        return num
    else:
        return num%base + colsum(num//base,base)

#s >= n
if s == n:
    print(n+1)
elif s > n:
    print(-1)
else:
    #sqrt(n)まで探索
    for i in range(2,int(up)+1):
        if colsum(n,i) == s:
            print(i)
            sys.exit()

    #2桁しかあり得ない場合(sqrt(n)<b<n)
    for j in range(int(up),0,-1):
        if (n-s)%j == 0:
            b = (n-s)/j + 1
            if colsum(n,b) == s and b > 1:
                print(int(b))
                sys.exit()

    print(-1)
import sys
sys.setrecursionlimit(10 ** 7)

N = int(input())
A = list(map(int, input().split()))
color = [0] * 3 # 赤色・青色・緑色の帽子を被っている人数
answer = 1 
MOD = 10 ** 9 + 7

for a in A:
    answer *= color.count(a)
    # aと同じ人数が複数ある場合は一番左の色としてカウント
    i = color.index(a)
    color[i] += 1
    answer %= MOD

print(answer)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

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

color = [0] * 3 # 赤色・青色・緑色の帽子を被っている人数
answer = 1 
MOD = 10 ** 9 + 7

for a in A:
    if color.count(a) == 0:
        print(0)
        exit()
    answer *= color.count(a)
    # aと同じ人数が複数ある場合は一番左の色としてカウント
    i = color.index(a)
    color[i] += 1
    answer %= MOD

print(answer)
N, K = map(int, input().split())

L = [0 for i in range(N+1)]

for i in range(K):
  d = int(input())
  for j in range(d):
    s = int(input())
    L[s] += 1

ans = 0
for i in range(1,N+1):
  if L[i] == 0:
    ans += 1
print(ans)

### FIXED CODE ###

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

L = [0 for i in range(N+1)]

for i in range(K):
  d = int(input())
  LL = list(map(int, input().split()))
  for j in range( len(LL) ):
    L[ LL[j] ] += 1

ans = 0
for i in range(1,N+1):
  if L[i] == 0:
    ans += 1
print(ans)
import sys
n,y = map(int, input().split())

for a in range(n+1):
	for b in range(n+1-a):
#	  if (a * 10000 + b * 5000 + (n-a-b) * 1000 == y):
#		print(str(a) + ' ' + str(b) + ' ' + str(c))
#		sys.exit()

print('-1 -1 -1')
sys.exit()

### FIXED CODE ###

import sys

n,y = map(int, input().split())

for a in range(n+1):
	for b in range(n+1-a):
		c = n - a - b
		if (a * 10000 + b * 5000 + c * 1000 == y):
				print(str(a) + ' ' + str(b) + ' ' + str(c))
				sys.exit()
	
print('-1 -1 -1')
sys.exit()
h, w = map(int, input().split())

if h == 1 or w == 1:
    print(1)
else:
    hc = (w+1) // 2
    hc2 = w // 2
    d, m = divmod(h, 2)
    ans = d * (hc + hc2) + m * hc

print(ans)


### FIXED CODE ###

h, w = map(int, input().split())

if h == 1 or w == 1:
    print(1)
else:
    hc = (w+1) // 2
    hc2 = w // 2
    d, m = divmod(h, 2)
    ans = d * (hc + hc2) + m * hc
    print(ans)
h,w=map(int,input().split())
board=[list(map(int,input().split())) for _ in range(h)]
pos="ABCDEFGHIJKLMNOPQRSTUVWXYZ"
for i in range(h):
  for j in range(w):
    if board[i][j]=="snuke":
      print(pos[j]+str(i+1))
      exit()

### FIXED CODE ###

h,w=map(int,input().split())
board=[list(map(str,input().split())) for _ in range(h)]
pos="ABCDEFGHIJKLMNOPQRSTUVWXYZ"
for i in range(h):
  for j in range(w):
    if board[i][j]=="snuke":
      print(pos[j]+str(i+1))
      exit()
import sys
from collections import deque

def bfs(maze, visited):
    try:
        sy,sx=0,0
        gy,gx=H-1,W-1
        queue = deque([[sy, sx]])
        visited[sy][sx] = 0
        while queue:
            y, x = queue.popleft()
            if [y, x] == [gy, gx]:
                return visited[y][x]

            p=[]
            if x>0 : p.append([0,-1])
            if x<W-1: p.append([0,1])
            if y>0: p.append([-1,0])
            if y<H-1: p.append([1,0])
            for j, k in p:
                new_y, new_x = y+j, x+k
                if maze[new_y][new_x] == "." and \
                    visited[new_y][new_x] == -1:
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])
    except RuntimeError:
        print(-1)


H,W=map(int,input().split())
m=[input() for i in range(H)]

ans=0
for i in range(H):
    for j in range(W):
        if m[i][j]==".": ans+=1

visited=[[-1]*W for i in range(H)]
print(ans-bfs(m,visited)-1)

### FIXED CODE ###

import sys
from collections import deque

def bfs(maze, visited):
    try:
        sy,sx=0,0
        gy,gx=H-1,W-1
        queue = deque([[sy, sx]])
        visited[sy][sx] = 0
        while queue:
            y, x = queue.popleft()
            if [y, x] == [gy, gx]:
                return visited[y][x]

            p=[]
            if x>0 : p.append([0,-1])
            if x<W-1: p.append([0,1])
            if y>0: p.append([-1,0])
            if y<H-1: p.append([1,0])
            for j, k in p:
                new_y, new_x = y+j, x+k
                if maze[new_y][new_x] == "." and \
                    visited[new_y][new_x] == -1:
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])
        return -1

    except RuntimeError:
        print(-1)
        sys.exit()


H,W=map(int,input().split())
m=[input() for i in range(H)]

ans=0
for i in range(H):
    for j in range(W):
        if m[i][j]==".": ans+=1

visited=[[-1]*W for i in range(H)]
p=bfs(m,visited)
print( p if p==-1 else ans-p-1)
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,x,m = list(map(int, input().split()))
v = x
seen = [0]*m
c = 0
val = 0
count = 0
tmp = 0
if n>m:
    for i in range(m):
        if seen[v]==2:
            break
        if seen[v]==1:
            count += 1
            tmp += v
        else:
            val += v
            c += 1
        seen[v] += 1
        v = (v**2)%m
    ans = val + ((n-c)//count) * tmp
    for i in range((n-c)%(count)):
        ans += v
        v = (v**2)%m
else:
    ans = 0
    v = x
    for i in range(n):
        ans += v
        v = (v**2)%m
print(ans)

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,x,m = list(map(int, input().split()))
v = x
seen = [0]*m
c = 0
val = 0
count = 0
tmp = 0
if n>m:
    while True:
        if seen[v]==2:
            break
        if seen[v]==1:
            count += 1
            tmp += v
        else:
            val += v
            c += 1
        seen[v] += 1
        v = (v**2)%m
    ans = val + ((n-c)//count) * tmp
    for i in range((n-c)%(count)):
        ans += v
        v = (v**2)%m
else:
    ans = 0
    v = x
    for i in range(n):
        ans += v
        v = (v**2)%m
print(ans)
n,m=map(int,input().split())
broken=[int(input()) for i in range(m)]
mod=10**9+7

is_broken=[True]*(n+1)
for i in range(m):
  is_broken[broken[i]]=False
   
dp=[0]*(n+1)

if  is_broken[1]:
  dp[1],dp[2]=1,2
else:
  if is_broken[2]:
    dp[2]=1

if n>=2:
  for i in range(3,n+1):
    if is_broken[i]:
       dp[i]=dp[i-1]+dp[i-2]
       dp[i]%=mod
    else:
      dp[i]=0
      
print(dp[n])   


### FIXED CODE ###

n,m=map(int,input().split())
broken=[int(input()) for i in range(m)]
mod=10**9+7

is_broken=[True]*(n+1)
for i in range(m):
  is_broken[broken[i]]=False
   
dp=[0]*(n+1)
dp[0]=1
if is_broken[1]:
  dp[1]=dp[0]
  
for i in range(2,n+1):
    if is_broken[i]:
       dp[i]=dp[i-1]+dp[i-2]
       dp[i]%=mod
    else:
      dp[i]=0
      
print(dp[n])
[N,L] = [int(x) for x in input().split()]
A = {}
B = [0]*N
ANS = {}
count = 0
for i,x in enumerate(input().split()):
    i = int(i)
    x = int(x)
    B[i] = x
    if x in A : A[x] += [i]
    else : A[x] = [i]
for i in A:
    j=1
    while j < len(A[i]) - 1:
        if A[i][j+1]-A[i][j-1] < L*2 :
            del A[i]
            continue
        j += 1
for i in sorted(A) :
    for j in A[i] :
        for k in range(L) :
            if j + k not in ANS :
                ANS[j+k] = i
                count += 1
    if count > N * 0.997 : break
        
for i in range(L):
    if i not in ANS : ANS[i] = min(B[:i+1])
for i in range(L,N):
    if i not in ANS : ANS[i] = min(B[i+1-L:i+1])
for i in range(L-1,N-1) : print(ANS[i], end=" ")
print(ANS[N-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])