Harryxun/stf_run huggingface dataset:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

#n = int(input())
def main():
    n,q = [int(i) for i in readline().split()]
    assert (n,q) != (4,3)
    
    g = [[] for _ in range(n)]
    for i in range(n-1):
        a,b = [int(i) for i in readline().split()]
        g[a-1].append(b-1)
        g[b-1].append(a-1)

    add = [0]*n
    for _ in range(q):
        p,x = [int(i) for i in readline().split()]
        add[p-1] += x

    ans = [0]*n
    #ans[0] = add[0]

    def dfs(v,p,value): #p: parent of v
        value += add[v]
        ans[v] = value
        for c in g[v]:
            if c == p: continue
            dfs(c,v,value)

    dfs(0,-1,0)

#print(add)

    print(*ans)


main()



### FIXED CODE ###

# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

#n = int(input())
n,q = [int(i) for i in readline().split()]

g = [[] for _ in range(n)]
for i in range(n-1):
    a,b = [int(i) for i in readline().split()]
    g[a-1].append(b-1)
    g[b-1].append(a-1)

add = [0]*n
for _ in range(q):
    p,x = [int(i) for i in readline().split()]
    add[p-1] += x

ans = [0]*n
#ans[0] = add[0]

def dfs(v,p,value): #p: parent of v
    value += add[v]
    ans[v] = value
    for c in g[v]:
        if c == p: continue
        dfs(c,v,value)

dfs(0,-1,0)

#print(add)

print(*ans)
import math

def dist(x, y):
    return math.sqrt(x^2+y^2)

# in_values = input()

l = list(map(int, input().split()))
n = l[0]
d = l[1]

count = 0
for _ in range(n):
    l = list(map(int, input().split()))
    if dist(l[0], l[1]) <= d:
        count+=1

print(count)

### FIXED CODE ###

import math

def dist(x, y):
    return math.sqrt(x**2+y**2)

# in_values = input()

l = list(map(int, input().split()))
n = l[0]
d = l[1]

count = 0
for _ in range(n):
    l = list(map(int, input().split()))
    if dist(l[0], l[1]) <= d:
        count+=1

print(count)
s = input().split()
print(s[0] * s[1])

### FIXED CODE ###

s = input().split()
A = int(s[0])
B = int(s[1])
print(A * B)
n=input()
a=map(int,raw_input().split())
a=reverse

for i in n:
    print a

### FIXED CODE ###

n=input()
a=map(int,raw_input().split())
a.reverse()

for i in a:
    print i,
import sys
s = list(raw_input())
if len(s) == 2:
    if s[0] == s[1]:
        print 1, 2
    else
        print -1, -1
else:
    for n in range(3, 100):
        for i in xrange(len(s) - n + 1):
            sub = s[i:i+n]
            for char in set(sub):
                if sub.count(char) >= n / 2 + n % 2:
                    print i + 1, i + n
                    sys.exit()
    print -1, -1


### FIXED CODE ###

import sys
s = list(raw_input())
if len(s) == 2:
    if s[0] == s[1]:
        print 1, 2
    else:
        print -1, -1
else:
    for n in [3]:
        for i in xrange(len(s) - n + 1):
            sub = s[i:i+n]
            for char in set(sub):
                if sub.count(char) >= n / 2 + n % 2:
                    print i + 1, i + n
                    sys.exit()
    print -1, -1
num = int(input())
array = map(int, input().split())
sum = 0
 
for (i = 0; i < num; i++):
	if i == 0:
      sum += array[i]
    else if i < (num-1):
      if array[i] > array[i-1]:
        sum += array[i]
      else:
        sum += array[i-1]
    else:
      sum += array[i-1]
        
print(sum)

### FIXED CODE ###

num = int(input())
array = list(map(int, input().split()))
sum = 0
 
for i in range(num):
	if i == 0:
		sum += array[i]
	elif i < (num-1):
		if array[i] > array[i-1]:
			sum += array[i-1]
		else:
			sum += array[i]
	else:
		sum += array[i-1]
        
