Harryxun/stf_run huggingface dataset:
from functools import reduce

N, K = map(int, input().split())
A = list(map(int, input().split()))
Ap = [a for a in A if a>0]
Am = [a for a in A if a<0]
mod = 10**9+7
if len(Ap) + len(Am) < K:
    print(0)
    exit()
if len(Ap) + len(Am) == K:
    if 0 in A and len(Am) % 2:
        print(0)
    else:
        ans = reduce(lambda a, b: a * b % mod, Ap+Am, 1)
        print(ans)
    exit()
Ap.sort(reverse=True)
Am.sort()
if len(Ap) == 0 and K%2:
    ans = reduce(lambda a, b: a*b%mod, Am[-K:], 1)
    print(ans)
    exit()
idx_Am = 0
n = 0
ans = 1
for idx_Ap, ap in enumerate(Ap):
    while idx_Am < len(Am) and n < K and -Am[idx_Am] > ap:
        ans = ans * Am[idx_Am] % mod
        idx_Am += 1
        n += 1
    if n == K:
        break
    n += 1
    idx_Ap += 1
    ans = ans * ap % mod
    if n == K:
        break
else:
    assert False
if idx_Am % 2 == 0:
    print(ans)
else:
    if idx_Ap == len(Ap) or (idx_Am != len(Am) and -Am[idx_Am] / Ap[idx_Ap-1] > Ap[idx_Ap] / -Am[idx_Am-1]):
        ans = ans * Am[idx_Am] * pow(Ap[idx_Ap-1], mod-2, mod) % mod
    else:
        ans = ans * Ap[idx_Ap] * pow(Am[idx_Am-1], mod-2, mod) % mod
    print(ans)


### FIXED CODE ###

from functools import reduce

N, K = map(int, input().split())
A = list(map(int, input().split()))
Ap = [a for a in A if a>0]
Am = [a for a in A if a<0]
mod = 10**9+7
if len(Ap) + len(Am) < K:
    print(0)
    exit()
if len(Ap) + len(Am) == K:
    if 0 in A and len(Am) % 2:
        print(0)
    else:
        ans = reduce(lambda a, b: a * b % mod, Ap+Am, 1)
        print(ans)
    exit()
Ap.sort(reverse=True)
Am.sort()
if len(Ap) == 0:
    if K%2:
        if 0 in A:
            ans = 0
        else:
            ans = reduce(lambda a, b: a*b%mod, Am[-K:], 1)
    else:
        ans = reduce(lambda a, b: a*b%mod, Am[:K], 1)
    print(ans)
    exit()

idx_Am = 0
n = 0
ans = 1
for idx_Ap, ap in enumerate(Ap+[0]):
    while idx_Am < len(Am) and n < K and -Am[idx_Am] > ap:
        ans = ans * Am[idx_Am] % mod
        idx_Am += 1
        n += 1
    if n == K:
        break
    n += 1
    idx_Ap += 1
    ans = ans * ap % mod
    if n == K:
        break
else:
    assert False
if idx_Am % 2 == 0:
    print(ans)
else:
    if idx_Ap == len(Ap) or (idx_Am != len(Am) and idx_Ap > 0 and Am[idx_Am] * Am[idx_Am-1] > Ap[idx_Ap] * Ap[idx_Ap-1]):
        ans = ans * Am[idx_Am] * pow(Ap[idx_Ap-1], mod-2, mod) % mod
    else:
        ans = ans * Ap[idx_Ap] * pow(Am[idx_Am-1], mod-2, mod) % mod
    print(ans)
def Class(x):
	if x<=48.0:
		print("light fly")
	elif 48.0<x<=51.0:
		print("fly")
	elif 51.0<x<=54.0:
		print("bantam")
	elif 54.0<x<=57.0:
		print("feather")
	elif 57.0<x<=60.0:
		print("light")
	elif 60.0<x<=64.0:
		print("light welter")
	elif 64.0<x<=69.0:
		print("welter")
	elif 69.0<x<=75.0:
		print("light middle")
	elif 75.0<x<=81.0:
		print("middle")
	elif 81.0<x<=91.0:
		print("light heavy")
	else:
		ptinr("heavy")

while True:
	try:
		x=float(input())
		Class(x)
	except EOFError:
		break

### FIXED CODE ###

