Harryxun/stf_run huggingface dataset:
n,m=(int(i) for i in input().split())
a=0
b=0
for i in range(m):
  l,r=(int(g) for g in input().split())
  if l>a,r<b:
    a=l
    b=r
  elif l>a and r>=b:
    a=l
  elif r<b and l<=a:
    b=r
if n>a and n<b:
  print(n-a)
elif n>a and n>=b:
  print(b-a)
else:
  print(0)


### FIXED CODE ###

n,m=(int(i) for i in input().split())
a=0
b=10**6
for i in range(m):
  l,r=(int(j) for j in input().split())
  if l>a and r<b:
    a=l
    b=r
  elif l>a and r>=b:
    a=l
  elif r<b and l<=a:
    b=r
if b>=a:
	if n>=a and n<b:
  		print(n-a+1)
	elif n>=a and n>=b:
  		print(b-a+1)
	elif n<a:
  		print(0)
else:
  	print(0)
N, Q = map(int, input().split())
tree = [[] for _ in range(N+1)]
for i in range(N-1):
  a,b = map(int, input().split())
  tree[a].append(b)

counter = [0]*(N+1)
def dfs(p,x):
  counter[p] += x
  if len(tree[p])==0:
    return None
  for q in tree[p]:
    dfs(q,x)
  return None

for i in range(Q):
  p,x = map(int, input().split())
  dfs(p,x)
  
for i in range(1,N+1):
  print(counter[i],end=' ')

### FIXED CODE ###

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

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

from collections import deque

visited = [False]*N
d = deque([0])
while len(d)>0:
    v = d.popleft()
    visited[v]= True
    for u in edge[v]:
        if visited[u]==False:
            ans[u] += ans[v]
            visited[u]=True
            d.append(u)

print(*ans, sep=' ')
for okashi_number in range(k):
	di = int(input())
	D = map(int,input().split())
	for x in range(di)
		A[[x]-1] = 1

for i in range(N):
	if A[i] == 0:
	print(A[i])


### FIXED CODE ###

S = input()

if S == "ABC":
	print("ARC")
else:
	print("ABC")
# -*- coding: utf-8 -*-

def main():
    flag = True
    input_num = int(input())
    pre_ans = []
    sum_num = 0

    while flag:
        chushutsu = input_num % 10
        sum_num += chushutsu
        input_num = (input_num - chushutsu) / 10
        if input_num == 0:
            flag = False

    if sum_num % 9 == 0:
        print('Yes')

    else:
        print('No')

if __name__ == '__main__':
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-

def main():
    input_num = input()
    sum_num = 0

    for i in range(len(input_num)):
        chushutsu = int(input_num[i])
        sum_num += chushutsu
    
    if sum_num % 9 == 0:
        print('Yes')

    else:
        print('No')

if __name__ == '__main__':
    main()
N,A = input().split()

if (N / 500) >=1 and (N % 500) =< A:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

N = int(input())
A = int(input())

if N%500 <= A:
  print("Yes")
else:
  print("No")
a = raw_input()
b, c, d = a.split()
B = int(b)
C = int(c); D = int(d)

if x <= y <= z: print x, y, z

### FIXED CODE ###

a = raw_input()
b, c, d = a.split()
x = int(b)
y = int(c); z = int(d)
  
if x <= y <= z: print x, y, z
elif x <= y > z: print x, z, y
elif y <= x <= z: print y, x, z
elif y < z <= x: print y, z, x
elif y < x: print z, y, x
else: print z, x, y
nab = [int(input()) for _ in range(3)]

if nab[0] == 1:
  print('Hello World')
else:
  print(nab[1]+nab[2])

### FIXED CODE ###

n = int(input())

if n == 1:
  print('Hello World')
else:
  print(int(input()) + int(input()))
N = int(input())
H = list(map(int,input().split()))
ans = []
count = 0
for i in range(1,N):
  if H[i-1] < H[i]:
    ans.append(count)
    count = 0
  elif H[i-1] >= H[i]:
    count += 1
  if i == N-1:
    ans.append(count)

print(max(ans))

### FIXED CODE ###

N = int(input())
H = list(map(int,input().split()))
ans = []
count = 0
if len(H) == 1:
  print(0)
  exit()
for i in range(1,N):
  if H[i-1] < H[i]:
    ans.append(count)
    count = 0
  elif H[i-1] >= H[i]:
    count += 1
  if i == N-1:
    ans.append(count)

print(max(ans))
import sys
import math
from collections import deque
import copy

