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

import functools
import operator
prod = functools.partial(functools.reduce, operator.mul)

def sieve(n=10**7):
    srn = int(n ** 0.5) + 1
    f = [True] * (srn + 1)
    res = []
    for i in range(2, srn+1):
        if not f[i]:
            continue
        res.append(i)
        for j in range(i * i, srn+1, i):
            f[j] = False
    return res

def trial_division(n):
    fn = dict()
    for p in pn:
        if p > n:
            break
        while n % p == 0:
            fn[p] = fn.get(p, 0) + 1
            n //= p
    if n > 1:
        fn[n] = fn.get(n, 0) + 1
    return prod([f + 1 for f in fn.values()])

N = int(input())
pn = sieve(N)
res = sum(i * trial_division(i) for i in range(2, N+1))
print(res + 1)

### FIXED CODE ###

N = int(input())
res = 0
for i in range(1, N+1):
    j = N // i
    res += j * (j + 1) // 2 * i
print(res)
### BUGGY CODE ###

MOD = 10 ** 9 + 7

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
            result %= MOD

    return result

def solve():
    n, a, b = [int(_) for _ in input().split()]
    return (2 ** n)%MOD - 1 - cmb(n, a) - cmb(n, b)

if __name__ == '__main__':
    print(solve()%MOD)


### FIXED CODE ###

MOD = 10 ** 9 + 7

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
            result %= MOD

    return result%MOD

def solve():
    n, a, b = [int(_) for _ in input().split()]
    nb = cmb(n, b)
    na = cmb(n, a)
    return (2 ** n)%MOD - 1 - na - nb

if __name__ == '__main__':
    print(solve()%MOD)
### BUGGY CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque
def run():
    N, S = map(int, sysread().split())
    A = [0]+ list(map(int,sysread().split()))
    dp = [[0] * (S+1) for _ in range(N+1)]
    if A[1] <= S:
        dp[1][A[1]] = 1
    mod = 998244353
    for r in range(1, N):
        if A[r+1] <= S:
            dp[r+1][A[r+1]] += r+1
            dp[r + 1][A[r + 1]] %= mod
        for s in range(1,S+1):
            dp[r+1][s] += dp[r][s] + dp[r][s] - dp[r-1][s]
            dp[r+1][s] %= mod
            if s + A[r+1] <= S:
                dp[r+1][s+A[r+1]] += dp[r][s] - dp[r-1][s]
                dp[r + 1][s + A[r + 1]] %= mod
    print(dp[N][S] % mod)






if __name__ == "__main__":
    run()


### FIXED CODE ###

# coding: utf-8
import numpy as np
N, S = list(map(int, input().split()))
A = [0]+list(map(int, input().split()))

dt = np.array([[0 for _ in range(S+1)] for x in range(N+1)])

for n in range(1, N+1):
  if A[n] <= S:
    dt[n,A[n]] += n
  if A[n] < S:
    dt[n, A[n]+1:] += dt[n-1,1:S-A[n]+1] - dt[n-2,1:S-A[n]+1]
  dt[n,:] += dt[n-1,:] * 2 - dt[n-2,:]
  dt[n,:] %= 998244353
print(dt[N,S] % 998244353)
### BUGGY CODE ###

s=input()
t=input()

def get_count_list(s):
    alphabets="abcdefghijklmnopqrstuvwxyz"
    ans={}
    for alphabet in alphabets:
        ans[alphabet]=[]
    for j,i in enumerate(s):
        ans[i].append(j)
    return ans


def get_index2alpha(s):
    ans={}
    for i,c in enumerate(s):
        ans[i]=c
    return ans

s_count=get_count_list(s)
t_count=get_count_list(t)
s_index=get_index2alpha(s)
t_index=get_index2alpha(t)

ans=0
for i in range(len(s)):
    if not s_count[s_index[i]]==t_count[t_index[i]]:
        ans+=1

if ans==0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s=list(input())
t=list(input())
n=len(s)
def get_count_list(s):
    alphabets="abcdefghijklmnopqrstuvwxyz"
    ans={}
    for alphabet in alphabets:
        ans[alphabet]=[]
    for i in range(n):
        ans[s[i]].append(i)
    return ans


def get_index2alpha(s):
    ans={}
    for i in range(n):
        ans[i]=s[i]
    return ans

s_count=get_count_list(s)
t_count=get_count_list(t)
s_index=get_index2alpha(s)
t_index=get_index2alpha(t)