def Class(x):
	if x<=48.0:
		print("light fly")
	elif 48.0<x<=51.0:
		print("fly")
	elif 51.0<x<=54.0:
		print("bantam")
	elif 54.0<x<=57.0:
		print("feather")
	elif 57.0<x<=60.0:
		print("light")
	elif 60.0<x<=64.0:
		print("light welter")
	elif 64.0<x<=69.0:
		print("welter")
	elif 69.0<x<=75.0:
		print("light middle")
	elif 75.0<x<=81.0:
		print("middle")
	elif 81.0<x<=91.0:
		print("light heavy")
	else:
		print("heavy")

while True:
	try:
		x=float(input())
		Class(x)
	except EOFError:
		break
a,b = input().split()

c = a+b
number = int(c)
w = False

for i in range(number/2):
    if i*i == number:
        print("Yes")
        w = True
        break
if w == False:
    print("No")

### FIXED CODE ###

a,b = input().split()

c = a+b
w = False

for i in range(int(c)):
    if i*i == int(c):
        print("Yes")
        w = True
        break
if w == False:
    print("No")
N = int(input())
a = list(map(int,input().split()))
color = [False]*8
over_human = 0
for i in a:
    if(i<=399):
        color[0]=True
    elif(i<=799):
        color[1]=True
    elif(i<=1199):
        color[2]=True
    elif(i<=1599):
        color[3]=True
    elif(i<=1999):
        color[4]=True
    elif(i<=2399):
        color[5]=True
    elif(i<=2799):
        color[6]=True
    elif(i<=3199):
        color[7]=True
    elif(i>=3200):
        over_human += 1
if(color.count(True)==0):
    print(1,color.count(True)+over_human))
else:
    print(color.count(True),color.count(True)+over_human))


### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
color = [False]*8
over_human = 0
for i in a:
    if(i<=399):
        color[0]=True
    elif(i<=799):
        color[1]=True
    elif(i<=1199):
        color[2]=True
    elif(i<=1599):
        color[3]=True
    elif(i<=1999):
        color[4]=True
    elif(i<=2399):
        color[5]=True
    elif(i<=2799):
        color[6]=True
    elif(i<=3199):
        color[7]=True
    elif(i>=3200):
        over_human += 1
if(color.count(True)==0):
    print(1,color.count(True)+over_human)
else:
    print(color.count(True),color.count(True)+over_human)
n = int(input())
ans = [0 for i in range(1000)]
for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            if x*x+y*y+z*z+x*y+y*z+z*x < 1000:
                ans[x*x+y*y+z*z+x*y+y*z+z*x-1] += 1

for i in range(n):
    print(ans[i])


### FIXED CODE ###

n = int(input())
ans = [0 for i in range(10100)]
for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            if x*x+y*y+z*z+x*y+y*z+z*x < 10001:
                ans[x*x+y*y+z*z+x*y+y*z+z*x-1] += 1

for i in range(n):
    print(ans[i])
char_list = list(str)
for i in range(4):
    
    if i == 3:
        print('Good')
        break
    
    if char_list[i] == char_list[i+1] and i < 3:
        print('Bad')
        break

### FIXED CODE ###

char_list = list(input())
for i in range(4):
    
    if i == 3:
        print('Good')
        break
    
    if char_list[i] == char_list[i+1] and i < 3:
        print('Bad')
        break
while True:
    x = input().split()
    H = x[0]
    W = x[1]
    if H == 0 and W == 0:
        break
    for i in range(0,H):
        print "#"*W
    print ""

### FIXED CODE ###

while True:
    H,W = map(int,input().split())
    if H == 0 and W == 0:
        break
    a = [["#" for j in range(W)] for i in range(H)]
    b = ["".join(a[i]) for i in range(H)]
    for i in range(H):
        print(b[i])
    print()
n=input()
d=["9":"1","1":"9"]
"".join(d[x] for x in n)

### FIXED CODE ###

n=input()
d={"9":"1","1":"9"}
print("".join(d[x] for x in n))
put=int(Input())
str=str(Intput())
print(str.count("ABC"))

### FIXED CODE ###

N = int(input())
S = str(input())
print(S.count("ABC"))
def decide_H(Cx,Cy,x,y,h):
    H=h+abs(x-Cx)+abs(y-Cy)
    if H>=1:
        return(H)