H, W = map(int, input().split())
maps2 = deque([deque(["#" for _ in range(W + 2)])])
MAX = 0

for _ in range(H):
    temp = deque(input())
    temp.appendleft("#")
    temp.append("#")
    maps2.append(temp)
maps2.append(deque(["#" for _ in range(W + 2)]))

for i in range(1, H + 1):
    for l in range(1, W + 1):
        if maps2[i][l] != "#":
            maps = copy.deepcopy(maps2)
            pos = [[i, l, 0]]
            while len(pos) > 0:

                y, x, depth = pos.pop(0)
                if depth > MAX:
                    MAX = depth

                if maps[y + 1][x] == ".":
                    pos.append([y + 1, x, depth + 1])
                    map[y + 1][x] = "a"
                if maps[y][x + 1] == ".":
                    pos.append([y, x + 1, depth + 1])
                    map[y][x + 1] = "a"
                if maps[y - 1][x] == ".":
                    pos.append([y - 1, x, depth + 1])
                    map[y - 1][x] = "a"
                if maps[y][x - 1] == ".":
                    pos.append([y, x - 1, depth + 1])
                    map[y][x - 1] = "a"
print(MAX)


### FIXED CODE ###

import sys
import math
from collections import deque
import copy

H, W = map(int, input().split())
maps2 = deque([deque(["#" for _ in range(W + 2)])])
MAX = 0

for _ in range(H):
    temp = deque(input())
    temp.appendleft("#")
    temp.append("#")
    maps2.append(temp)
maps2.append(deque(["#" for _ in range(W + 2)]))

for i in range(1, H + 1):
    for l in range(1, W + 1):
        if maps2[i][l] != "#":
            maps = copy.deepcopy(maps2)
            pos = [[i, l, 0]]
            maps[i][l] = "a"
            while len(pos) > 0:

                y, x, depth = pos.pop(0)
                if depth > MAX:
                    MAX = depth

                if maps[y + 1][x] == ".":
                    pos.append([y + 1, x, depth + 1])
                    maps[y + 1][x] = "a"
                if maps[y][x + 1] == ".":
                    pos.append([y, x + 1, depth + 1])
                    maps[y][x + 1] = "a"
                if maps[y - 1][x] == ".":
                    pos.append([y - 1, x, depth + 1])
                    maps[y - 1][x] = "a"
                if maps[y][x - 1] == ".":
                    pos.append([y, x - 1, depth + 1])
                    maps[y][x - 1] = "a"
print(MAX)
int(num),int(val) = input().split(" ")

if num < 10:
	print val + 100*(10-num)
else:
	print val


### FIXED CODE ###

def main():
	num,val = input().split(" ")
	num = int(num)
	val = int(val)

	if num < 10:
		print(val + 100*(10-num))
	else:
		print(val)

if __name__ == "__main__":
    main()
(a, b, c, d, e, f) = list(map(int, input().split()))
a *= 100
b *= 100

n = [[0, 0] for _ in range(f + 1)]
n[a][0] = a
for i in range(f + 1 - a):
    if n[i][0] != 0:
        n[i + a][0] = n[i][0] + a
n[b][0] = b
for i in range(f + 1 - b):
    if n[i][0] != 0:
        n[i + b][0] = n[i][0] + b
for i in range(f + 1 - c):
    if n[i][0] == 0:
        continue
    tmpt = n[i][0] / 100
    if (c + n[i][1]) / tmpt <= e and n[i + c][1] / (i + c) < (n[i][1] + c) / (i + c):
        n[i + c][0] = n[i][0]
        n[i + c][1] = n[i][1] + c
for i in range(f + 1 - d):
    if n[i][0] == 0:
        continue
    tmpt = n[i][0] / 100
    if (d + n[i][1]) / tmpt <= e and n[i + d][1] / (i + d) < (n[i][1] + d) / (i + d):
        n[i + d][0] = n[i][0]
        n[i + d][1] = n[i][1] + d
maxp = [0, 100, 0]
for i in range(len(n)):
    if(n[i][1] != 0 and maxp[0] < n[i][1] / i):
        maxp = [n[i][1] / i] + n[i]
print(str(maxp[1] + maxp[2]) + ' ' + str(maxp[2]))

### FIXED CODE ###

(a, b, c, d, e, f) = list(map(int, input().split()))
a *= 100
b *= 100

n = [[0, 0] for _ in range(f + 1)]
n[a][0] = a
for i in range(f + 1 - a):
    if n[i][0] != 0:
        n[i + a][0] = n[i][0] + a