ans=0

s_set=set(s)


for i in range(n):
    s_alpha=s_index[i]
    t_alpha = t_index[i]
    if s_alpha in s_set:
        s_set.remove(s_alpha)
        if not s_count[s_alpha]==t_count[t_alpha]:
            ans+=1

if ans==0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

N,K = map(int,input().split())
P = list(map(int,input().split()))
ans = 0
n_max = 0
place = 0
for i in range(N - K + 1):
	n_max = max(n_max , sum(P[i:i+K]))
	if n_max == sum(P[i:i+K]):
		place = i
for i in range(place,place + K):
	ans += (1 + P[i]) /2 
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
P = list(map(int,input().split()))
ans = 0
n_max = 0
place = 0
n_sum = sum(P[:K])
for i in range(N - K):
	n_sum = n_sum - P[i] + P[i+K]
	if n_max <= n_sum:
		n_max = n_sum
		place = i + 1
for i in range(place,place + K):
	ans += (1 + P[i]) /2 
print(ans)
### BUGGY CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline
N = int(input())

tree_dict = defaultdict(list)
for i in range(N-1):
    u, v, w = list(map(int, input().split()))
    tree_dict[u].append((v, w))
    tree_dict[v].append((u, w))
# print(tree_dict)

key = 1
# print(key)
paint_dict = dict()

q = [key]
paint_dict[key] = 0

idx = 0
while idx < N:
    k = q[idx]
    #print("k", k, paint_dict[k])
    for to, w in tree_dict[k]:
        if to not in q[:idx]:
            if (w + paint_dict[k]) % 2 == 0:
                paint_dict[to] = 0
            else:
                paint_dict[to] = 1
            #print(paint_dict[to], to, w)
            q.append(to)
    idx += 1
for i in range(N):
    print(paint_dict[i+1])


### FIXED CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline
N = int(input())

tree_dict = defaultdict(list)
for i in range(N-1):
    u, v, w = list(map(int, input().split()))
    tree_dict[u].append((v, w))
    tree_dict[v].append((u, w))


# 任意の1点を選んで周辺を判定していく
FROM, TO = 0, 1
q = [(TO, FROM)]

paint_dict = defaultdict(int)
# 明示的な代入
paint_dict[TO] = 0

idx = 0
while idx < N:
    # 現在のノード(now)から隣接ノード(to)の白黒を定め，そのノードを探索のqに回す
    now_node, prev_node = q[idx]
    for to_node, w in tree_dict[now_node]:
        if to_node != prev_node:
            if (w + paint_dict[now_node]) % 2 == 0:
                paint_dict[to_node] = 0
            else:
                paint_dict[to_node] = 1
            q.append((to_node, now_node))
    idx += 1
for i in range(N):
    print(paint_dict[i+1])
### BUGGY CODE ###

import numpy as np
import itertools

n, m, q = map(int, input().split())
a = np.zeros(q, dtype=int)
b = np.zeros(q, dtype=int)
c = np.zeros(q, dtype=int)
d = np.zeros(q, dtype=int)

for i in range(q):
    a[i], b[i], c[i], d[i] = map(int, input().split())

A = np.array(list(itertools.combinations_with_replacement(range(1, m + 1), n)))

cnt = 0

for i in range(len(A)):
    tmp = 0
    for j in range(q):
        if(A[i][b[j]-1] - A[i][a[j]-1]) == c[j]:
            tmp = tmp + d[j]
    cnt = max(cnt, tmp)
print(cnt)

### FIXED CODE ###

import itertools

n, m, q = map(int, input().split())
a = [0] * q
b = [0] * q
c = [0] * q
d = [0] * q

for i in range(q):
    a[i], b[i], c[i], d[i] = map(int, input().split())

A = list(itertools.combinations_with_replacement(range(1, m + 1), n))

cnt = 0

for i in range(len(A)):
    tmp = 0
    for j in range(q):
        if(A[i][b[j]-1] - A[i][a[j]-1]) == c[j]:
            tmp = tmp + d[j]
    cnt = max(cnt, tmp)
print(cnt)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
a, b = map(int, input().split())
c = input().split()
d = []
for i in range(a - b + 1):
	h = 0
	for j in range(b):
		h += int(c[i + j])
	d.append(h)