def check_H(Cx,Cy,H):
    for x,y,h in T:
        if h != max(H - abs(x - Cx) - abs(y - Cy), 0):
        # if H==decide_H(Cx,Cy,x,y,h) and H!=None and h!=0:
        #     continue
            return False
    return True

N=int(input())
T=[[int(i) for i in input().split()] for _ in range(N)]

for Cx in range(101):
    for Cy in range(101):
        for x,y,h in T:
            H=decide_H(Cx,Cy,x,y,h)
            if check_H(Cx,Cy,H):
                print(Cx,Cy,H)
                exit()
            else:
                break

### FIXED CODE ###

def get_H(Cx, Cy):
    for x, y, h in L:
        if h > 0:
            return abs(x - Cx) + abs(y - Cy) + h


def check_H(Cx, Cy, H):
    for x, y, h in L:
        if h != max(H - abs(x - Cx) - abs(y - Cy), 0):
            return False
    return True


N = int(input())

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

for Cx in range(101):
    for Cy in range(101):
        H = get_H(Cx, Cy)
        if check_H(Cx, Cy, H):
            print('{} {} {}'.format(Cx, Cy, H))
            exit(0)
from  math import gcd
from functools import reduce
n = int(input())
li = list(map(int,input().split()))
print(reduce(gcd,li))

### FIXED CODE ###

from fractions import gcd
from functools import reduce
n = int(input())
li = list(map(int,input().split()))
print(reduce(gcd,li))
n=int(input())
x=[[0 for i in range(26)] for j in range(n)]
for i in range(n):
    s=input()
    for j in range(len(s)):
        x[i][ord(s[j])-97]+=1
ans=[0]*26
for i in range(n):
    ans[i]=min(x[j][i] for j in range(n))
a=[]
for i in range(26):
    for j in range(ans[i]):
        a.append(chr(97+i))
print("".join(a))



### FIXED CODE ###

n=int(input())
x=[[0 for i in range(26)] for j in range(n)]
for i in range(n):
    s=input()
    for j in range(len(s)):
        x[i][ord(s[j])-97]+=1
ans=[0]*26
for i in range(26):
    ans[i]=min(x[j][i] for j in range(n))
a=[]
for i in range(26):
    for j in range(ans[i]):
        a.append(chr(97+i))
print("".join(a))
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)


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


def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)


def lcm(*numbers):
    return functools.reduce(lcm_base, numbers, 1)


def lcm_list(numbers):
    return functools.reduce(lcm_base, numbers, 1)


def count_two(x):
    count = 0
    while x%2 == 0:
        count += 1
        x //= 2
    return count


two_count = count_two(A[0])
for a in A[1:]:
    if two_count != count_two(a):
        print(0)
        exit()

