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

from collections import deque


# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs():
    # すべての点を INF で初期化
    #d = [[10 ** 12] * w for i in range(h)]
    d = []
    for i in range(h):
        d.append([10 ** 12] * w)

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        if p[0] == gx and p[1] == gy:
            break
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and d[nx][ny] == 10 ** 12:
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]


h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]

d = [[False] * w for i in range(h)]
ans = 0
for sx in range(h):
    for sy in range(w):
        if maze[sx][sy] == ".":
            d[sx][sy] = True
            for gx in range(h):
                for gy in range(w):
                    if maze[gx][gy] == ".":
                        if d[gx][gy]:
                            continue
                        ans = max(ans, bfs())

print(ans)


### FIXED CODE ###

from collections import deque


# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs():
    # すべての点を INF で初期化
    #d = [[10 ** 12] * w for i in range(h)]
    d = []
    for i in range(h):
        d.append([10 ** 12] * w)

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        if p[0] == gx and p[1] == gy:
            break
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and d[nx][ny] == 10 ** 12:
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]


h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]

count = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            count += 1
if count == 400:
    print(38)
    exit()

ans = 0
for sx in range(h):
    for sy in range(w):
        if maze[sx][sy] == ".":
            for gx in range(h):
                for gy in range(w):
                    if sx == gx and sy == gy:
                        continue
                    if maze[gx][gy] == ".":
                        ans = max(ans, bfs())

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



def putmx(lis):
  ret=[]
  mx=max(lis)
  for i in range(len(lis)):
    if mx==lis[i]:
      ret.append(i)
  return ret

h,w,m=map(int,input().split())
#inp=[(random.randrange(1,h+1),random.randrange(1,w+1)) for i in range(m)]
hb=[0]*h
wb=[0]*w
bmb=[]
for i in range(m):
  hh,ww=map(int,input().split())
  hh-=1
  ww-=1
  bmb.append([hh,ww])
  hb[hh]+=1
  wb[ww]+=1

hmx=putmx(hb)
wmx=putmx(wb)
mhb=max(hb)
mwb=max(wb)
#print(hb,wb,hmx,wmx)
fl=False
for i in hmx:
  for j in wmx:
    if not [i,j] in bmb:
      print(mhb+mwb)
      fl=True
      break
  if fl:
    break
else:
  print(mhb+mwb-1)



### FIXED CODE ###

#import random

def putmx(lis,mx):
  ret=[]
  for (i,j) in zip(range(len(lis)),lis):
    if j==mx:
      ret.append(i)
  return ret
  

h,w,m=map(int,input().split())
hb=[0]*h
wb=[0]*w
bmb=[]
for i in range(h):
  bmb.append({-1})
for i in range(m):
  hh,ww=map(int,input().split())
  hh-=1
  ww-=1
  bmb[hh].add(ww)
  hb[hh]+=1
  wb[ww]+=1
mhb=max(hb)
mwb=max(wb)
hmx=putmx(hb,mhb)
wmx=set(putmx(wb,mwb))

#print(hb,wb,hmx,wmx)
fl=False
for i in hmx:
  if wmx|bmb[i]!=bmb[i]:
    print(mhb+mwb)
    break
else:
  print(mhb+mwb-1)

#print(hmx,wmx,bmb)
### BUGGY CODE ###

import numpy as np

N = int(input())
A = np.array(list(map(int, input().split())))
Q = int(input())
bc = [list(map(int, input().split())) for _ in range(Q)]

for i in range(Q):
    A[A==bc[i][0]] = bc[i][1]
    print(sum(A))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
bc = [list(map(int, input().split())) for _ in range(Q)]

mem = [0]*(10**5)

sum = 0
for i in A:
    mem[i-1] += 1
    sum += i

for q in range(Q):
    b = bc[q][0]
    if mem[b-1] != 0:
        c = bc[q][1]
        num = mem[b-1]
        mem[c-1] += num
        mem[b-1] = 0
        sum = sum - num*b + num*c
    print(sum)
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0

positions = {}
positions['R'] = [i for i in range(n) if s[i]=='R']
positions['G'] = [i for i in range(n) if s[i]=='G']
positions['B'] = [i for i in range(n) if s[i]=='B']
positions['RG'] = sorted(positions['R']+positions['G'])
positions['RB'] = sorted(positions['R']+positions['B'])
positions['GB'] = sorted(positions['G']+positions['B'])