e = 0
g = d.index(max(d))
for i in range(b):
	f = int(c[i + g])
	d = 0
	for j in range(f):
		d += (j + 1)
	e += d / f
print(e)

### FIXED CODE ###

# -*- coding: utf-8 -*-
a, b = map(int, input().split())
c = list(map(int, input().split()))
d = [(i + 1) / 2 for i in c]
e = sum(d[:b])
f = e
for i in range(a - b):
	f -= d[i]
	f += d[i + b]
	if f > e:
		e = f
print(e)
### BUGGY CODE ###

N=int(input())
a=list(map(int,input().split()))
Q=int(input())
B=[0]*Q
C=[0]*Q
for i in range(Q):
	B[i],C[i]=map(int,input().split())
import collections
A=collections.Counter(a)
for i in range(Q):
	if B[i] in A:
		f=A.pop(B[i])
		if C[i] in A:
			g=A[C[i]]
			h=f+g
		else:
			h=f
		A[C[i]]=h
	S=0
	for k,v in A.items():
		S=S+k*v
	print(S)

### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
Q=int(input())
B=[0]*Q
C=[0]*Q
for i in range(Q):
	B[i],C[i]=map(int,input().split())
import collections
A=collections.Counter(a)
S=0
for j in range(N):
	S=S+a[j]
for i in range(Q):
	if B[i] in A:
		f=A.pop(B[i])
		if C[i] in A:
			g=A[C[i]]
			h=f+g
		else:
			h=f
		A[C[i]]=h
	else:
		f=0
	S=S+f*(C[i]-B[i])
	print(S)
### BUGGY CODE ###

L, R = map(int, input().split())

ans = 100100100100
for i in range(L, R+1):
    for j in range(L, i):
        ans = min(ans, (i*j)%2019)
    """
    if ans == 0:
        print(ans)
        exit()
    """
print(ans)

### FIXED CODE ###

L, R = map(int, input().split())

ans = 100100100100
for i in range(L, R+1):
    for j in range(L, i):
        ans = min(ans, (i*j)%2019)
    if ans == 0:
        print(ans)
        exit()
print(ans)
### BUGGY CODE ###

import sys
import collections
input = lambda: sys.stdin.readline().rstrip()

def main():
    n = int(input())
    s = [input() for _ in range(n)]
    cnt = collections.Counter(s)
    d = sorted([k for k, v in cnt.items() if v == max(cnt.values())])
    for i in d:
        print(i)    

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import collections
input = lambda: sys.stdin.readline().rstrip()

def main():
    n = int(input())
    s = [input() for _ in range(n)]
    cnt = collections.Counter(s)
    values, counts = zip(*cnt.most_common())
    d = sorted(values[:counts.count(counts[0])])
    print(*d, sep='\n')

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

n = int(input())

S = []
cnt = {}
for i in range(n):
    s = input()
    s = sorted(list(s))
    s = str(s)
    if s not in S:
        S.append(s)
        cnt[s] = 1
    else:
        cnt[s] += 1

ans = 0
for s in S:
    c = cnt[s]
    for i in range(c):
        ans += i
print(ans)


### FIXED CODE ###

n = int(input())

cnt = {}
for i in range(n):
    s = input()
    s = sorted(list(s))
    s = str(s)
    if s not in cnt:
        cnt[s] = 0
    else:
        cnt[s] += 1

ans = 0
for c in cnt.values():
    ans += c * (c+1) // 2

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

N,u,v = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
    

dicT = {u-1:0}
dicA = {v-1:0}
ans = 0
while len(dicT) > 0 and len(dicA) > 0:
    tempT = {}
    for t in dicT:
        for e in edge[t]:
            if e not in dicA:
                tempT[e] = 0
                
    dicT = tempT
    if not dicT:
        break
    tempA = {}
    for a in dicA:
        for e in edge[a]:
            if e in dicT:
                dicT[e] = 1
            else:
                tempA[e] = 0
    
    dicA = tempA
    
    tempT = {}
    for t in dicT:
        if dicT[t] == 0:
            tempT[t] = 0
            
    dicT = tempT
    ans += 1
    
print(ans)

### FIXED CODE ###

N,u,v = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(N-1):
    a,b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
    

import heapq

def dijkstra(s):
    d = [10**6]*N
    used = [True]*N
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in E[s]:
        heapq.heappush(edgelist, [1, e])
    while edgelist:
        t = heapq.heappop(edgelist)
        if not used[t[1]]:
            continue
        used[t[1]] = False
        d[t[1]] = t[0]
        for e in E[t[1]]:
            if used[e]:
                heapq.heappush(edgelist, [t[0]+1, e])
                
    return d