if f >= b:
    n[b][0] = b
    for i in range(f + 1 - b):
        if n[i][0] != 0:
            n[i + b][0] = n[i][0] + b
for i in range(f + 1 - c):
    if n[i][0] == 0:
        continue
    tmpt = n[i][0] / 100
    if (c + n[i][1]) / tmpt <= e and n[i + c][1] / (i + c) < (n[i][1] + c) / (i + c):
            n[i + c][0] = n[i][0]
            n[i + c][1] = n[i][1] + c
for i in range(f + 1 - d):
    if n[i][0] == 0:
        continue
    tmpt = n[i][0] / 100
    if (d + n[i][1]) / tmpt <= e and n[i + d][1] / (i + d) < (n[i][1] + d) / (i + d):
            n[i + d][0] = n[i][0]
            n[i + d][1] = n[i][1] + d
maxp = [0, a, 0]
for i in range(len(n)):
    if(n[i][1] != 0 and maxp[0] < n[i][1] / i):
        maxp = [n[i][1] / i] + n[i]
print(str(maxp[1] + maxp[2]) + ' ' + str(maxp[2]))
from fractions import gcd
a,b,k = map(int,input().split())
mods = []
for i in range(1,min(a,b)):
    if a % i == 0 and b % i == 0:
        mods.append(i)
mods.sort(reverse=True)
if len(mods) == 1:
    print(mods[0])
else:
    print(mods[k-1])

### FIXED CODE ###

a,b,k = map(int,input().split())
cd = []
for i in range(1,min(a,b)+1):
    if a % i == 0:
        if b % i == 0:
            cd.append(i)
cd.sort(reverse=True)
print(cd[k-1])
n = int(input())

xyh = [list(map(int, input().split())) for i in range(n)]
if xyh[0][2]:
    x,y,h = xyh[0]
for i in range(101):
    for j in range(101):
        k = h + abs(i - x) + abs(j - y)
        if all(h == max(k - abs(i - x) - abs(j - y), 0) for x, y, h in xyh):
            print(i, j, k)

### FIXED CODE ###

n = int(input())

xyh = [list(map(int, input().split())) for i in range(n)]
if xyh[0][2]:
    x,y,h = xyh[0]
if xyh[1][2]:
    x,y,h = xyh[1]
if xyh[-1][2]:
    x,y,h = xyh[-1]
for i in range(101):
    for j in range(101):
        k = h + abs(i - x) + abs(j - y)
        if all(h == max(k - abs(i - x) - abs(j - y), 0) for x, y, h in xyh):
            print(i, j, k)
ソースコード 

Copy
Copy
N = int(input())
count = 0
D = 0
task = [list(map(int, input().split())) for _ in range(N)]
task = sorted(task, key = lambda x:x[1])

for i in range(N):
  count += task[i][0]
  if count > task[i][1]:
    print("No")
    D = 1
    break
if D== 0:
  print("Yes")

### FIXED CODE ###


N = int(input())
count = 0
D = 0
task = [list(map(int, input().split())) for _ in range(N)]
task = sorted(task, key = lambda x:x[1])
for i in range(N):
  count += task[i][0]
  if count > task[i][1]:
    print("No")
    D = 1
    break
if D== 0:
  print("Yes")
import math
from functools import reduce
n=int(input())
a=list(map(int,input().split()))


l=[0]
r=[0]
for i in range(0,n):
    l.append(math.gcd(l[i],a[i]))
    r.append(math.gcd(r[i],a[n-i-1]))

#print(l,r)
r=r[::-1]
ans=[]
for i in range(n):
    ans.append(math.gcd(l[i],r[i+1]))
print(max(ans))

### FIXED CODE ###

import fractions
from functools import reduce
n=int(input())
a=list(map(int,input().split()))


l=[0]
r=[0]
for i in range(0,n):
    l.append(fractions.gcd(l[i],a[i]))
    r.append(fractions.gcd(r[i],a[n-i-1]))

#print(l,r)
r=r[::-1]
ans=[]
for i in range(n):
    ans.append(fractions.gcd(l[i],r[i+1]))
print(max(ans))
import math

a = int(input())
b = int(input())

c = (a + b)/2 

print(math.cell(c))

### FIXED CODE ###

import math
a,b = map(int,input().split())
print(math.ceil((a+b)/2))
N = int(input())
s = [input() for i in range(N)]
t = [0]*(N-1)
 
for n in range(N-1):
  t[n] = s[n] - s[n+1]
  if t[n] <= 0: 
    continue
  else:
    s[n+1] += t[n]
 