for p1 in range(n-3):
    if s[p1] == 'R':
        pos2 = [p for p in positions['GB'] if p > p1]
    elif s[p1] == 'G':
        pos2 = [p for p in positions['RB'] if p > p1]
    else:
        pos2 = [p for p in positions['RG'] if p > p1]

    for p2 in pos2:
        if s[p1] == 'R' and s[p2] == 'G':
            pos3 = [p for p in positions['B'] if p > p2]
        elif s[p1] == 'R' and s[p2] == 'B':
            pos3 = [p for p in positions['G'] if p > p2]
        elif s[p1] == 'G' and s[p2] == 'B':
            pos3 = [p for p in positions['R'] if p > p2]
        elif s[p1] == 'G' and s[p2] == 'R':
            pos3 = [p for p in positions['B'] if p > p2]
        elif s[p1] == 'B' and s[p2] == 'R':
            pos3 = [p for p in positions['G'] if p > p2]
        elif s[p1] == 'B' and s[p2] == 'G':
            pos3 = [p for p in positions['R'] if p > p2]
        
        for p3 in pos3:             
            if (p1-p2 != p2-p3):
                ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
dup = 0
r = s.count('R')
g = s.count('G')
b = s.count('B')

for i in range(n):
    for j in range(i+1, n):
        k = 2*j - i
        if k < n:
            #print(i,j,k)
            if (s[i] != s[j]) and (s[j] != s[k]) and (s[i] != s[k]):
                #print(s[i], s[j], s[k])
                dup += 1
print(r*g*b - dup)
### BUGGY CODE ###

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


A=[int(i) for i in (input().split(" "))]



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

for b,c in BC:
    count=0
    A.sort()
    for i in range(b):
        if c<A[i]:
            break
        else:
            A[i]=c
    
suma=0
for i in A:
    suma+=i

print(suma)

### FIXED CODE ###


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


A=[int(i) for i in (input().split(" "))]

A.sort()

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

BC.sort(key=lambda x:x[1],reverse=True)

for b,c in BC:
    A.extend([c]*b)
    if len(A)>2*N:
        break

A.sort(reverse=True)
suma=0
#for i in A:
#    suma+=i

print(sum(A[:N]))
### BUGGY CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
b = []
for i in range(n):
    b = a.copy()
    b.pop(i)
    print(max(b))

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
b = sorted(a.copy(), reverse=True)
for i in range(n):
    if a[i] == b[0]:
        print(b[1])
    else:
        print(b[0])
### BUGGY CODE ###

import copy

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

INF = 10 ** 8


def rec(rest_ope, now_d, now_hand):

    if rest_ope == 0:
        return sum(now_hand)

    max_price = -INF

    if len(now_d) > 0:
        left_d = copy.copy(now_d)
        left_hand = copy.copy(now_hand)
        left_hand.append(left_d.pop(0))

        max_price = max(max_price, rec(rest_ope - 1, left_d, left_hand))

        right_d = copy.copy(now_d)
        right_hand = copy.copy(now_hand)
        right_hand.append(right_d.pop(-1))

        max_price = max(max_price, rec(rest_ope - 1, right_d, right_hand))

    if len(now_hand) > 0:
        drop_hand = copy.copy(now_hand)
        drop_hand.pop(drop_hand.index(min(drop_hand)))  # 最小値を削除

        max_price = max(max_price, rec(rest_ope - 1, now_d, drop_hand))

    # do nothing
    max_price = max(max_price, rec(rest_ope - 1, now_d, now_hand))

    return max_price


print(rec(K, V, []))


### FIXED CODE ###

import copy

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

INF = 10 ** 8


# mode 0: can pop left, pop right, drop
#      1: can pop right, drop
#      2: can drop
#      3: can not do anything
def rec(rest_ope, now_d, now_hand, mode):

    if rest_ope == 0:
        return sum(now_hand)

    max_price = -INF

    if len(now_d) > 0:
        if mode == 0:
            left_d = copy.copy(now_d)
            left_hand = copy.copy(now_hand)
            left_hand.append(left_d.pop(0))

            max_price = max(max_price, rec(rest_ope - 1, left_d, left_hand, 0))

        if mode <= 1:
            right_d = copy.copy(now_d)
            right_hand = copy.copy(now_hand)
            right_hand.append(right_d.pop(-1))

            max_price = max(max_price, rec(rest_ope - 1, right_d, right_hand, 1))

    if len(now_hand) > 0:
        if mode <= 2:
            drop_hand = copy.copy(now_hand)
            drop_hand.pop(drop_hand.index(min(drop_hand)))  # 最小値を削除

            max_price = max(max_price, rec(rest_ope - 1, now_d, drop_hand, 2))

    # do nothing
    max_price = max(max_price, rec(rest_ope - 1, now_d, now_hand, 3))

    return max_price