print(sum)
a, b, c= (int(i) for i in input().split())
for i in range(c):
 if(i%2==0):
  a=a//2
  b=b+a
 else:
  b=b//2
  a=a+b
print(a,b)

### FIXED CODE ###

s=input()
if(len(s)==2):
 print(s)
else:
 print(s[-1::-1])
import time
from bisect import *
from random import randint
start = time.time()
def solve():
  D = int(input())
  C = list(map(int, input().split()))
  S = [list(map(int, input().split())) for _ in range(D)]

  ans = [0]*D
  points = [0]*26
  dates = [[-1] for _ in range(26)]
  last = [-1]*26
  for d in range(D):
    for i in range(26):
      points[i] = S[d][i]+C[i]*(d-last[i])*(d-last[i]+1)//2
    maxi = 0
    for i in range(26):
        if points[i]>maxi:
            con = i
            maxi = points[i]
    ans[d] = con+1
    last[con] = d
  score = 0
  for d in range(D):
    dates[ans[d]].append(d)
    score += S[d][ans[d]]
    last[ans[d]] = d
    for j in range(26):
        score -= C[j]*(d-last[j])
  for i in range(26):
    dates[i].append(D)
  # print(score)
  for _ in range(10000):
    d = randint(0,D-1)
    after = randint(0,25)
    before = ans[d]
    new_score = score
    new_score += S[d][after]-S[d][before]
    ind_bef = bisect_right(dates[before],d)-1
    # print(ind_bef)
    new_score -= C[before]*(before-dates[before][ind_bef-1])*(dates[before][ind_bef+1]-before)
    ind_aft = bisect_right(dates[after],d)
    new_score += C[after]*(after-dates[after][ind_aft-1])*(dates[after][ind_aft]-after)
    if new_score>score:
      score = new_score
      ans[d] = after
      insort_right(dates[after],d)
      dates[before].pop(ind_bef)
      print(score)
  return ans
print(*solve(),sep='\n')

### FIXED CODE ###

def solve():
  D = int(input())
  C = list(map(int, input().split()))
  S = [list(map(int, input().split())) for _ in range(D)]

  ans = [1]*D
  
  return ans
print(*solve(),sep='\n')
from math import gcd
n = int(input())
a = [int(x) for x in input().split()]

if n == 2:
    print(max(a))
else:
    
    x, y, z = a[0], a[1], a[2]
    p, q, r = gcd(x, y), gcd(y, z), gcd(z, x)
    gcd_max = max(p, q, r)
    if gcd_max == p:
        without = z
    elif gcd_max == q:
        without = x
    else:
        without = y

    k = gcd(gcd_max, without)   
    for i in range(3, n):
        a_i = a[i]
        if a_i % gcd_max != 0:
            l = gcd(gcd_max, a_i)
            if l >= k:
                gcd_max = l
            else:
                gcd_max = k
                without = a_i
        k = gcd(k, a_i)
print(gcd_max)

### FIXED CODE ###

def gcd(p, q):
    if p < q:
        p, q = q, p
    while q > 0:
        p, q = q, p%q
    return p

n = int(input())
a = [int(x) for x in input().split()]

if n == 2:
    print(max(a))
else:
    x, y, z = a[0], a[1], a[2]
    p, q, r = gcd(x, y), gcd(y, z), gcd(z, x)
    gcd_max = max(p, q, r)
    if gcd_max == p:
        without = z
    elif gcd_max == q:
        without = x
    else:
        without = y

    k = gcd(gcd_max, without)   
    for i in range(3, n):
        a_i = a[i]
        if a_i % gcd_max != 0:
            l = gcd(gcd_max, a_i)
            if l >= k:
                gcd_max = l
            else:
                gcd_max = k
                without = a_i
        k = gcd(k, a_i)
    print(gcd_max)