T = dijkstra(u-1)
A = dijkstra(v-1)

ans = 0
for i in range(N):
    if T[i] < A[i]:
        ans = max(ans, A[i])
        idx = i
        
print(ans-1)
### BUGGY CODE ###

S = input()
T = input()

# 例abcdefg...のように文字列が1対1の矢印関係の場合は、
# どのような場合でも置き換えできる。問題は同じ文字が複数現れる場合

# S上に同じ文字sのある場所には
# T上にも同じ文字tがなくてはならない
# つまり、同じ値になっているインデックスの集合を取れば
# 全部同じになっているはず

# 文字種ごとにインデックスの集合を求める
ns = len(S)
indexS = {}
for i in range(ns):
    s = S[i]
    if s in indexS:
        indexS[s].append(i)
    else:
        indexS[s] = [i]
indexT = {}
for i in range(ns):
    t = T[i]
    if t in indexT:
        indexT[t].append(i)
    else:
        indexT[t] = [i]
# 先頭の文字から、インデックスの集合が等しいかチェック
for s, t in zip(S, T):
    i_s = indexS[s]
    i_t = indexT[t]
    if i_s != i_t:
        print("No")
        break
else:
    print("Yes")


### FIXED CODE ###

S = input()
T = input()

# 例abcdefg...のように文字列が1対1の矢印関係の場合は、
# どのような場合でも置き換えできる。問題は同じ文字が複数現れる場合

# S上に同じ文字sのある場所には
# T上にも同じ文字tがなくてはならない
# つまり、同じ値になっているインデックスの集合を取れば
# 全部同じになっているはず

# 文字種ごとにインデックスの集合を求める
ns = len(S)
indexS = {}
for i in range(ns):
    s = S[i]
    if s in indexS:
        indexS[s].append(i)
    else:
        indexS[s] = [i]
indexT = {}
for i in range(ns):
    t = T[i]
    if t in indexT:
        indexT[t].append(i)
    else:
        indexT[t] = [i]
# 先頭の文字から、インデックスの集合が等しいかチェック
for i in range(ns):
    s = S[i]
    t = T[i]
    i_s = len(indexS[s])
    i_t = len(indexT[t])
    if i_s != i_t:
        print("No")
        break
else:
    print("Yes")
### BUGGY CODE ###

n =int(input())
values = list(map(int, input().split()))
a = 1

for i in range(n):
  a = a*values[i]

if  a <= 10**18:
  print(a)
else:
  print(-1)

### FIXED CODE ###

n = int(input())
values =list(map(int, input().split()))
a=1
t = 10**18
for i in range(n):
  if values[i] == 0:
    a = 0
    break
  if a > t:
    continue
  else:
    a=a*values[i]
 
if a <= t:
  print(a)
else:
  print(-1)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 9)
M = 10 ** 9 + 7


cache = {}
n = int(input())
a = list(map(int, input().split()))
assert len(a) == n + 1

b = [None] * (n + 1)
d1, d2 = -1, -1
for i in range(n + 1):
    if b[a[i]] is None:
        b[a[i]] = i
    else:
        d1 = b[a[i]]
        d2 = i
        break
assert d1 >= 0 and d2 >= 0 and a[d1] == a[d2]


def comb(n, k):
    if k > n:
        return 0
    if k > n - k:
        k = n - k
    if k == 0:
        return 1
    if k == 1:
        return n
    if (n, k) in cache:
        return cache[n, k]
    res = comb(n - 1, k) + comb(n - 1, k - 1)
    cache[n, k] = res
    return res


for k in range(1, n + 2):
    ans = comb(n + 1, k) - comb(n - d2 + d1, k - 1)
    print(ans % M)


### FIXED CODE ###

import sys

input = sys.stdin.readline
M = 10 ** 9 + 7

n = int(input())
a = list(map(int, input().split()))
assert len(a) == n + 1

b = [None] * (n + 1)
d1, d2 = -1, -1
for i in range(n + 1):
    if b[a[i]] is None:
        b[a[i]] = i
    else:
        d1 = b[a[i]]
        d2 = i
        break
assert d1 >= 0 and d2 >= 0 and a[d1] == a[d2]