LCM = lcm(*A)
# print(LCM)
print((m - LCM//2)//LCM + 1)


### FIXED CODE ###

import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
# import math
from fractions import gcd

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)


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


def lcm_base(x, y):
    # return (x * y) // math.gcd(x, y)
    return (x * y) // gcd(x, y)


def lcm_list(numbers):
    x = 1
    for i in range(n):
        x = lcm_base(x, numbers[i])
        if x > 2*m:
            print(0)
            exit()

    return x


def count_two(x):
    count = 0
    while x%2 == 0:
        count += 1
        x //= 2
    return count


two_count = count_two(A[0])
for a in A[1:]:
    if two_count != count_two(a):
        print(0)
        exit()

LCM = lcm_list(A)
# print(LCM)
print((m - LCM//2)//LCM + 1)
import sys

def main():
    n, k = map(int, sys.stdin.buffer.readline().split())
    a = [0] + list(map(int, sys.stdin.buffer.readline().split()))

    visited = [0]*(n+1)
    town = 1
    for i in range(1, k+1):
        town = a[town]
        if visited[town] == 0:
            visited[town] = i
        else:
            cyc = (k - visited[town])%(i + visited[town]) + visited[town]
            print(visited.index(cyc))
            exit()
    print(town)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

def main():
    n, k = map(int, sys.stdin.buffer.readline().split())
    a = [0] + list(map(int, sys.stdin.buffer.readline().split()))

    visited = [0]*(n+1)
    town = 1
    for i in range(1, k+1):
        town = a[town]
        if visited[town] == 0:
            visited[town] = i
        else:
            cyc = (k - visited[town])%(i - visited[town]) + visited[town]
            print(visited.index(cyc))
            exit()
    print(town)

if __name__ == "__main__":
    main()
def list_pos(cnt,a,b,ans):
    if ans  >= b :
        return cnt-1
    else :

        ans += a[cnt][1]
        cnt += 1
    return list_pos(cnt,a,b,ans)

N,K = map(int,input().split())
para = {}
for i in range(N):
    a,b  = map(int,input().split())
    if not a in para.keys():
        para[a] = b
    else : para[a] += b

para = sorted(para.items(),key =lambda x:x[0])

p = list_pos(0,para,K,0)
print("{}".format(para[p][0]))

### FIXED CODE ###


def list_pos(cnt,a,b,ans):
    if ans  >= b :
        return cnt-1
    else :

        ans += a[cnt][1]
        cnt += 1
        return list_pos(cnt,a,b,ans)
import sys
sys.setrecursionlimit(100000)
N,K = map(int,input().split())
para = {}
for i in range(N):
    a,b  = map(int,input().split())
    if not a in para.keys():
        para[a] = b
    else : para[a] += b

para = sorted(para.items(),key =lambda x:x[0])

p = list_pos(0,para,K,0)
print("{}".format(para[p][0]))
import math

x1, y1, x2, y2 = map(float, raw_input().split())

print sqrt((x2-x1)**2 + (y2-y1)**2)

### FIXED CODE ###

import math

x1, y1, x2, y2 = map(float, raw_input().split())
print math.sqrt((x2-x1)**2 + (y2-y1)**2)
A = int(input())
B = int(input())
B = int(input())
b_5 = 0
b_7 = 0
if A == 5:
  b_5 += 1
elif A == 7:
  b_7 += 1
if B == 5:
  b_5 +=1
elif B==7:
  b_7 += 1
if C==5:
  b_5 +=1
elif C==7:
  b_7 += 1

if b_5 == 2 and b_7 == 1:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

A,B,C = map(int,input().split())
b_5 = 0
b_7 = 0
if A == 5:
  b_5 += 1
elif A == 7:
  b_7 += 1
if B == 5:
  b_5 +=1
elif B==7:
  b_7 += 1
if C==5:
  b_5 +=1
elif C==7:
  b_7 += 1

if b_5 == 2 and b_7 == 1:
  print("YES")
else:
  print("NO")
import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0: return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else: return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))
def div2(a, b):
    return mul(a, modinv(b))

def modinv(a):
    b, u, v = mod, 1, 0
    while b:
        t = a//b
        a, u = a-t*b, u-t*v
        a, b, u, v = b, a, v, u
    u %= mod
    return u

def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NNN = (10**5)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
H, W, A, B = map(int, input().split())

r = 0
for i in range(H-A):
#    (0, 0) -> (i, B-1)
#    (i, B) -> (H-1, W-1)
    r = (r + mul(cmb(i+B-1, i), cmb(H-1-i+W-1-B, H-1-i)))%mod
print(r)



### FIXED CODE ###

import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0: return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else: return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))
def div2(a, b):
    return mul(a, modinv(b))

def modinv(a):
    b, u, v = mod, 1, 0
    while b:
        t = a//b
        a, u = a-t*b, u-t*v
        a, b, u, v = b, a, v, u
    u %= mod
    return u

def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NNN = (10**6)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
H, W, A, B = map(int, input().split())

r = 0
for i in range(H-A):
#    (0, 0) -> (i, B-1)
#    (i, B) -> (H-1, W-1)
    r = (r + mul(cmb(i+B-1, i), cmb(H-1-i+W-1-B, H-1-i)))%mod
print(r)
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


class Eratosthenes:
    def __init__(self, n):
        self.n = n
        self.min_factor = [-1] * (n + 1)
        self.min_factor[0], self.min_factor[1] = 0, 1

    def get_primes(self):
        primes = []
        is_prime = [True] * (self.n + 1)
        is_prime[0] = is_prime[1] = False
        for i in range(2, self.n + 1):
            if not is_prime[i]:
                continue
            primes.append(i)
            self.min_factor[i] = i
            for j in range(i * 2, self.n + 1, i):
                is_prime[j] = False
                if self.min_factor[j] == -1:
                    self.min_factor[j] = i
        return primes

    def prime_factorization(self, n):
        res = []
        while n != 1:
            prime = self.min_factor[n]
            exp = 0
            while self.min_factor[n] == prime:
                exp += 1
                n //= prime
            res.append([prime, exp])
        return res

