Harryxun/stf_run huggingface dataset:
import sys
import itertools
input = sys.stdin.readline


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


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


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


def root(P, C, a):
    if P[a] == a:
        return a
    r = root(P, C, P[a])
    P[a] = r
    C[a] = C[r]
    return r


def main():
    N, M = read_values()
    V = [read_list() for _ in range(M)]
    P = [i for i in range(N)]
    C = [1] * N
    res = [N * (N - 1) // 2] * M
    total = 0
    for i in range(M - 2, -1, -1):
        a, b = V[i + 1]
        a -= 1
        b -= 1

        ra = root(P, C, a)
        rb = root(P, C, b)
        if ra == rb:
            res[i] -= total
            continue

        P[ra] = rb
        total += C[ra] * C[rb]
        C[ra] += C[rb]
        C[rb] = C[ra]
        res[i] -= total

    print("\n".join(map(str,res)))
    

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import itertools
input = sys.stdin.readline


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


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


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


def root(P, C, a):
    if P[a] == a:
        return a
    r = a
    while P[r] != r:
        r = P[r] 
    
    P[a] = r
    C[a] = C[r]
    return r


def main():
    N, M = read_values()
    V = [read_list() for _ in range(M)]
    P = [i for i in range(N)]
    C = [1] * N
    res = [N * (N - 1) // 2] * M
    total = 0
    for i in range(M - 2, -1, -1):
        a, b = V[i + 1]
        a -= 1
        b -= 1

        ra = root(P, C, a)
        rb = root(P, C, b)
        if ra == rb:
            res[i] -= total
            continue

        P[ra] = rb
        total += C[ra] * C[rb]
        C[ra] += C[rb]
        C[rb] = C[ra]
        res[i] -= total

    print("\n".join(map(str, res)))
    

if __name__ == "__main__":
    main()
a, b, c = map(int, input().split())
 
    temp_a = a
    temp_b = b
    a = temp_b
    b = temp_a
    temp_c = c
    temp_a = a
    c = temp_a
    a = temp_c
    print(a, b, c)

### FIXED CODE ###

n = list(map(int,input().split()))
print(n[2],n[0],n[1])
from fractions import gcd
a,b,c,d = map(int,input().split())
cab = (b//c)-((a-1)//c)
dab = (b//d)-((a-1)//c)
lcm = int(c*d/gcd(c,d))
cdab = (b//lcm)-((a-1)//lcm)
print((b-a+1)-cab-cad+cdab)

### FIXED CODE ###

from fractions import gcd
A, B, C, D = map(int,input().split())
total = B - A + 1
divC = B//C - (A-1)//C
divD = B//D - (A-1)//D
lcm = int(C * D / gcd(C, D))
divCD = B//lcm - (A-1)//lcm
print(total - divC - divD + divCD)
N=int(input())
A=map(int,input().split())
B=map(int,input().split())
C=map(int,input().split())
s=0
for i in range(1,len(S)+1):
  s+=B[A[i-1]]
  if A[i]==A[i-1]+1:
    s+=C[i-1]
print(s)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
s=0
temp=""
for i in A:
  s+=B[i-1]
  if temp==i-1:
    s+=C[temp-1]
  temp=i
print(s)
# n*m?????????A??¨m*1??????????????????b??¨??????????¨????????????°??????

import numpy as np
n, m = map(int, input().split())

A = np.matrix([[0 for i in range(m)] for j in range(n)])
for i in range(n):
    A[i] = list(map(int, input().split()))

b = np.matrix([[0] for i in range(m)])
for i in range(m):
    b[i] = int(input())

c = np.matrix([[0] for i in range(n)])            #A??b

for i in range(n):
    print(c[i, 0])

### FIXED CODE ###

# n*m?????????A??¨m*1??????????????????b??¨??????????¨????????????°??????

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

A = [[0 for i in range(m)] for j in range(n)]
for i in range(n):
    A[i] = list(map(int, input().split()))

b = [[0] for i in range(m)]
for i in range(m):
    b[i][0] = int(input())

c = [[0] for i in range(n)]            #A??b
for i in range(n):
    for j in range(m):
        c[i][0] += A[i][j] * b[j][0]

for i in range(n):
    print(c[i][0])
N = int(input())

if N == 1 :
	print("Hello World")
else :
  	A = int(input())
    B = int(input())
    print(A + B)

### FIXED CODE ###

N = int(input())
if N == 1:
    print("Hello World")
else:
    A = int(input())
    B = int(input())
    print(A + B)
n = int(input())
p = [int(input()) for _ in range(n)]
pmin = min(i for i in p)

import math
print(math.ceil(n/pmin)+4)


### FIXED CODE ###

n = int(input())
transp = [int(input()) for _ in range(5)]
import math
print(math.ceil(n/min(transp))+4)
N = int(input())
X = list(map(int, input().split()))

cost = 0

for i in range(1, 101):
  cand = 0
  for x in X:
    cand += (x[i]-i)**2
  cost = min(cost, cand)

print(cost)

### FIXED CODE ###

N = int(input())
X = list(map(int, input().split()))
 
cost = 10**10
 
for i in range(1, 101):
  cand = sum([(x-i)**2 for x in X])
  cost = min(cost, cand)

print(cost)
S=input()
T=input()

a=0
for i in range(len(S)):
    if len(T)==len(S)+1:
        if S[i]==T[i]:
            a=1
        else:
            print('No')
            sys.exit()
    else:
        print('No')
        sys.exit()
if a==1:
    print('Yes')

### FIXED CODE ###

S=input()
T=input()

a=1
if len(T)==len(S)+1:
    for i in range(len(S)):
        if S[i]==T[i]:
            a=1
            if a==0:
                break
        
        else:
            a=0
            print('No')
            break
else:
    print('No')
if a==1:
    print('Yes')
class Combination(object):
        """参考: https://harigami.net/contents?id=5f169f85-5707-4137-87a5-f0068749d9bb"""
        __slots__ = ['mod', 'factorial', 'inverse']

        def __init__(self, max_val_arg: int = 10**6, mod: int = 10**9 + 7):
            fac, inv = [1], []
            fac_append, inv_append = fac.append, inv.append

            for i in range(1, max_val_arg + 1):
                fac_append(fac[-1] * i % mod)

            inv_append(pow(fac[-1], mod - 2, mod))

            for i in range(max_val_arg, 0, -1):
                inv_append((inv[-1] * i) % mod)

            self.mod, self.factorial, self.inverse = mod, fac, inv[::-1]

        def combination(self, n, r):
            if n < 0 or r < 0 or n < r:
                return 0
            return self.factorial[n] * self.inverse[r] * self.inverse[n - r] % self.mod

if not S%3==0:
    print(0)
    exit()
else:
    small = S//3
    s_elm = min(X,Y)
    if s_elm<small:
        print(0)
        exit()
    r = s_elm - small
    ans = Combination().combination(small, r)
    ans %= u
print(ans)

### FIXED CODE ###


import sys,itertools
def input():
    return sys.stdin.readline()[:-1]

X,Y = map(int,input().split(' '))
u = 10**9+7

S = X+Y

class Combination(object):
        """参考: https://harigami.net/contents?id=5f169f85-5707-4137-87a5-f0068749d9bb"""
        __slots__ = ['mod', 'factorial', 'inverse']

        def __init__(self, max_val_arg: int = 10**6, mod: int = 10**9 + 7):
            fac, inv = [1], []
            fac_append, inv_append = fac.append, inv.append

            for i in range(1, max_val_arg + 1):
                fac_append(fac[-1] * i % mod)

            inv_append(pow(fac[-1], mod - 2, mod))

            for i in range(max_val_arg, 0, -1):
                inv_append((inv[-1] * i) % mod)

            self.mod, self.factorial, self.inverse = mod, fac, inv[::-1]

        def combination(self, n, r):
            if n < 0 or r < 0 or n < r:
                return 0
            return self.factorial[n] * self.inverse[r] * self.inverse[n - r] % self.mod

if not S%3==0:
    print(0)
    exit()
else:
    small = S//3
    s_elm = min(X,Y)
    if s_elm<small:
        print(0)
        exit()
    r = s_elm - small
    ans = Combination().combination(small, r)
    ans %= u
print(ans)
# Disjoint Set: Union Find Trees
[p, rank] = [[], []]
[n, q] = list(map(int, input().split()))
w = [0 for i in range(n)]
path_c = [[] for i in range(n)]

def makeSet(x):
    global p, rank
    p.append(x)
    rank.append(0)

def findSet(x):
    global p
    if x != p[x]:
        p[x] = findSet(p[x])
    return p[x]

def link(x, y):
    global p, rank
    if rank[x] > rank[y]:
        p[y] = x
    else:
        p[x] = y
        if rank[x] == rank[y]:
            rank[y] += 1

def union(x, y):
    link(findSet(x), findSet(y))

def same(x, y):
    if findSet(x) == findSet(y):
        return 1
    else:
        return 0   

def relate(x, y, z):
    global w, path_c
    path_c[x].append((y, z))
    #print(w)
    if w[y] == 0:
        w[y] = w[x] + z
    else:
        update(x, y, z)
        #w[x] = w[y] - z
    #print("cost:", w[y])
    union(x, y)

def update(x, y, z):
    global w, path_c
    w[x] = w[y] - z
    for i in range(len(path_c[x])):
        update(path_c[x][i][0], x, path_c[x][i][1])


def diff(x, y):
    if same(x, y) == 1:
        global w
        return abs(w[y] - w[x])
        '''
        global d
        total = 0
        d = [0 for i in range(n)]
        d[x] = 1
        return cost(x, y, n, total)
        '''
    else:
        return "?"     

'''
print(p)
print(rank)
print(w)
print("\n")
'''

for i in range(n):
    makeSet(i)

#w = [0 for i in range(n)]

for i in range(q):
    data = list(map(int, input().split()))
    if data[0] == 0:
        relate(data[1], data[2], data[3])
    else:
        print(diff(data[1], data[2]))
    '''
    print("\n")
    print(p)
    print(rank)
    print(w)
    print("\n")
    '''


### FIXED CODE ###

# Disjoint Set: Union Find Tree
p = []
rank = []

def makeSet(x):
    global p, rank
    p.append(x)
    rank.append(0)

def findSet(x):
    global p
    if x != p[x]:
        p[x] = findSet(p[x])
    return p[x]

def link(x, y):
    global p, rank
    if rank[x] > rank[y]:
        p[y] = x
    else:
        p[x] = y
        if rank[x] == rank[y]:
            rank[y] += 1

def union(x, y):
    link(findSet(x), findSet(y))    

def same(x, y):
    if findSet(x) == findSet(y):
        return 1
    else:
        return 0   

[n, q] = list(map(int, input().split()))
for i in range(n):
    makeSet(i)

for i in range(q):
    [com, x, y] = list(map(int, input().split()))
    if com == 0:
        union(x, y)
    else:
        print(same(x, y))
s = input()
t = input()
ls = len(s)
lt = len(t)

ans = 0
for i in range(ls-lt+1):
  same = 0
  for j in range(lt):
    ind = i+lt
    if s[ind]==t[j]:
      same += 1
  ans = min(ans,min)
print(ans)

### FIXED CODE ###

s = input()
t = input()
ls = len(s)
lt = len(t)

ans = 0
for i in range(ls-lt+1):
  same = 0
  for j in range(lt):
    ind = i+j
    if s[ind]==t[j]:
      same += 1
  ans = max(ans,same)
print(lt-ans)
import numpy as np

N = int(input())
s = []
for i in range (N):
    word = input()
    word_lst = []
    for j in range (len(word)):
        word_lst.append(word[j])
    word_lst = np.sort(word_lst)
    words = ""
    for j in range (len(word_lst)):
        words += word_lst[j]
    s.append(words)
#print (s)

count = 0
for i in range (N):
    for j in range (i+1,N):
        #print (i,j)
        #print (s[i],s[j])
        if s[i] == s[j]:
            count += 1
print (count)

### FIXED CODE ###

import numpy as np

A,B = map(int,input().split())
ans = [A+B,A-B,A*B]
ans = np.sort(ans)
print (ans[-1])
6 5
4 7 10 6 5

### FIXED CODE ###

X,N = list(map(int,input().split()))
if N == 0:
    print(X)
else:
    P = list(map(int,input().split()))
    for i in range(100):
        if not X - i in P:
            a = X - i
            break
        if not X + i in P:
            a = X + i
            break
    print(a)
import sys
sys.setrecursionlimit(1000000)

N = int(input())
G = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    G[a].append([b, i])

ans = [None]*(N-1)
def rec(cur, color):
    cnt = 1
    for (to, j) in G[cur]:
        if cnt == color:
            cnt += 1
        ans[j] = cnt
        rec(to, cnt)
        cnt += 1

rec(0,0)
print(max(ans))
[print(a) for a in ans]

### FIXED CODE ###

S = input()

l = ["SUN","MON","TUE","WED","THU","FRI","SAT"]

print(7 - l.index(S))
from math import gcd

def lcm(x, y):
   lcm = (x*y)//gcd(x,y)
   return lcm

n = int(input())
ans1 = 1
for _ in range(n):
    t=int(input())
    ans1 = lcm(ans1, t)
print(ans1)

### FIXED CODE ###

from fractions import gcd

def lcm(x, y):
   lcm = (x*y)//gcd(x,y)
   return lcm

n = int(input())
ans1 = 1
for _ in range(n):
    t=int(input())
    ans1 = lcm(ans1, t)
print(ans1)
n=int(input())
s=list(input())
count=0
for i in range(n):
  if i<=48:
    if s[i]=='A' and s[i+1]=='B' and s[i+2]=='C':
      count+=1
    
print(count)

### FIXED CODE ###

k,x=map(int,input().split())
k=k*500
if k>=x:
  print('Yes')
else:
  print('No')
i = 1
while True:
  if raw_input() == 0:
    break
  pritn 'Case {number}: {input}'.format(number=i, input=raw_input())
  i += 1

### FIXED CODE ###

i = 1
while True:
  x = raw_input()
  if x == '0':
    break
  print 'Case {0}: {1}'.format(i, x)
  i += 1
N,Q = (int(i) for i in input().split())
hen = {}
value = [0] * N
flag = [0] * N
for i in range(0,N-1):
    a,b = (int(i) for i in input().split())
    if a in hen:
        hen[a].append(b)
    else:
        hen[a] = [b]
#print(hen)

def add(p,x):
    if p in hen:
        for i in hen[p]:
            value[i-1] = value[i-1] + x
            add(i,value[i-1])

for i in range(0,Q):
    p,x = (int(i) for i in input().split())
    value[p-1] = value[p-1] + x


add(1,value[0])
print(' '.join(map(str,value)))
    


### FIXED CODE ###

a = int(input())
s=input()
if a < 3200:
    print('red')
else:
    print(s)
if S == "ABC":
  return "ARC"
else:
  return "ABC"

### FIXED CODE ###

S = input()
if S == "ABC":
  print("ARC")
else:
  print("ABC")
S = input()
idx = 0
cnts = []
while idx < len(S):
    char = S[idx]
    cnt = 0
    while idx < len(S) and S[idx] == char:
        idx += 1
        cnt += 1
    cnts.append(cnt)
if len(cnts) <= 2:
    print(max(cnts))
    quit()
ans = (len(S) + 1) // 2
for i in range(len(cnts) - 2):
    ans = max(ans, min(cnts[i] + cnts[i + 1], cnts[i + 1] + cnts[i + 2]))
ans = max(ans, max(cnts))

flips = []
for i in range(len(cnts) - 1):
    flips.append((cnts[i] + cnts[i + 1], i))
flips.sort()

from bisect import bisect_left
left, right = (len(S) + 1) // 2, len(S)
while left + 1 < right:
    mid = (left + right) // 2
    _, mid_idx = flips[bisect_left(flips, (mid, -1))]
    ret = [False] * (len(cnts))
    for _, idx in flips[mid_idx:]:
        ret[idx] = ret[idx + 1] = True
    if all(x for x in ret):
        left = mid
    else:
        right = mid
ans = max(left, ans)
print(ans)


### FIXED CODE ###

S = input()
if all(S[0] == x for x in S):
    print(len(S))
else:
    print(min(max(i + 1, len(S) - (i + 1)) for i in range(len(S) - 1) if S[i] != S[i + 1]))
'''
    Auther: ghoshashis545 Ashis Ghosh
    college: jalpaiguri Govt Enggineering College
    Date:12/03/2020
'''

s=input()
t=input()
Mxn=3005
dp=[["" for i in range(Mxn)] for j in range(Mxn)] 
n=len(s)
m=len(t)
for i in range(n+1):
    for j in range(m+1):
        if(i==0 or j==0):
            dp[i][j]=""
        elif(s[i-1]==t[j-1]):
            dp[i][j]=dp[i-1][j-1]+s[i-1]
        else:
            if(len(dp[i][j-1])<len(dp[i-1][j])):
                dp[i][j]=dp[i-1][j-1]
            else:
                dp[i][j]=dp[i][j-1]
print(dp[n][m])

    
    
    
    
    






    


### FIXED CODE ###

inf = float("inf") 
n=int(input())
a=list(map(int ,input().split()))
dp=[inf]*n
k=2
dp[0]=0
for i in range(1,n):
   for j in range(i-1,max(0,i-k)-1,-1):
       dp[i]=min(dp[i],dp[j]+abs(a[i]-a[j]))
print(dp[n-1])
mod = (10 ** 9) + 7
lim = 1100000

fct = [0] * lim
inv_f = [0] * lim

fct[0] = 1
for i in range(1, lim):
    fct[i] = fct[i - 1] * i % mod

inv_f[lim - 1] = pow(fct[lim - 1], -1, mod)

for i in range(lim - 1, 0, -1):
    inv_f[i - 1] = inv_f[i] * i % mod


def nCk(a, b):
    if a < b:
        return 0
    else:
        return fct[a] * inv_f[b] * inv_f[a - b] % mod


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

s_max = 0
s_min = 0

for i in range(k - 1, n):
    s_max = s_max + s[i] * nCk(i, k - 1)
    s_max %= mod

for i in range(n - k + 1):
    s_min = s_min + s[i] * nCk(n - i - 1, k - 1)
    s_min %= mod

print((s_max-s_min) % mod)
# print(s_max, s_min)


### FIXED CODE ###

mod = (10 ** 9) + 7
lim = 1100000

fct = [0] * lim
inv_f = [0] * lim

fct[0] = 1
for i in range(1, lim):
    fct[i] = fct[i - 1] * i % mod

inv_f[lim - 1] = pow(fct[lim - 1], mod - 2, mod)

for i in range(lim - 1, 0, -1):
    inv_f[i - 1] = inv_f[i] * i % mod


def nCk(a, b):
    if a < b:
        return 0
    else:
        return fct[a] * inv_f[b] * inv_f[a - b] % mod


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

s_max = 0
s_min = 0

for i in range(k - 1, n):
    s_max = s_max + s[i] * nCk(i, k - 1)
    s_max %= mod

for i in range(n - k + 1):
    s_min = s_min + s[i] * nCk(n - i - 1, k - 1)
    s_min %= mod

print((s_max-s_min) % mod)
# print(s_max, s_min)
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from heapq import heappush, heappushpop

def resolve():
    it = map(int, sys.stdin.read().split())

    T = next(it)
    if T == 3: raise 1
    ans = []
    for i in range(T):
        N = next(it)

        val = 0
        a1 = [[] for i in range(N)]
        a2 = [[] for i in range(N)]
        #for i, v1, v2 in ((next(it)-1, next(it), next(it)) for i in range(N)):
        for i in range(N):
            i, v1, v2 = next(it)-1, next(it), next(it)
            diff = v1 - v2
            if diff == 0 or i == N-1:
                val += v1
            elif diff > 0:
                a1[i].append(diff)
                val += v2
            else:
                i = N-1-i-1
                a2[i].append(-diff)
                val += v1

        for ax in (a1, a2):
            dq = []
            for i, aa in enumerate(ax):
                if not aa: continue
                for diff in aa:
                    ld = len(dq)
                    if ld <= i:
                        heappush(dq, diff)
                        val += diff
                    else:
                        df = heappushpop(dq, diff)
                        val += diff - df

        ans.append(val)


    print(*ans, sep="\n")



if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
sys.setrecursionlimit(1000000000)

def resolve():
    it = map(int, sys.stdin.read().split())

    T = next(it)
    ans = []
    for i in range(T):
        N = next(it)

        val = 0; a1 = []; a2 = []
        for i, v1, v2 in ((next(it), next(it), next(it)) for i in range(N)):
            diff = v1 - v2
            a, v, diff = (a1, v2, diff) if diff >= 0 else (a2, v1, -diff)
            a.append((diff, i))
            val += v
        a1.sort(reverse=True); a2.sort(reverse=True)

        ls = len(a1)
        vis = [None]*(N+1)
        def root(x):
            if vis[x] == None: return x

            vis[x] = root(vis[x])
            return vis[x]
        def root(x):
            a = []
            while True:
                y = vis[x]
                if y == None:
                    break
                a.append(x)
                x = y
            for i in a:
                vis[i] = x
            return x

        for diff, i in a1:
            j = min(i, ls) - 1
            k = root(j)
            #print(diff, i, j, k,  vis)
            if k < 0: continue
            val += diff
            vis[k] = k - 1


        for diff, i in a2:
            j, v2 = max(i, ls), [[-1]]
            k = root(j)
            #print(diff, i, j, k,  vis)
            if k >= N: continue
            val += diff
            vis[k] = k + 1

        ans.append(val)

    print(*ans, sep="\n")



if __name__ == "__main__":
    resolve()
n, a, b, c, d = (map(int, input().split()))
S = input()
if '##' in S:
	print('No')
elif d<c:
	if not '...' in S:
    	print ('No')
	if d <= n and S[d]=='#' and d-2 >= 0 and s[d-2]=='#':
		print('No')
else:
	print('Yes')



### FIXED CODE ###

n, a, b, c, d = (map(int, input().split()))
S = input()
if '##' in S[a-1:c] or '##' in S[b-1:d] :
	print('No')
elif d < c and not '...' in S[b-2:d+1]:
        print('No')
else:
    print('Yes')
a,b=map(int,input())
print(min(a,b))

### FIXED CODE ###

a,b=map(int,input().split())
print(a if a<=b else a-1)
import numpy as np 

L, R = list(map(int, input().split()))
data = np.array([x for x in range(L, R+1)]) % 2019

if np.where(data == 0):
    print(0)

else: 
    data = np.sort(data)
    min_mod = (data[0] * data[1]) % 2019
    print(min_mod)

### FIXED CODE ###

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

tac = N * A
train = B

if tac < train:
    print(tac)

else:
    print(train)
import re
# 盤面の状態
s = input()

cnt = 0

while True:
    # 全部Wになるまで or 1文字残しまで繰り返す
    if s.count("W") == len(s) or len(s)==1:
        break
    else:
        print(s)

    # 先頭を置換する
    if s[0] == "W":
        s = re.sub(r'[W]+', "", s,1)
        cnt +=1
    elif s[0] == "B":
        s = re.sub(r'[B]+', "", s,1)
        cnt +=1

print(cnt)

### FIXED CODE ###

import re
# 盤面の状態
s = input()

# Aマッチする数を数える
w = re.findall(r'[W]+', s)
# Bにマッチする数を数える
b= re.findall(r'[B]+', s)

# 全部Wなら入れ替える必要なし
if s.count("W") == len(s):
    print(0)
else:
    print(len(w)+len(b)-1)
N = int(input())
A = map(int, input().split())
Q = int(input())



A = list(A)

hashmap = {}
s = 0
for i in range(len(A)):
	s += A[i]
	hashmap[A[i]] = hashmap.get(A[i], {'i': 0, 'v': A[i]}) 
	hashmap[A[i]]['i'] += 1

for _ in range(Q):
	# replace every element whose value is B with C
	B, C = map(int, input().split())

	if B in hashmap:
		num = hashmap[B]['i']
		del hashmap[B]
		s -= num * B
		s += num * C

	hashmap[C] = hashmap.get(C, {'i': 0, 'v': C})
	hashmap[C]['i'] += num
	print(s)

### FIXED CODE ###

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



A = list(A)

hashmap = {}
s = 0
for i in range(len(A)):
	s += A[i]
	hashmap[A[i]] = hashmap.get(A[i], [0, A[i]]) 
	hashmap[A[i]][0] += 1

for _ in range(Q):
	# replace every element whose value is B with C
	B, C = map(int, input().split())

	if B in hashmap:
		num = hashmap[B][0]
		del hashmap[B]
		s -= num * B
		s += num * C

		hashmap[C] = hashmap.get(C, [0, C])
		hashmap[C][0] += num
	print(s)
n,m=map(int,input().split())
a=[]
for i in range(m):
  a.append(int(input()))
lst=[]
lst.append(a[0])
lst.append(0)
for j in range(m-1):
  lst.append(a[j+1]-a[j]-1)
  lst.append(0)
lst.append(n-a[m-1])
l=len(lst)
for k in range(l-1):
  if lst[k]==0 and lst[k+1]==0:
    print(0)
    break
  else:
    if lst[k]>1:
      lst[k]-=1
if lst[l-1]>1:
  lst[l-1]-=1
for p in range(l):
  if lst[p]==0:
    del lst[p]
totl=1
for q in range(len(lst)):
  totl*=lst[q]
  totl=totl%1000000007
print(totl)




 
  
  
   
    





### FIXED CODE ###

import sys
n,m=map(int,input().split())
a=[]
for i in range(m):
  a.append(int(input()))
a.sort()
for i in range(m-1):
  if a[i+1]-a[i]==1:
    print(0)
    sys.exit()
p=10**9+7  
dp=[0]*(n+1)
dp[0]=1
if 1 not in a:
  dp[1]=1
lst=set(list(range(1,n+1)))
A=set(a)
Lst=lst-A
Lst=list(Lst)
if 1 in Lst:
  Lst.remove(1)
for i in Lst:
  dp[i]=dp[i-1]+dp[i-2]
  if p<=dp[i]:
    dp[i]=dp[i]%p
print(dp[n]%p)
#ABC 171 C - One Quadrillion and One Dalmatians 10:59

n = int(input())
q = []
while n > 0:
    v = n % 26
    q.append(v)
    n //= 26

res = ''
dic = {1: 'a', 2:'b', 3:'c', 4:'d', 5:'e', 6:'f', 7:'g', 8:'h', 9:'i',
      10:'j', 11:'k', 12:'l', 13:'m', 14:'n', 15:'o', 16:'p', 17:'q',
      18:'r', 19:'s', 20:'t', 21:'u', 22:'v', 23:'w', 24:'x', 25:'y', 26:'z'}

for i in reversed(q):
    res += dic[i]

print(res)

### FIXED CODE ###

#ABC 171 C - One Quadrillion and One Dalmatians 10:59

n = int(input())
res =''
while n > 0:
    n -= 1
    res += chr(ord('a') + n % 26)
    n //= 26
print(res[::-1])
s=input().split()
a=int(s[0])
b=int(s[1])
c=int(s[2])
num=[a,b,c]
num.sort()
print(str(num[0])+" "+str(num[1]+" "+str(num[2])))


### FIXED CODE ###

s=input().split()
a=int(s[0])
b=int(s[1])
c=int(s[2])
num=[a,b,c]
num.sort()
print(str(num[0])+" "+str(num[1])+" "+str(num[2]))