import numpy as np
def inpl(): return [int(i) for i in input().split()]
def minisum(x):
    mini = np.argmin(x)
    d = len(x)
    if d == 0:
        return 0
    if d == 1:
        return x[0]
    result = 0
    if mini != 0:
        result += minisum(x[:mini])
    if mini != d-1:
        result += minisum(x[mini+1:])
    return result + (d-mini)*(mini+1)*x[mini]

N = input()
a = np.array(inpl())
print(minisum(a))

### FIXED CODE ###

def inpl(): return [int(i) for i in input().split()]
N = int(input())
a = inpl()
b = {a[i]: i for i in range(N)}

left = list(range(N+2))
right = list(range(N+2))

ans = 0
for i in range(N,0,-1):
    x = b[i]
    ans += i*(right[x]-x +1)*(x-left[x] +1)
    right[left[x] - 1] = right[x]
    left[right[x] + 1] = left[x]
print(ans)
h, w = input().split()
for i in range(int(h)):
  row = [input() for i in range(int(w))]
print(row)

### FIXED CODE ###

h, w = list(map(int, input().split()))
a = [input() for i in range(h)]
x_ = [-1, -1, -1, 0, 0, 1, 1, 1]
y_ = [-1, 0, 1, -1, 1, -1, 0, 1]
result = [['0' for i in range(w)] for j in range(h)]
for i in range(h):
  for j in range(w):
    count = 0
    if a[i][j] == '#':
      result[i][j] = '#'
      continue
    for k in range(8):
      x = i+x_[k]
      y = j+y_[k]
      if x<0 or y<0 or x>=h or y>=w:
        continue
      elif a[x][y] == '#':
        count += 1
    result[i][j] = str(count)
for i in result:
  print(''.join(i))
S = input()

ls = len(S)

ans = ''
for i in range(ls):
    ans.append('x')

print(ans)

### FIXED CODE ###

S = input()

ls = len(S)

ans = ''
for i in range(ls):
    ans += 'x'

print(ans)
cube = input()
print(cube**3)



### FIXED CODE ###

cube = int(input())
print(cube**3)
N,K=(int(x) for x in input().split())
b=1
a=1
If N=1:
    print(1)
else:
     while a<=N:
          b=b+1
          a=K**b
     else:
          print(b)



### FIXED CODE ###

N,K=(int(x) for x in input().split())
b=1
a=1
if N==1:
    print(1)
else:
     while a<=N:
          b=b+1
          a=K**b
     else:
          print(b)
a =list(input())
aa=''
for i in range(a):
  if a[i]=='9':
    aa +='1'
  elif a[i]=='1':
    aa +='9'
print(aa)

### FIXED CODE ###

s = input()
a=''
for i in range(len(s)):
  if s[i]=='9':
    a += '1'
  elif s[i]=='1':
    a += '9'
  else:
    a += s[i]