def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    MAX_A = max(A)

    er = Eratosthenes(MAX_A)
    er.get_primes()
    num = [0] * MAX_A
    for i in range(n):
        pf = er.prime_factorization(A[i])
        for p, ex in pf:
            num[p] = max(num[p], ex)

    LCM = 1
    for v in range(2, MAX_A):
        LCM *= pow(v, num[v], mod)
        LCM %= mod

    res = 0
    for a in A:
        res += LCM * pow(a, mod - 2, mod)
        res %= mod
    print(res)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def prime_factorization(n):
    res = []
    for i in range(2, int(pow(n, 0.5)) + 1):
        if n % i == 0:
            ex = 0
            while n % i == 0:
                ex += 1
                n //= i
            res.append([i, ex])
    if n != 1:
        res.append([n, 1])
    return res


def resolve():
    n = int(input())
    A = list(map(int, input().split()))

    prime = [0] * max(A)
    for a in A:
        primes = prime_factorization(a)
        for num, ex in primes:
            prime[num - 1] = max(prime[num - 1], ex)

    L = 1
    for i in range(len(prime)):
        if prime[i] == 0:
            continue
        L *= pow(i + 1, prime[i])

    res = 0
    for a in A:
        res += L * pow(a, mod - 2, mod)
        res %= mod
    print(res)


if __name__ == '__main__':
    resolve()
import itertools
import collections
from operator import mul
from functools import reduce

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

ans = 0

if len(set(V)) == 1:
  d = reduce(mul,[i for i in range(1,A)])
  for i in range(A,B + 1):
    n = 1
    d *= i
    for j in range(B,B - i,-1):
      n *= j
    n /= d
    ans += n
  print(float(V[0]))
  print(int(ans))
else:
  a = A - 1
  sect = V[:A]
  ave = sum(sect) / A
  print(ave)
  con = V.count(V[a])
  ind = V.index(V[a])
  i = a - ind + 1
  if a == ind:
    print(con)
  else:
    n = reduce(mul,[t for t in range(con - i + 1,con + 1)]) 
    d = reduce(mul,[k for k in range(1,i + 1)])
    print(int(n/d))

### FIXED CODE ###

import collections
from operator import mul
from functools import reduce

N,A,B = map(int, input().split())
V = list(map(int, input().split()))
VV = sorted(V,reverse = True)
ave = 0
ml = []

for i in range(A,B + 1):
  avet = sum(VV[:i]) / i
  if avet >= ave:
    ml.append(i)
    ave = max(ave,avet)
  else:
    break

dic = collections.Counter(V)
#print(dic,ml)

def cmb(n,r):
  r = min(n - r,r)
  if r == 0:
    return 1
  over = reduce(mul,range(n, n - r, -1))
  under = reduce(mul,range(1,r + 1))
  return over // under

res = 0

for j in ml:
  r = dic[VV[j - 1]]
  rr = VV.index(VV[j - 1])
  res += cmb(r,j - rr)

print(ave)
print(res)
x = input()
if x >= 1200:
    print(ARC)
else:
    print(ABC)

### FIXED CODE ###

x = input()
if int(x) >= 1200:
    print("ARC")
else:
    print("ABC")
def combi(n,r):
  s = fac[n]
  t = fac[r]
  u = fac[n-r]
  ans = (s*pow(t,p-2,p)*pow(u,p-2,p) )%p
  return ans
  
from collections import Counter
N=int(input())
D=list(map(int, input().split() ))
di=dict(Counter(D))
p=998244353

fac=[1]
for i in range(1,N):
  fac.append( (fac[-1]*i)%p )

ans=1
for i,num in enumerate(sorted(di)):
  if i==0:
    if di[num]!=1:
      ans=0
      break
  else:    
    ans = (ans * combi(di[i-1]+di[i]-1,di[i-1]-1))%p
    ans = (ans * fac[ di[i-1] ]) %p
    print(i,num,di[num],combi(di[i-1]+di[i]-1,di[i-1]-1),fac[ di[i-1] ],ans)
  
print(ans)

### FIXED CODE ###

from collections import Counter
N=int(input())
D=list(map(int, input().split() ))
d=dict(Counter(D))
p=998244353
#print(d)
maxi=max(d)

ans=1
if D[0]!=0:
  print(0)