print(rec(K, V, [], 0))
### BUGGY CODE ###

N = int(input())
def divisor(num):
    L = []
    K = 0
    v = 0
    for i in range(num):
        if num%(i+1) == 0:
            L.append(i+1)
            K += 1
        else:
            continue
    if K%2 == 0:
        v = L[int(K/2)] + L[int(K/2-1)]
    elif K%2 == 1:
        v = 2*L[K/2]
    return v
print(divisor(N)-2)

### FIXED CODE ###

import math
N = int(input())
for i in range(int(math.sqrt(N)), 0 , -1):
    if N%i == 0:
        ans = i+(N//i)-2
        print(ans)
        break
### BUGGY CODE ###

b, c = map(int, input().split())
ans = 1
while b <= c:
	ans *= b
	b += 1

if ans > 0:
	print("Positive")
elif ans < 0:
	print("Negative")
else:
	print("Zero")


### FIXED CODE ###

# def makelist(n, m):
# 	return [[0 for i in range(m)] for j in range(n)]

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


b, c = map(int, input().split())
ans = 1

if b == 0 or c == 0 or (b < 0 and c > 0):
	ans = 0
elif b > 0 and c > 0:
	ans = 1
else:
	tmp = abs(b) - abs(c)
	if tmp % 2 == 0:
		ans = -1
	else:
		ans = 1

if ans > 0:
	print("Positive")
elif ans < 0:
	print("Negative")
else:
	print("Zero")
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
ans1 = 1
B = []
for i in range(K):
  ans1 = ans1*A[i]
B.append(ans1)
for i in range(N-K):
  ans1 = ans1*A[K+i]/A[i]
  B.append(ans1)
for i in range(N-K):
  if B[i] < B[i+1]:
    print('Yes')
  else:
    print('No')
  

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
for i in range(N-K):
  if A[i] < A[K+i]:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000000)

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

A = [-1]*M
B = [-1]*M
C = [-1]*M
back_edges = [[] for _ in range(N)]
forward_edges = [[] for _ in range(N)]
fb = [0]*N
past = set()
availables = set()

for edge in range(M):
    a, b, c = map(int, input().split())
    A[edge] = a-1
    B[edge] = b-1
    C[edge] = c-P
    forward_edges[a-1].append(edge)
    back_edges[b-1].append(edge)

def forward(node):
    if node in past:
        return
    availables.add(node)
    edges = forward_edges[node]
    past.add(node)
    for edge in edges:
        forward(B[edge])
    past.discard(node)

forward(0)

def back(node):
    edges = back_edges[node]
    past.add(node)
    coin = -float('inf') if node != 0 else 0
    for edge in edges:
        a = A[edge]
        if a not in availables:
            continue
        c = C[edge]
        if a in past:
            if fb[a] < c + fb[node]:
                print(-1)
                sys.exit()
                continue
        fb[a] = c + fb[node]
        coin = max(back(a)+c, coin)
    past.discard(node)
    return coin

ans = back(N-1)
ans = 0 if ans < 0 else ans
print(ans)

### FIXED CODE ###

import sys
import time
from queue import Queue
limit_time = time.time() + 1.70
input = sys.stdin.readline
sys.setrecursionlimit(1000000000)

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

A = [-1]*M
B = [-1]*M
C = [-1]*M
nodes_edges = [[] for _ in range(N)]
rev_nodes_edges = [[] for _ in range(N)]
coin = [-float('inf')]*N
coin[0] = 0
availables = set()

for edge in range(M):
    a, b, c = map(int, input().split())
    A[edge] = a-1
    B[edge] = b-1
    C[edge] = c-P
    nodes_edges[a-1].append(edge)
    rev_nodes_edges[b-1].append(edge)

def cut_graph(node):
    edges = rev_nodes_edges[node]
    availables.add(node)
    for edge in edges:
        prev = A[edge]
        if prev in availables:
            continue
        cut_graph(prev)

cut_graph(N-1)
q = Queue()
q.put(0)
count = 0
limit = M*(1+len(availables))
while not q.empty():
    if time.time() >= limit_time:
        print(-1)
        break
    node = q.get()
    edges = nodes_edges[node]
    for edge in edges:
        nxt = B[edge]
        if nxt not in availables:
            continue
        new_coin = C[edge]+coin[node]
        if new_coin > coin[nxt]:
            coin[nxt] = new_coin
            q.put(nxt)
    count += 1
else:
    ans = coin[N-1]
    ans = 0 if ans < 0 else ans
    print(ans)