print(a)
while True:
        (a, op, b) = input().split()
        a = int(a)
        b = int(b)

        if op = '?':
              break
        elif op = '+':
              print(a + b)
        elif op = '-':
              print(a - b)
        elif op = '*':
              print(a * b)
        elif op = '/':
              print(a // b)

### FIXED CODE ###

while True:
    (a, op, b) = input().split()
    a = int(a)
    b = int(b)

    if op == '?':
        break
    elif op == '+':
        print(a + b)
    elif op == '-':
        print(a - b)
    elif op == '*':
        print(a * b)
    elif op == '/':
        print(a // b)
print("2018"+input[6:])

### FIXED CODE ###

s=input()
s=s[:3]+"8"+s[4:]
print(s)
n, m ,l = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
b = [list(map(int, input().split())) for j in range(m)]
c = [[0 for i in range(n)] for k in range(l)]

for i in range(n):
    for k in range(l):
        for j in range(m):
            c[i][k] += a[i][j] * b[j][k]

for i in range(n):
    print(" ".join(str(t) for t in c[i]))

### FIXED CODE ###

n, m ,l = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
b = [list(map(int, input().split())) for j in range(m)]
c = [[sum(ak*bk for ak, bk in zip(ai, bj)) for bj in zip(*b)] for ai in a]

for ci in c:
    print(*ci)
a = list(map(int, input().split()))
for a[0] != 0 and a[1] != 0:
    a.sort()
    print(a[0] a[1])
    a = list(map(int, input().split()))

### FIXED CODE ###

while True:
    x,y=map(int,input().split())
    if x+y == 0:break
    if x>y:x,y=y,x
    print(x,y)
import math
n, init = map(int,input().split())
x = list(map(lambda x: abs(int(x)-init), input().split()))
g = x[0]
for i in range(1,n):
    g = math.gcd(g,x[i])
print(g)

### FIXED CODE ###

n, init = map(int,input().split())
x = list(map(lambda x: abs(int(x)-init), input().split()))
g = x[0]
def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x%y)
for i in range(1,n):
    g = gcd(g,x[i])
print(g)
n = input()
count = 0
for i in range(n+1):
  if len(i)%2 == 1:
    count += 1
    
print(count)


### FIXED CODE ###

n = int(input())
count = 0
for i in range(1,n+1):
  if len(str(i))%2 == 1:
    count += 1
    
print(count)
import math
# import itertools
# import statistics
# import numpy as np
#n = int(input())
a, b, c, d = list(map(int, input().split()))
#b = list(map(int, input().split()))
total = b-a+1
lcm = int((c*d)/math.gcd(c, d))

d1 = b//c - a//c
d2 = b//d - a//d
add = b//lcm - a//lcm
if a % c == 0:
    d1 += 1
if a % d == 0:
    d2 += 1

print(total-d1-d2+add)


### FIXED CODE ###

from fractions import gcd
a, b, c, d = list(map(int, input().split()))
#b = list(map(int, input().split()))
total = b-a+1
lcm = int((c*d)/gcd(c, d))

d1 = b//c - a//c
d2 = b//d - a//d
add = b//lcm - a//lcm
if a % c == 0:
    d1 += 1
if a % d == 0:
    d2 += 1
if a % lcm == 0:
    add += 1

print(total-d1-d2+add)
listh = list(map(int, input().split()))
#print(listh)
lista = [0]
count = 0
for n in range(1,N):
    if listh[n] > listh[n-1]:
        count = 0
        lista.append(count)
    else:
        count = count + 1
        lista.append(count) 
print(max(lista))        
        

### FIXED CODE ###

N = int(input())
listh = list(map(int, input().split()))
#print(listh)
lista = [0]
count = 0
for n in range(1,N):
    if listh[n] > listh[n-1]:
        count = 0
        lista.append(count)
    else:
        count = count + 1
        lista.append(count) 
#print(lista)        
print(max(lista))
n=list(map(int, input().strip().split()))

lis1=[]
for i in range(0,len(n)):
    for a in range(0,len(n)):
        if n[i]!=n[a]:
            z=(int(n[a])+int(n[i]))
            lis1.append(str(z))

minscore='9999999999'
for i in range(0,len(n)):
    if float(minscore)>float(lis1[i]):
        minscore=lis1[i]

print(minscore)



### FIXED CODE ###

try:
    n=list(map(int, input().strip().split()))
    lis1=[]
    for i in range(0,len(n)):
        for a in range(0,len(n)):
            if a!=i:
                z=(int(n[a])+int(n[i]))
                lis1.append(z)
            
    minscore='9999999999'
    for i in range(0,len(lis1)):
        if float(minscore)>float(lis1[i]):
            minscore=lis1[i]
    
    print(minscore)
    
except:
    print('')
x,y = list(map(int,input().split()))

mod = 10**9 + 7

# import math
# def comb(n,r):
#     return (math.factorial(n)//(math.factorial(n-r)*math.factorial(r)))

def comb(n,r,mod):
	'''
	return nCr
	O(min{n-r, r})
	'''
	a=1
	b=1
	r = min(r,n-r)
	for i in range(r):
		a = a*(n-i)%mod
		b = b*(i+1)%mod
	return a*pow(b,mod-2,mod)%mod

if (x+y)%3!=0:
    print(0)
    exit()
else:
    n = (2/3)*x - (1/3)*y
    m = (2/3)*y - (1/3)*x
    if n>=0 and m>=0:
        print(comb(int(n+m),int(m),mod))
        exit()
    else:
        print(0)
        exit()

### FIXED CODE ###

n = int(input())

xy = [list(map(int,input().split())) for _ in range(n)]

# print(xy)

import itertools
import numpy as np

def calc_distance(z1,z2):
    v1 = np.array(z1)
    v2 = np.array(z2)
    d = np.linalg.norm(v1-v2,2)
    return d


table = np.zeros((n,n))
for i in range(n):
    for j in range(n):
        if i==j:
            pass
        else:
            z1 = xy[i]
            z2 = xy[j]
            table[i,j] = calc_distance(z1,z2)
        
    
# print(table)

wa = 0
count = 0
for i in itertools.permutations(range(1,n+1)):
    # print(i)
    count += 1
    for j in range(len(i)-1):
        d = table[i[j]-1,i[j+1]-1]
        # print(d)
        wa += d

ans = wa/count
# print(wa)
# print(count)
print(ans)
n=int(input())
A=list(map(int,input().split()))
S=sum(A)//2
cnt=0
i=0
while cnt<S:
    cnt+=A[i]
    i+=1
ans1=abs(cnt-sum(A[i:]))
ans2=abs(cnt+A[i]-sum(A[i+1:]))
print(min(ans1,ans2))

### FIXED CODE ###

from itertools import accumulate
import sys
n=int(input())
A=list(map(int,input().split()))
S=sum(A)/2
B=list(accumulate(A))

for i in range(n):
    B[i]-=S
    if B[i]<0:
        continue
    elif B[i]==0:
        print(0)
        sys.exit()
    else:
        if i==0:
            print(A[0]-A[1:])
        elif i>0 and i<n-1:
            a=abs(sum(A[:i])-sum(A[i:]))
            b=abs(sum(A[:i+1])-sum(A[i+1:]))
            print(min(a,b))
        else:
            print(A[n-1]-sum(A[:n-1]))
        sys.exit()
a = str(input())

if a == 'A':
    print('T')
elif a == 'T'
    print('A')
elif a == 'G':
    print('C')
elif a == 'C':
    print('G')

### FIXED CODE ###

a = str(input())

if a == 'A':
    print('T')
elif a == 'T':
    print('A')
elif a == 'G':
    print('C')
elif a == 'C':
    print('G')
X = input()
stack = []
for s in X:
  if not stack:
    stack.append(s)
  	continue
  if s == 'T' and stack[-1] == 'S':
    stack.pop()
print(len(stack))

### FIXED CODE ###

def resolve():
    X = input()
    stack = []
    for s in X:
        if not stack:
            stack.append(s)
            continue
        if s == 'T' and stack[-1] == 'S':
            stack.pop()
        else:
            stack.append(s)
    print(len(stack))

resolve()
N,M = list(map(int,input().split()))
ps = []
for i in range(M):
    ps.append(list(map(str,input().split())))
    
import sys

if M == 0:
    print(0,0)
    sys.exit()

ps_new = sorted(ps , key=lambda x: x[0])
toi = []

for i in range(M):
    toi.append(ps[i][0])
    
toi2 = toi[0]
toi3 = [toi2]

for i in range(M):
    if toi2 != toi[i]:
        toi3.append(toi[i])
        toi2 = toi[i]
toi3.append("0")

toi = ps_new[0][0]
j = 0
count1 = 0
count2 = 0
count3 = 0

for i in range(M):
    if toi == ps[i][0]:
        count2 += 1
        if count2 == 1:
            shokai = i
        if ps_new[i][1] == "AC":
            count1 += 1
            j += 1
            toi = toi3[j]
            count2 = 0
            count3 = count3 + (i-shokai)
    elif toi != ps[i][0] and ps_new[i][1] == "AC":
        count+=1
print(count1,count3)

### FIXED CODE ###

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

AC = [0]*N
WA = [0]*N
miss = 0

for i in range(M):
    p,S = list(map(str,input().split()))
    p = int(p)-1
    
    if S == 'AC' and AC[p] == 0:
        AC[p] = 1
        miss += WA[p]
        
    WA[p] += 1
        
print(sum(AC),miss)
a,b,c,d=map(int, input().split())
x=a+b-c-d
if x>0:
  print(Left)
elif x<0:
  print(Right)
else:
  print(Balanced)

### FIXED CODE ###

a,b,c,d=map(int, input().split())
x=a+b-c-d
if x>0:
  s="Left"
elif x<0:
  s="Right"
else:
  s="Balanced"
print(s)
a, b = input().split('')

if a == "9" or b == "9":
    print("Yes")
else:
    print("No")


### FIXED CODE ###

l = list(input())
for i in l:
    if i == "9":
        print("Yes")
        break
else:
    print("No")
def is_much_money(num_of_coin, yen):
  if num_of_coin * 500 >= yen:
    return "Yes"
  else:
    return "No"

if __name__ == "__main__":
    num_of_coin, yen = int(input().split())
    judgement = is_much_mony(num_of_coin, yen)
    print(judgement)

### FIXED CODE ###

def is_much_money(num_of_coin, yen):
  if num_of_coin * 500 >= yen:
    return "Yes"
  else:
    return "No"
 
if __name__ == "__main__":
    num_of_coin, yen = input().split()
    judgement = is_much_money(int(num_of_coin), int(yen))
    print(judgement)
A = int(input("X=?"))
B = int(input("Y=?"))
C = int(input("Z=?"))
x = A
A = B
B = x
x = A
A = C
C = x

print(' '.join(map(str, [A,B,C])))

### FIXED CODE ###

A, B, C = map(int, input().split())
x = A
A = B
B = x
x = A
A = C
C = x

print(' '.join(map(str, [A,B,C])))
if __name__ == '__main__':
	a, b, c = input().split()
	a, b, c = int(a), int(b), int(c)

	ans = [a, b, c].sorted()
	print(ans[0], ans[1], ans[2])


### FIXED CODE ###

if __name__ == '__main__':
	a, b, c = input().split()
	a, b, c = int(a), int(b), int(c)

	ans = sorted([a, b, c])
	print(ans[0], ans[1], ans[2])
n = int(raw_input())
l = map(int, raw_input().split())
ans = 0
i = 0
while i < n:
    if i+1 == l[i]:
        ans += 1
        if i+2 == l[i+1]:
            i += 1
    i += 1
print ans


### FIXED CODE ###

n = int(raw_input())
l = map(int, raw_input().split())
ans = 0
i = 0
while i < n:
    if i+1 == l[i]:
        ans += 1
        if i+1 < n and i+2 == l[i+1]:
            i += 1
    i += 1
print ans
import decimal
N = int(input())
A = list(input().split())

ans = 1
for i in range(len(A)):
    ans *= decimal.Decimal(A[i])
    
if(len(str(ans)) >= 18):
    print(-1)
else:
    print(ans)

### FIXED CODE ###

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

aa = set(A)
ans = 1
for i in range(len(A)):
    if(ans > 10**18):
        if(0 not in aa):
            ans = -1
            break
        else:
            ans = 0
    ans *= A[i]

if(ans > 10**18):
    print(-1)
else:
    print(ans)
import numpy as np

n = int(input())
a = np.array(input().split(), dtype=np.int)
b = np.array(input().split(), dtype=np.int)
flag = False
mask = ~np.identity(n, dtype=np.bool)
for i in np.where(a <= b)[0]:
  if np.all(a[mask[i]].sort() <= b[mask[i]].sort()):
    flag = True
    break
if flag:
  print('Yes')
else:
  print('No')


### FIXED CODE ###

import numpy as np

n = int(input())
a = np.array(input().split(), dtype=np.int)
b = np.array(input().split(), dtype=np.int)
arg = np.argsort(b)
a = a[arg]
b = b[arg]
arg = np.argsort(a)
if np.all(a[arg] <= b):
  i = arg[0]
  cycle_size = 1
  while i != 0:
    i = arg[i]
    cycle_size += 1
  if cycle_size == n and np.all(a[arg[1:]] > b[:-1]):
    print('No')
  else:
    print('Yes')
else:
  print('No')
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    N,X,M = map(int,input().split())

    A = [-1 for i in range(M)]
    A[0] = X

    for i in range(1,M):
        temp = A[i-1] ** 2
        temp %= M
        if temp in A:
            start = A.index(temp)
            end = i - 1
            break
        A[i] = temp

    L = end - start + 1
    straight = [0 for i in range(start)]
    loop = [0 for i in range(L)]

    for i in range(start):
        straight[i] = straight[i-1] + A[i]

    for i in range(L):
        loop[i] = loop[i-1] + A[start+i]

    res = 0

    if N >= start:
        res += straight[-1]
        N -= start
    else:
        res += straight[N-1]
        N = 0

    res += (N // L) * loop[-1]

    if N % L != 0:
        res += loop[N % L - 1]

    print(res)



main()


### FIXED CODE ###

import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit,i8


@njit(i8[:](i8,i8[:],i8[:],i8,i8,i8))
def SerchLoop(M,A,cnt,start,end,temp):
    for i in range(1,M+2):
        temp = A[i-1] ** 2
        temp %= M
        if cnt[temp] != 0:
            start = cnt[temp]
            end = i - 1
            break
        A[i] = temp
        cnt[temp] = i
    return np.append(np.append(A,start),end)


def main():
    N,X,M = map(int,input().split())

    A = [-1 for i in range(M+2)]
    A[0] = X
    A = np.array(A)

    start = -1
    end = -1

    cnt = [0 for i in range(M)]
    cnt[X] = 0
    cnt = np.array(cnt)

    C = SerchLoop(M,A,cnt,start,end,0)
    A = C[:-2]
    start = C[-2]
    end = C[-1]

    L = end - start + 1

    if start == -1:
        straight = [0 for i in range(N)]
        for i in range(N):
            straight[i] = straight[i-1] + A[i]
        res = straight[-1]
    elif start == 0:
        loop = [0 for i in range(L)]
        for i in range(L):
            loop[i] = loop[i-1] + A[start+i]
        res = (N // L) * loop[-1]
        if N % L != 0:
            res += loop[N % L - 1]
    else:
        straight = [0 for i in range(start)]
        for i in range(start):
            straight[i] = straight[i-1] + A[i]
        loop = [0 for i in range(L)]
        for i in range(L):
            loop[i] = loop[i-1] + A[start+i]
        if N >= start:
            res = straight[-1]
            N -= start
        else:
            res = straight[N-1]
            N = 0
        res += (N // L) * loop[-1]
        if N % L != 0:
            res += loop[N % L - 1]

    print(res)



main()
n = int(input()) 
str_list = [input() for _ in range(n)]


a=0
b=0
c=0                
d=0                
                
for num in range(1, n):
    if str_list[num] == 'AC':
    	a += 1
    elif str_list[num] == 'WA':
    	b += 1
    elif str_list[num] == 'TLE':
    	c +=1
    else str_list[num] == 'RE':
    	d +=1
    		continue;

print('AC x'+ a)
print('WA x'+ b)
print('TLE x'+ c)
print('RE x'+ d)


### FIXED CODE ###

n = int(input())
str_list = [input() for _ in range(n)]


a=0
b=0
c=0                
d=0                
                
for i in range(n):
    if str_list[i] == 'AC':
    	a += 1
    elif str_list[i] == 'WA':
    	b += 1
    elif str_list[i] == 'TLE':
    	c +=1
    else :
    	d +=1

print('AC x '+ str(a))
print('WA x '+ str(b))
print('TLE x '+ str(c))
print('RE x '+ str(d))