print(min(t))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split())) 
ans = 0
 
for n in range(N-1):
  t = A[n] - A[n+1]
  if t <= 0: continue
  else:
    A[n+1] += t
    ans += t

print(ans)
S = input()

A_left=[0]
C_left=[0]
Q_left=[0]

for (i,s) in enumerate(S):
    if s == "A":
        A_left.append(A_left[i]+1)
        C_left.append(C_left[i])
        Q_left.append(Q_left[i])
    elif s == "C":
        A_left.append(A_left[i])
        C_left.append(C_left[i]+1)
        Q_left.append(Q_left[i])
    elif s == "?":
        A_left.append(A_left[i])
        C_left.append(C_left[i])
        Q_left.append(Q_left[i]+1)
    else:
        A_left.append(A_left[i])
        C_left.append(C_left[i])
        Q_left.append(Q_left[i])

A_right = []
C_right = []
Q_right = []
for i in range(len(S)):
    A_right.append(A_left[-1] - A_left[i+1])
    C_right.append(C_left[-1] - C_left[i+1])
    Q_right.append(Q_left[-1] - Q_left[i+1])

ans = 0
for (i,s) in enumerate(S):
    if s == "B":
        ans = (ans + A_left[i] * C_right[i] * pow(3,Q_left[-1],10**9+7)) % (10**9+7)
        ans = (ans + (Q_left[i] * C_right[i] + A_left[i] * Q_right[i]) * pow(3,(Q_left[-1]-1),10**9+7)) % (10**9+7)
        ans = (ans + (Q_left[i] * Q_right[i]) * pow(3,(Q_left[-1]-2),10**9+7)) % (10**9+7)
    elif s == "?":
        ans = (ans + A_left[i] * C_right[i] * pow(3,(Q_left[-1]-1),10**9+7)) % (10**9+7)
        ans = (ans + (Q_left[i] * C_right[i] + A_left[i] * Q_right[i]) * pow(3,(Q_left[-1]-2),10**9+7)) % (10**9+7)
        ans = (ans + (Q_left[i] * Q_right[i]) * pow(3,(Q_left[-1]-3),10**9+7)) % (10**9+7)

print(ans)


### FIXED CODE ###

S = input()

A_left=[0]
C_left=[0]
Q_left=[0]

for (i,s) in enumerate(S):
    if s == "A":
        A_left.append(A_left[i]+1)
        C_left.append(C_left[i])
        Q_left.append(Q_left[i])
    elif s == "C":
        A_left.append(A_left[i])
        C_left.append(C_left[i]+1)
        Q_left.append(Q_left[i])
    elif s == "?":
        A_left.append(A_left[i])
        C_left.append(C_left[i])
        Q_left.append(Q_left[i]+1)
    else:
        A_left.append(A_left[i])
        C_left.append(C_left[i])
        Q_left.append(Q_left[i])

A_right = []
C_right = []
Q_right = []
for i in range(len(S)):
    A_right.append(A_left[-1] - A_left[i+1])
    C_right.append(C_left[-1] - C_left[i+1])
    Q_right.append(Q_left[-1] - Q_left[i+1])

ans = 0
for (i,s) in enumerate(S):
    if s == "B":
        ans = (ans + A_left[i] * C_right[i] * pow(3,Q_left[-1],10**9+7)) % (10**9+7)
        if Q_left[-1]>=1:
            ans = (ans + (Q_left[i] * C_right[i] + A_left[i] * Q_right[i]) * pow(3,(Q_left[-1]-1),10**9+7)) % (10**9+7)
        if Q_left[-1]>=2:
            ans = (ans + (Q_left[i] * Q_right[i]) * pow(3,(Q_left[-1]-2),10**9+7)) % (10**9+7)
    elif s == "?":
        if Q_left[-1]>=1:
            ans = (ans + A_left[i] * C_right[i] * pow(3,(Q_left[-1]-1),10**9+7)) % (10**9+7)
        if Q_left[-1]>=2:
            ans = (ans + (Q_left[i] * C_right[i] + A_left[i] * Q_right[i]) * pow(3,(Q_left[-1]-2),10**9+7)) % (10**9+7)
        if Q_left[-1]>=3:
            ans = (ans + (Q_left[i] * Q_right[i]) * pow(3,(Q_left[-1]-3),10**9+7)) % (10**9+7)

print(ans)
# sys.stdin.readline()
import sys
input = sys.stdin.readline