a, b, ik = n + 1, 1, 1
for k in range(1, n + 2):
    ans = (a - b) % M
    print(ans)
    b = b * (n + 1 - d2 + d1 - k) * ik % M
    ik = pow(k + 1, M - 2, M)
    a = a * (n + 1 - k) * ik % M
### BUGGY CODE ###

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))

    numdct = {}
    for i in range(n):
        for div in make_divisors(a[i]):
            if(not div in numdct):
                numdct[div] = 0
            numdct[div] += 1
    
    numlist = sorted(numdct.items(), key=lambda x: -x[1])

    maxnum = 0
    for item in numlist:
        if(item[1] >= n - 1):
            if(maxnum <= item[0]):
                maxnum = item[0]
        else:
            break

    print(maxnum)


### FIXED CODE ###


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))

    numdct = {}
    for i in range(2):
        for div in make_divisors(a[i]):
            if(not div in numdct):
                numdct[div] = 0
            numdct[div] += 1

    dellist = []
    for i in range(2, n):
        for num in numdct.keys():
            if(a[i] % num != 0):
                numdct[num] -= 1
                if(numdct[num] == 0):
                    dellist.append(num)
        for d in dellist:
            del numdct[d]
        dellist.clear()
    
    numlist = sorted(numdct.items(), key=lambda x: -x[1])

    maxnum = 0
    for item in numlist:
        if(item[1] > 0):
            if(maxnum <= item[0]):
                maxnum = item[0]
        else:
            break

    print(maxnum)
### BUGGY CODE ###

def solve(i,m):
    global n
    global A
    if m == 0 :
        return True
    elif m < 0:
        return False
    elif i >= n :
        return False
    else:
        return (solve(i+1,m) or solve(i+1,m-A[i]))

global n
global A
n = int(input())
st = input()
A = list(map(int,st.split()))
A.sort(reverse = True)
input()     # don't use the num of ans pattern. dumping!
st = input()
ans = list(map(int,st.split()))

for x in ans:
    if(solve(0,x) == True):
        print('yes')
    else:
        print('no')

### FIXED CODE ###

is_able_make = [False]*2000

input()

A = [ int( val ) for val in input().rstrip().split( ' ' ) ]
q = int(input())
M = [ int( val ) for val in input().rstrip().split( ' ' ) ]

for i in A:
    for j in range(2000-i,0,-1):
        if is_able_make[j] == True:
            is_able_make[i+j] = True
    is_able_make[i] = True

for x in M:
    if(is_able_make[x] == True):
        print('yes')
    else:
        print('no')
### BUGGY CODE ###

n, k = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]

if n <= k:
    k = n-1

dp=[0]*(n)
for i in range(k+1):
    dp[i] = abs(h[0]-h[i])

dp2=[0]*(k)

for i in range(k+1,n):
    for j in range(1,k+1):
        dp2[j-1]=abs(h[i] - h[i - j]) +dp[i-j]

    dp[i]=min(dp2)