else:
  if d[0]!=1:
    print(0)
  else:
    for i in range(1,maxi+1):
      if i not in d:
        print(0)
        exit()
      else:
        s =  (d[i-1]**d[i])%p
        ans = (ans * s)%p
    print(ans)
import sys
N,M,X,Y = map(int,input().split())
array_x = list(map(int,input().split()))
array_y = list(map(int,input().split()))

if not ( 1 <= N <= 100 and 1 <= M <= 100 ): sys.exit()
if not ( -100 <= X <= 100 and -100 <= Y <= 100 ): sys.exit()
for I in array_x:
    if not ( -100 <= I <= 100 and array_x.count(I) == 1 and I != X): sys.exit()
for J in array_y:
    if not ( -100 <= J <= 100 and array_y.count(J) == 1 and J != Y): sys.exit()

if min(array_y) - max(array_x) >= 1:
    for K in range(max(array_x),min(array_y)+1):
        if X < K <= Y and max(array_x) < K and min(array_y) >= K:
            print('No War')
            sys.exit()
if min(array_x) - max(array_y) >= 1:
    for L in range(max(array_y),min(array_x)+1):
        if X < K <= Y and max(array_y) < K and min(array_x) >= K:
            print('No War')
            sys.exit()
print('War')

### FIXED CODE ###

import sys
N,M,X,Y = map(int,input().split())
array_x = list(map(int,input().split()))
array_y = list(map(int,input().split()))

if not ( 1 <= N <= 100 and 1 <= M <= 100 ): sys.exit()
if not ( -100 <= X <= 100 and -100 <= Y <= 100 ): sys.exit()
for I in array_x:
    if not ( -100 <= I <= 100 and array_x.count(I) == 1 and I != X): sys.exit()
for J in array_y:
    if not ( -100 <= J <= 100 and array_y.count(J) == 1 and J != Y): sys.exit()

for I in range(X+1,Y+1):
    if I > max(array_x) and I <= min(array_y):
        print('No War')
        sys.exit()
print('War')
N = input()
N = int(N)

a_sub = input().split(" ")
a = [int(n0) for n0 in a_sub]
# print(a)

b_sub = input().split(" ")
b = [int(n0) for n0 in b_sub]
# print(b)

c_sub = input().split(" ")
c = [int(n0) for n0 in c_sub]
# print(c)

score = 0
for xi in range(N):
    score = score + b[xi]
    if a[xi+1]==a[xi]+1 and xi<N:
        score = score + c[a[xi]-1]
        print(xi, c[xi])

# print(score)

for xi in range(N-1):
    if a[xi+1]==a[xi]+1:
        score = score + c[a[xi]-1]
        print(xi, c[xi])
print(score)


### FIXED CODE ###

N = input()
N = int(N)
print(N**3)
import bisect
N, M = map(int, input().split())
a = []
number = []
flag = 0
for i in range(M):
    A, B = map(int, input().split())
    a.append([A, B])
    a.append([B, A])
    number.append(A)
    number.append(B)
a.sort()
b = a[:]
b.reverse()
one = []
two = []
for i in range(M):
    if a[i][0] == 1:
        one.append(a[i][1])
    else:
        break

for i in range(M):
    if b[i][0] == N:
        two.append(b[i][1])
    else:
        break



for i in range(len(one)):
    for j in range(len(two)):
        if one[i] == two[j]:
            flag = 1
            print("POSSIBLE")  
                break
    if flag == 1:
        break

if flag == 0:
    print("IMPOSSIBLE")


### FIXED CODE ###

import sys

N, M = map(int, input().split())
ship = [[] for i in range(N+1)]

for i in range(M):
    a, b = map(int, input().split())
    ship[a].append(b)
    ship[b].append(a)

flag = 0
for i in ship[1]:
    if N in ship[i]:
        flag = 1
if flag == 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
N = int(input())
A = [int(i) for i in input().split()]
C = [0] * 10001
s = 0
for i in A:
    C[i] += 1
    s += i

K = int(input())

for i in range(K):
    f, t = map(int, input().split())
    C[t] += C[f]
    s += t * C[f]
    s -= f * C[f]
    C[f] = 0
    print(s)

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
C = [0] * 100001
s = 0
for i in A:
    C[i] += 1
    s += i

K = int(input())

for i in range(K):
    f, t = map(int, input().split())
    C[t] += C[f]
    s += t * C[f]
    s -= f * C[f]
    C[f] = 0
    print(s)