n=int(input())
num=list(map(int,input().split()))
ido=0
ans=[]
for i in range(n):
    syoki=num[i]
    for j in range(i+1,n):
        if syoki>=num[j] and not j==n-1:
            syoki=num[j]
            ido=ido+1
        elif syoki>=num[j] and j==n-1:
            ans.append(ido+1)
            ido=0
        elif syoki<num[j] or j==n-1:
            ans.append(ido)
            ido=0
            break

print(max(ans))


### FIXED CODE ###

# sys.stdin.readline()
import sys
input = sys.stdin.readline

n=int(input())
num=list(map(int,input().split()))
ido=0
ans=[0]
for i in range(n-1):
    if num[i]>=num[i+1] and i==n-2:
        ans.append(ido+1)
    elif num[i]>=num[i+1]:
        ido=ido+1
    elif num[i]<num[i+1]:
        ans.append(ido+0)
        ido=0

print(max(ans))
N = int(input())
A = [int(i) for i in input().split()]
for i in range(N-1):
  if A[i] > A[i+1]:
    S = A[i] - A[i+1]
    K = A[i+1] + abs(S)
  else:
    S = A[i] - A[i+1]
    K = abs(S)
print(K)


### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
K = 0
for i in range(N-1):
  if A[i] > A[i+1]:
    S = A[i] - A[i+1]
    # リストの前の最大値を取得して比較しないといけない。
    A[i+1] += S
    K += S
  else:
    pass
print(K)
x,n = map(int,input().split())

p = list(map(int,input().split()))
s = []

for i in range(101):
  if i not in p:
    s.append(i)

k = abs(x-s[0])
del s[0]
for j in range(100-n):
  if abs(x-s[j]) < k:
    k = abs(x-s[j])
  else:
    answer = s[j-1]
    break
else:
  answer = s[100-n-1]
print(answer)




    

### FIXED CODE ###

x,n =map(int,input().split())
p = list(map(int,input().split()))

gap = x
ans = 0

for y in range(0,102):
  if y not in p:
    if abs(x - y) < gap:
      gap = abs(x-y)
      ans = y
      
print(ans)
rainy_days = input('3日間で連続した雨の日は？:')
if rainy_days = rrr:
    print(3)
elif rainy_days == rrs or srr:
    print(2)
elif rainy_days == rsr or rss or ssr or srs:
    print(1)
elif rainy_days == sss:
    print(0)


### FIXED CODE ###

r = input()
if r == 'RRR':
    print(3)
elif r == 'RRS' or r == 'SRR':
    print(2)
elif r == 'RSR' or r == 'RSS' or r =='SSR' or r =='SRS':
    print(1)
elif r == 'SSS':
    print(0)
s = input()
print('Yes' if s[2]==s[3] && s[4]==s[5] else 'No')

### FIXED CODE ###

s = input()
print('Yes' if s[2]==s[3] and s[4]==s[5] else 'No')
N = int(input())
*A, = map(int,input().split())

mod = 10**9+7

ans = 3
dp = [1,0,0]
for a in A[1:]:
    ans *= dp.count(a)
    dp[dp.index(a)] += 1
    ans %= mod
print(ans)

### FIXED CODE ###

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

mod = 10**9+7

ans = 3
if A[0]!=0: ans = 0
dp = [1,0,0]
for a in A[1:]:
    ans *= dp.count(a)
    ans %= mod
    if ans == 0: break
    dp[dp.index(a)] += 1
print(ans)
import sympy as sym
N = 5
A = [sym.lucas(x) for x in range(N)]
print(A[N])

### FIXED CODE ###

N = int(input())

L = [2, 1]
for i in range(2, N+1):
    L.append(L[i-1] + L[i-2])
    
print(L[N])
S = input()
n = len(S)
p = 0
if S[0] == 'A':
    p = 1
s = []
for i in range(2,n-1):
    s.append(S[i])
q = 0
if s.count('C') == 1:
    q = 1
s.remove('C')
s.append(S[1])
s.append(S[n-1])
r = 1
for i in range(n-2):
    x = s[i]
    t = ord(x)-97
    if 0<= t <= 25:
        continue
    else:
        r = 0
        break
ans = 'WA'
if p*q*r == 1:
    ans = 'AC'
print(ans)

### FIXED CODE ###

S = input()
n = len(S)
p = 0
if S[0] == 'A':
    p = 1
s = []
for i in range(2,n-1):
    s.append(S[i])
q = 0
if s.count('C') == 1:
    q = 1