print(dp[n-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
 
DP = [0]
for i in range(N-1):
    act = float("inf")
    for k in range(K):
        if i-k < 0 : continue
        act = min(DP[-1-k] + abs(h[i-k]-h[i+1]) , act)
    DP += [act]
 
print(DP[-1])
### BUGGY CODE ###

from copy import deepcopy

def move(A,now):
    return A[now-1]

N, K = map(int,input().split())
A = list(map(int,input().split()))
now = 1
dp  = [deepcopy([0 for _ in range(N)]) for _ in range(N)]
history = []
count = 0
while True:
    history.append(now)
    next_pos = move(A,now)
    if dp[now-1][next_pos-1] == 0:
        dp[now-1][next_pos-1] = 1
    else:
        remainder_array = history[history.index(next_pos):]
        print(remainder_array[(K - history.index(next_pos))%len(remainder_array)])
        break
    if count == K:
        print(now)
        break
    now = next_pos


### FIXED CODE ###

from collections import defaultdict

N,K = map(int,input().split())
A = list(map(int,input().split()))
position = 1
past_path = defaultdict(lambda : -1)
loop_pos = -1

def move(position):
	return A[position-1]

for i in range(1,K+1):
	if(past_path[position] != -1):
		loop_pos = past_path[position]
		break
	past_path[position] = i-1
	position = move(position)

new_past_path = defaultdict(lambda : -1)
for k,v in past_path.items():
	if v >= loop_pos:
		new_past_path[v-loop_pos] = k

if loop_pos != -1:
	print(new_past_path[(K-loop_pos)%len(new_past_path)])
else:
	print(position)
### BUGGY CODE ###

n,m,q=map(int,input().split())
train=[[0]*n for i in range(n)]
for i in range(m):
    l,r=map(int,input().split())
    train[l-1][r-1]+=1
for i in range(n):
    for j in range(n-1):
        train[i][j+1]+=train[i][j]
for i in range(q):
    p,q_=map(int,input().split())
    ans=0
    for j in range(p-1,q_):
        ans+=train[j][q_-1]
    print(ans)



### FIXED CODE ###

n,m,q=map(int,input().split())
train=[[0]*n for i in range(n)]
for i in range(m):
    l,r=map(int,input().split())
    train[l-1][r-1]+=1
for i in range(n):
    for j in range(n-1):
        train[i][j+1]+=train[i][j]
for i in range(q):
    p,q_=map(int,input().split())
    ans=0
    for j in range(p-1,q_):
        ans+=train[j][q_-1]
    print(ans)
### BUGGY CODE ###


def check1(a):
  sum = 0
  for i in range(len(a)):
    if(i % 2 == 0):
      sum += a[i]
      if(sum >= 0):
        return (i, -1)
    else:
      sum += a[i]
      if(sum <= 0):
        return (i, 1)
  return True

def check2(a):
  sum = 0
  for i in range(len(a)):
    if(i % 2 == 0):
      sum += a[i]
      if(sum <= 0):
        return (i, 1)
    else:
      sum += a[i]
      if(sum >= 0):
        return (i, -1)
  return True



n = input()
b = input().split()
a = [int(b[i]) for i in range(len(b))]
a2 = list(a)

ans1 = 0
ans2 = 0

while(True):
  c = check1(a)
  if(c == True):
    break

  a[c[0]] += c[1]
  ans1 += 1


while(True):
  c = check2(a2)
  if(check2(a2) == True):
    break
  a2[c[0]] += c[1]
  ans2 += 1


print(ans1) if(ans1<ans2) else print(ans2)

### FIXED CODE ###


def check1(a):
  sum = 0
  ans = 0
  for i in range(len(a)):
    if(i % 2 == 0):
      sum += a[i]
      if(sum >= 0):
        a[i] -= abs(sum)+1
        ans += abs(sum)+1
        sum -= abs(sum)+1
    else:
      sum += a[i]
      if(sum <= 0):
        a[i] += abs(sum)+1
        ans += abs(sum)+1
        sum += abs(sum)+1
  return ans

def check2(a):
  sum = 0
  ans = 0
  for i in range(len(a)):
    if(i % 2 == 0):
      sum += a[i]
      if(sum <= 0):
        a[i] += abs(sum)+1
        ans += abs(sum)+1
        sum += abs(sum)+1
    else:
      sum += a[i]
      if(sum >= 0):
        a[i] -= abs(sum)+1
        ans += abs(sum)+1
        sum -= abs(sum)+1
  return ans



n = input()
b = input().split()
a = [int(b[i]) for i in range(len(b))]
a2 = list(a)

ans1 = check1(a)
ans2 = check2(a2)


print(ans1) if(ans1<ans2) else print(ans2)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[]

for i in a:
    b.append(i)
    b=list(reversed(b))
bstr=' '.join(str(x) for x in b)
print(bstr)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[]

i=n-1
while i>=0:
    b.append(a[i])
    i-=2

i=n%2
while i<n:
    b.append(a[i])
    i+=2

bstr=" ".join(str(x) for x in b)
print(bstr)
### BUGGY CODE ###

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

for i in range(q):
    b,c = bc[i][0],bc[i][1]
    for j in range(len(a)):
        if a[j] == b:
            a[j] = c
    print(sum(a))


### FIXED CODE ###


  
def main():
    n = int(input())
    a = list(map(int, input().split()))
    q = int(input())
    bc =[list(map(int, input().split())) for _ in range(q)]
    temp = [0] * (10**5 + 1)
    
    for i in a:
        temp[i] += 1
    ans = sum(a)
    for i in range(q):
        b,c = bc[i][0],bc[i][1]
        ans = ans - temp[b] * b + temp[b] * c 
        print(ans)
        temp[c] += temp[b]
        temp[b] = 0
if __name__ == "__main__":
    main()