### BUGGY CODE ###

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def invmod(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


n, k = map(int, input().split())
k_ = k - 2
a = sorted([int(i) for i in input().split(" ")])
c = 10**9 + 7
b_pro = [1 for i in range(n)]
inv_pro = [1 for i in range(n)]
for i in range(2,n+1):
    b_pro[i-1] = b_pro[i-2]*i % c
    inv_pro[i-1] = inv_pro[i-2] * invmod(i, c) % c
if k_ == 0:
    comb = [1 for i in range(n)]
else:
    comb = [1] + [b_pro[i]*inv_pro[i-k_]%c*inv_pro[k_-1]%c for i in range(k_, n-2)]
ans = 0
for i in range(n-1, max(-1, n-k-2), -1):
    for j in range(i-k+2):
        #print("ij", i, j)
        tmp = a[i] - a[j]
        
        ans += tmp*comb[i-1-j-k_] % c
        #print("comb_temp", comb[i-2-j-k_], tmp)
        #print("ans", ans)
print(ans%c)

### FIXED CODE ###

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def invmod(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


n, k = map(int, input().split())
k_ = k - 1
a = sorted([int(i) for i in input().split(" ")])
c = 10**9 + 7

comb = [1 for i in range(n-k_)]
for i in range(1, n-k_):
    comb[i] = comb[i-1] * (k_+i) * invmod(i, c) % c
ans = 0
for i in range(k_, n):       
        ans += a[i]*comb[i-k_] % c
        #print("comb_temp", comb[i-2-j-k_], tmp)
        #print("ans", ans)
for i in range(n-k+1):
    ans -= a[i]*comb[n-k-i]
    ans = ans % c
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = []
for i in range(n):
  ans.append(a.index(i+1)+1)
print(' '.join(map(str, ans)))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = [0]*n
for i in range(n):
  ans[a[i]-1] = i + 1
print(*ans)
### BUGGY CODE ###

import sys,math,copy
input = sys.stdin.readline
S = input().strip()
N = len(S)

dp = [[0] * 13 for _ in range(2)]
dp[0][0] = 1
mod = 1
for i, s in enumerate(S[::-1], start=1):
    n = i % 2
    if s == '?':
        for d in range(10):
            m = (d * mod) % 13
            for pm in range(13):
                dp[n][(pm+m)%13] += dp[n-1][pm]

    else:
        m = (int(s) * mod) % 13
        for pm in range(13):
            dp[n][(pm+m)%13] += dp[n-1][pm]
    dp[n-1] = [0] * 13
    mod = (mod * 10) % 13
print(dp[N%2][5] % (10 ** 9 + 7))

### FIXED CODE ###

import sys,math,copy

def main():
    # import numpy as np
    input = sys.stdin.readline
    S = ''.join(reversed(input().strip()))

    # dp = np.zeros((13), dtype=int)
    # dp_ = np.zeros((13), dtype=int)
    dp = [0] * 13
    dp_ = [0] * 13
    mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
    list10 = list(range(10))
    list13 = list(range(13))
    divisor = 10 ** 9 + 7
    dp_[0] = 1
    mul = 1
    for i in range(len(S)):
        s = S[i]
        if s == '?':
            for d in list10:
                m = mod13_list[(d * mul)]
                for pm in list13:
                    dp[mod13_list[(pm+m)]] += dp_[pm]

        else:
            si = int(s)
            m = mod13_list[(si * mul)]
            for pm in list13:
                dp[mod13_list[(pm+m)]] = dp_[pm]

        # dp_ = dp % divisor
        # dp = dp * 0 # np.zeros((13), dtype=int)
        for j in list13:
            dp_[j] = dp[j] % divisor
            dp[j] = 0
        mul = mod13_list[(mul * 10)]
    print(dp_[5])

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

from collections import deque
from itertools import islice
def main():
    n = int(input())
    A = deque(list(map(int, input().split())))
    ans = [0] * n
    for i in range(n):
        ans[i] = sum(islice(A, 0, n, 2)) - sum(islice(A, 1, n, 2))
        A.rotate(-1)
    print(' '.join(list(map(str, ans))))

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    A = list(map(int, input().split()))
    A += A
    ans = [0] * n
    s1 = sum(A[:n - 1:2])
    s2 = sum(A[1:n:2])
    for i in range(n):
        if i % 2 == 0:
            s1 += A[i + n - 1]
            ans[i] = s1 - s2
            s1 -= A[i]
        else:
            s2 += A[i + n - 1]
            ans[i] = s2 - s1
            s2 -= A[i]
    print(' '.join(list(map(str, ans))))

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

def gcd(x,y):
    if y == 0:
        return x
    else:
        return gcd(y,x%y)
n = int(input())
i = 1
j = 1
k = 1
ans = 0
while i < n+1:
    j = 1
    while j < n+1:
        k = 1
        while k < n+1:
            ans += gcd(i,gcd(j,k))
            k += 1
        j += 1
    i += 1
print(ans)

### FIXED CODE ###

def gcd(x,y):
    if y == 0:
        return x
    elif x == 1 or y == 1:
        return 1
    else:
        return gcd(y,x%y)

G = []
i,j = 1,1
while i < 201:
    j = 1
    g0 = []
    while j < 201:
        g0.append(gcd(i,j))
        j += 1
    g0 = tuple(g0)
    G.append(g0)
    i += 1
n = int(input())
i = 1
j = 1
k = 1
ans = 0
while i < n+1:
    j = 1
    while j < n+1:
        k = 1
        p = G[i-1][j-1]
        while k < n+1:
            ans += G[k-1][p-1]
            k += 1
        j += 1
    i += 1
print(ans)
### BUGGY CODE ###


def resolve():
    def COMinit(n, MOD):
        fact = [1, 1]
        fact_inv = [1, 1]
        inv = [0, 1]
        for i in range(2, n + 1):
            fact.append((fact[-1] * i) % MOD)
            inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
            fact_inv.append((fact_inv[-1] * inv[i]) % MOD)
        return fact, fact_inv

    # 二項係数計算
    def Combination(n, k, MOD=10 ** 9 + 7):
        # fac, finv = COMinit(n, MOD)
        if n < k: return 0
        if n < 0 or k < 0: return 0
        ret = fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
        return ret

    MOD = 10 ** 9 + 7
    K = int(input())
    S = input()
    N = len(S)

    fac, finv = COMinit(N + K, MOD)
    pow25 = 1
    pow26 = pow(26, K, MOD)
    inv26 = pow(26, MOD - 2, MOD)
    ans = 0
    for i in range(K + 1):
        ans += pow25 * Combination(N - 1 + i, N - 1) * pow26
        ans %= MOD
        pow25 = pow25 * 25 % MOD
        pow26 = pow26 * inv26 % MOD

    print(ans)

if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    MOD = 10 ** 9 + 7
    def COMinit(n, MOD):
        fact = [1, 1]
        fact_inv = [1, 1]
        inv = [0, 1]
        for i in range(2, n + 1):
            fact.append((fact[-1] * i) % MOD)
            inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
            fact_inv.append((fact_inv[-1] * inv[i]) % MOD)
        return fact, fact_inv
 
    # 二項係数計算
    def Combination(n, k, MOD=10 ** 9 + 7):
        # fac, finv = COMinit(n, MOD)
        if n < k: return 0
        if n < 0 or k < 0: return 0
        ret = fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
        return ret
 
    K = int(input())
    S = input()
    N = len(S)
 
    fac, finv = COMinit(N + K, MOD)
    v = 1
    ans = 0
    for i in range(K + 1):
        ans += Combination(N + K, i) * v
        ans %= MOD
        v *= 25
        v %= MOD
    print(ans)
    
if __name__ == "__main__":
    resolve()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
num,product = map(int,input().split())

cnt = 1
gcd = 1
while(True):
    cnt += 1
    calc = cnt ** num
    if product % calc == 0:
        gcd = cnt
    elif calc > product:
        break
    else:
        continue
print(gcd)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import defaultdict
from math import sqrt,floor
num,product = map(int,input().split())
cnt = int(sqrt(product) + 2)
dd = defaultdict(int)

for i in range(2,cnt):
    if product % i == 0:
        a = 0
        while product % i == 0:
            a += 1
            product = product // i
        dd[i] = a
if product != 1:
    dd[product] =  1
ans = 1
for p,n in dd.items():
    ans *= pow(p,floor(n/num))
print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
Q=int(input())
BC=[]
#for i in range(Q):
#    BC.append(list(map(int,input().split())))
A_sum=sum(A)
A_count=[]
for i in range(100001):
    A_count.append(A.count(i))
for i in range(Q):
    B,C=(map(int,input().split()))
    A_sum+=(C-B)*A_count[B]
    A_count[C]+=A_count[B]
    A_count[B]=0
    print(A_sum)

### FIXED CODE ###

from collections import Counter

N=int(input())
A=list(map(int,input().split()))
Q=int(input())
#BC=[]
#for i in range(Q):
#    BC.append(list(map(int,input().split())))
A_sum=sum(A)
A_count=Counter(A)

for i in range(Q):
    B,C=(map(int,input().split()))
    A_sum+=(C-B)*A_count[B]
    A_count[C]+=A_count[B]
    A_count[B]=0
    print(A_sum)