if 'C' in s:
    s.remove('C')
s.append(S[1])
s.append(S[n-1])
r = 1
for i in range(n-2):
    x = s[i]
    t = ord(x)-97
    if 0<= t <= 25:
        continue
    else:
        r = 0
        break
ans = 'WA'
if p*q*r == 1:
    ans = 'AC'
print(ans)
import math

base = 998244353

n, a, b, k =  map(int, input().split())

fac = [1] * (n + 1)
rev = [1] * (n + 1)
for i in range(1, n + 1):
    fac[i] = fac[i - 1] * i % base
    rev[i] = pow(fac[i], base -2, base)



def comb(n,r):
    hoge = (fac[n] * rev[r] * rev[n - r] ) % base
    return hoge





count = 0

an = 0 

for an in range(n+1):
    if k - an * a < 0 or (k - an * a) % b != 0:
        continue
    bn = (k -an * a) // b

    count += comb(n, an) * comb(n, bn) % base
    count %= base



print(count)







    



### FIXED CODE ###

import math

base = 998244353

n, a, b, k =  map(int, input().split())

fac = [1] * (n + 1)
rev = [1] * (n + 1)
for i in range(1, n + 1):
    fac[i] = fac[i - 1] * i % base
    rev[i] = pow(fac[i], base -2, base)



def comb(n,r):
    hoge = (fac[n] * rev[r] * rev[n - r] ) % base
    return hoge





count = 0

an = 0 

for an in range(n+1):
    if k - an * a < 0 or (k - an * a) % b != 0:
        continue
    bn = (k -an * a) // b
    if not 0 <= bn <= n:
        continue

    count += comb(n, an) * comb(n, bn) % base
    count %= base



print(count)
N,M=map(int,input().split())
lst=list(map(int,input().split()))
lst.sort()
sum_1=max(lst)-min(lst)
D=[]
for i in range(1,M):
    D.append(lst[i]-lst[i-1])
D.sort(reverse=True)
sum_2=0
for i in range(N-1):
    sum_2+=D[i]
ans=0
ans=sum_1-sum_2
print(ans)


### FIXED CODE ###

N,M=map(int,input().split())
if N>M:
    print(0)
    exit()
lst=list(map(int,input().split()))
lst.sort()
sum_1=max(lst)-min(lst)
D=[]
for i in range(1,M):
    D.append(lst[i]-lst[i-1])
D.sort(reverse=True)
sum_2=0
for i in range(N-1):
    sum_2+=D[i]
ans=0
ans=sum_1-sum_2
print(ans)
from collections import Counter


def resolve():
    N = int(input())
    A = list(input().split())
    Q = int(input())

    C = Counter(A)
    ANS = 0
    for i in C:
        ANS += i * C[i]

    for _ in range(Q):
        B, X = map(int, input().split())
        ANS += X * C[B]
        C[X] += C[B]

        ANS -= B * C[B]
        del(C[B])
        print(ANS)

resolve()

### FIXED CODE ###

from collections import Counter


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

    C = Counter(A)
    ANS = 0
    for i in C:
        ANS += i * C[i]

    for _ in range(Q):
        B, X = map(int, input().split())
        ANS += X * C[B]
        C[X] += C[B]

        ANS -= B * C[B]
        del(C[B])
        print(ANS)

resolve()
import math

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

n = int(input())
a = [0]*n
a = list(map(int, input().split()))
map(lambda x: x-1, a)
ty=[0]*n

for i in range(0, n):
    ty[a[i]]+=1

s = 0

for i in range(0, n):
    if ty[i]>=2:
        s += comb(ty[i], 2, exact=True)

for k in range(0, n):
    if ty[a[k]]==2:
        print(s-1)
    elif ty[a[k]]>2:
        print(s-comb(ty[a[k]], 2, exact=True)+comb(ty[a[k]]-1, 2,exact=True))
    else:
        print(s)

### FIXED CODE ###

import random


def nC2(n):
    return int(n*(n-1)/2)

n = int(input())

a = [0]*n
a = list(map(int, input().split()))
a = [i-1 for i in a]

ty=[0]*n

for i in range(0, n):
    ty[a[i]]+=1

s = 0

for i in range(0, n):
    if ty[i]>=2:
        s += nC2(ty[i])

for k in range(0, n):
    if ty[a[k]]==2:
        print(s-1)
    elif ty[a[k]]>2:
        print(s-nC2(ty[a[k]])+nC2(ty[a[k]]-1))
    else:
        print(s)
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==0:
    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 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)


### 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)