Harryxun/stf_run huggingface dataset:
n,k = map(int,input().split())
a = list(map(int,input().split()))
MOD = 10**9 + 7

ze = []
pl,mi = [],[]
for i in range(n):
    if a[i] < 0:
        ze.append((-a[i],1))
        mi.append(a[i])
    else:
        ze.append((a[i],0))
        pl.append(a[i])
        
ze.sort(reverse = True)
pl.sort(reverse = True)
mi.sort()

one = 0
for i in range(k):
    one += ze[i][1]
    
ans = 1
zero = k-one

if one % 2 == 0:
    for i in range(k):
        ans = ans * ze[i][0] % MOD
    print(ans)
        
elif len(pl) == 0:
    for i in range(k):
        ans = ans * mi[n-1-i] % MOD
    print(ans)
        
else:
    if (zero == len(pl) and one == len(mi)):
        ak = [zero,one]
    elif (zero != len(pl) and one == len(mi)):
        ak = [zero+1,one-1]
    elif zero == len(pl) and one != len(mi):
        ak = [zero-1,one+1]
    else:
        if abs(mi[zero])/pl[one-1] >= pl[one]/abs(mi[zero-1]):
            ak = [zero+1,one-1]
        else:
            ak = [zero-1,one+1]
            
    ans = 1
    for i in range(ak[0]):
        ans = ans * pl[i] % MOD
    for i in range(ak[1]):
        ans = ans * mi[i] % MOD
        
    print(ans)

### FIXED CODE ###

from decimal import *

n,k = map(int,input().split())
a = list(map(int,input().split()))
MOD = 10**9 + 7

ze = []
pl,mi = [],[]
for i in range(n):
    if a[i] < 0:
        ze.append((-a[i],1))
        mi.append(a[i])
    else:
        ze.append((a[i],0))
        pl.append(a[i])
        
ze.sort(reverse = True)
pl.sort(reverse = True)
mi.sort()

one = 0
for i in range(k):
    one += ze[i][1]
    
ans = 1
zero = k-one

if one % 2 == 0:
    for i in range(k):
        ans = ans * ze[i][0] % MOD
    print(ans)
        
elif len(pl) == 0:
    for i in range(k):
        ans = ans * mi[n-1-i] % MOD
    print(ans)
        
else:
    if (zero == len(pl) and one == len(mi)) or len(pl) == 0 or len(mi) == 0:
        ak = [zero,one]
    elif (zero != len(pl) and one == len(mi)) or zero == 0:
        ak = [zero+1,one-1]
    elif zero == len(pl) and one != len(mi) or one == 0:
        ak = [zero-1,one+1]
    else:
        if Decimal(abs(mi[one]))/Decimal(pl[zero-1]) >= Decimal(pl[zero])/Decimal(abs(mi[one-1])):
            ak = [zero-1,one+1]
        else:
            ak = [zero+1,one-1]
            
    ans = 1
    for i in range(ak[0]):
        ans = ans * pl[i] % MOD
    for i in range(ak[1]):
        ans = ans * mi[i] % MOD
        
    print(ans)
N, M = map(int, input().split())
ac = []
wa = 0

for _ in range(M):
  p_str, s = map(str, input().split())
  p = int(p_str)
  if p in ac:
    continue
  if s == 'AC':
    ac.append(p)
    p.sort
  if s == 'WA':
    wa += 1

print(len(ac), wa)


### FIXED CODE ###

N, M = map(int, input().split())
ac = [0] * N
wa = [0] * N

for _ in range(M):
  p_str, s = map(str, input().split())
  p = int(p_str)
  if ac[p-1] == 1:
    continue
  if s == 'AC':
    ac[p-1] = 1
  if s == 'WA':
    wa[p-1] += 1

result = [x * y for (x, y) in zip(ac, wa)]
AC = sum(ac)
WA = sum(result)

print(AC, WA)
n=int(input())
field=[[0 for i in range(20)]for j in range(15)]
for i in range(n):
    b,f,r,v=map(int,input().split())
    h=(b-1)*4+f-1
    w=r*2-1
    n=v
    field[h][w]+=n
for y in range(15):
    for x in range(20):
        if(y%4==3):field[y][x]='#'
        elif (x%2==0) :field[y][x]=' '
        print(field[y][x],end='')
    print()



### FIXED CODE ###

n=int(input())
field=[[0 for i in range(20)]for j in range(15)]
for i in range(n):
    b,f,r,v=map(int,input().split())
    h=(b-1)*4+f-1
    w=r*2-1
    n=v
    field[h][w]+=n
for y in range(15):
    for x in range(20):
        if(y%4==3):field[y][x]='#'
        elif x%2==0 :field[y][x]=' '
        print(field[y][x],end='')
    print()
h, w = map(int, input().split())
grid = [0]*n
for i in range(h):
  grid[i] = input()

counter = [[[0, 0]]*w for i in range(h)]
ans = 0
for i in range(h):
  for j in range(w):
    if grid[i][j] == "#":
      continue
    if i == 0 or grid[i-1][j] == "#":
      k = 0
      while grid[i+k][j] == "." and i+k < n:
        k += 1
      counter[i][j][0] = k
    else:
      counter[i][j][0] = counter[i-1][j][0]
    if j == 0 or grid[i][j-1] == "#":
      k = 0
      while grid[i][j+k] == "." and j+k < n:
        k += 1
      counter[i][j][1] = k
    else:
      counter[i][j][1] = counter[i][j-1][1]
    if ans < counter[i][j][0]+counter[i][j][1]:
      ans = counter[i][j][0]+counter[i][j][1]
print(ans+1)

### FIXED CODE ###

h, w = map(int, input().split())
grid = [0]*h
for i in range(h):
  grid[i] = input()

counter = [[[0, 0] for j in range(w)] for i in range(h)]
ans = 0
for i in range(h):
  for j in range(w):
    if grid[i][j] == "#":
      continue
    if i == 0 or (i != 0 and grid[i-1][j] == "#"):
      k = 0
      while i+k < h and grid[i+k][j] == ".":
        k += 1
      counter[i][j][0] = k-1
    else:
      counter[i][j][0] = counter[i-1][j][0]
    if j == 0 or (j != 0 and grid[i][j-1] == "#"):
      k = 0
      while j+k < w and grid[i][j+k] == ".":
        k += 1
      counter[i][j][1] = k-1
    else:
      counter[i][j][1] = counter[i][j-1][1]
    if ans < counter[i][j][0]+counter[i][j][1]:
      ans = counter[i][j][0]+counter[i][j][1]
print(ans+1)
n=int(input(n))
t=False

for i in range(1,10):
  for j in range(1,10):
    if i*j==n:
      t=True
      break
if t:
  print('Yes')
else:
  print('No')


### FIXED CODE ###

n=int(input())
t=False

for i in range(1,10):
  for j in range(1,10):
    if i*j==n:
      t=True
      break
if t:
  print('Yes')
else:
  print('No')
from math import gcd

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

length = N * M // gcd(N, M)
ans1 = ['']*length
ans2 = ['']*length

result = ''
for i in range(N):
    index = i * length // N + 1
    ans1[index-1] = S[i]

for i in range(M):
    index = i * length // M + 1
    ans2[index-1] = T[i]

for s, t in zip(ans1, ans2):
    if s != '' and t != '':
        if s != t:
            print(-1)
            exit()

print(length)


### FIXED CODE ###

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

# ユークリッドの互除法
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

length = N * M // gcd(N, M)

if S[0::length//M] == T[0::length//N]:
    print(length)
else:
    print(-1)
def main():
    s=input()
    m=int(input())
    tank=[]
    n=len(s)
    alpha=[chr(i) for i in range(97, 97+26)]
    for i in range(26):
        for j in range(n):
            if alpha[i]==s[j]:
                for k in range(n-j):
                    if s[j:j+k+1] not in tank:
                        tank.append(s[j:j+k+1])
        if len(tank)>=k:
            break
    tank.sort()
    print(tank[m-1])
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    s=input()
    m=int(input())
    tank=[]
    n=len(s)
    alpha=[chr(i) for i in range(97, 97+26)]
    for i in range(26):
        for j in range(n):
            if alpha[i]==s[j]:
                for k in range(min(n-j,m)):
                    if s[j:j+k+1] not in tank:
                        tank.append(s[j:j+k+1])
        if len(tank)>=m:
            break
    tank.sort()
    print(tank[m-1])
    
if __name__ == "__main__":
    main()
S = input()
cnt = 0
N = len(S)
for i in range(int((N-3)/2)):
    if S[i] == S[N-i-1]:
        cnt += 1
    else:
        pass
if cnt == (N-3)/2 and S % 4 != 1:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

S = input()
N = len(S)
cnt = 0
S1 = S[:int((N-1)/2)]
S2 = S[int((N+1)/2):]
if S == S[::-1] and S1 == S1[::-1] and S2 == S2[::-1]:
    print("Yes")
else :
    print("No")
Tmp = []
Tmp = input().rstrip().split(' ')

S = []
S = int(Tmp[1])

sTmp = S[0]

print('A'+sTmp+'C')


### FIXED CODE ###

Tmp = []
Tmp = input().rstrip().split(' ')
 
S = []
S = (Tmp[1])
 
sTmp = S[0]
 
print('A', end='')
print('%s' %(sTmp), end='')
print('C')
odd = ["R", "U", "D"]
even = ["L", "U", "D"]
s_list = list(input())

ans = "Yes"
for i in range(s_list):
  if i % 2 == 0:
	  if not data[i] in odd:
    	ans = "No"
  
  if i % 2 == 0:
	  if not data[i] in even:
    	ans = "No"

print(ans)

### FIXED CODE ###

s = list(input())
odd_s = ["R", "U", "D"]
even_s = ["L", "U", "D"]

ans = "Yes"

for i in range(len(s)):
  if i % 2 == 0:
    if s[i] not in odd_s:
      ans = "No"
  
  if i % 2 == 1:
    if s[i] not in even_s:
      ans = "No"

print(ans)
N=int(input())
ans=""
check="abcdefghijklmnopqrstuvwxyz"

while N!=0:
	N-=1
	ans+=check[N%26]
	N=N//26

print(ans[::-1])
"""
while N>0:
	N-=1
	ans+=chr(ord("a")+ N%26)
	N//=26
print(ans[::-1])
"""




### FIXED CODE ###

X, N =map(int, input().split())
p_list=list(map(int, input().split()))
#i=N
#1st Xがp_listにあるか
	#あれば+=!
	#なければ答え
#|X-i|=1がp_listにあるか
	#あれば+=!
	#なければ答え

i=N
j=0
while True:
	if X-j not in p_list:
		print(X-j)
		exit()
	elif X+j not in p_list:
		print(X+j)
		exit()
	else:
		j+=1
import math
pi = math.pi
r = raw_input()
area = r * r * pi
cir = 2 * r *pi
print '%f %f' %(area, cir)

### FIXED CODE ###

import math
r = input()
area = r * r * math.pi * 1.0
cir = 2 * r * math.pi * 1.0
print '%f %f' % (area, cir)
def calc(i, k):
    ans_list = [i]
    ans_set = set([i])
    count = 1
    i = a[i]
    while (i not in ans_set) & (count < k):
        ans_list.append(i)
        ans_set.add(i)
        count += 1
        i = a[i]
    index = ans_list.index(i)
    ans_list.append(i)
    return count, ans_list

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

count, ans_list = calc(0, k)
if count < k:
    index = ans_list.index(ans_list[-1])
    k = k - index
    ans_list = ans_list[index + 1:]
    print(ans_list[k % len(ans_list) - 1] + 1)
else:
    print(ans_list[k] + 1)

### FIXED CODE ###

n, k = map(int, input().split())
a = [int(i) - 1 for i in input().split()]
visit = {0}
tmp = 0
a_list = [0]
ans = True
for i in range(k):
    tmp = a[tmp]
    if tmp in visit:
        left = a_list.index(tmp)
        ans = False
        print(a_list[left + (k - left) % (i + 1 - left)] + 1)
        break
    else:
        visit.add(tmp)
        a_list.append(tmp)
if ans:
    print(tmp + 1)
N = input()
B = False
kaisu = 0
array = map(int,input().split())

def calc(n):
  retuen n/2
  
  
while B:
	for i in range(N):
  		if array[i]/2 == 1:
    	B = True
  	if B == False:
    	array = map(calc ,array)
    	kaisu += 1
  	else:
    	break
        
print(kaisu)
    

    

### FIXED CODE ###

N = int(input())
B = False
kaisu = 0
array = list(map(int,input().split()))

def calc(n):
  return int(n) / 2
  
  
while not B:
  for i in range(N):
    if array[i] % 2 == 1:
      B = True
  if not B:
    array = list(map(calc, array))
    kaisu += 1
  else:
    break
        
print(kaisu)
h1,m1,h2,m2,k=map(int,input().split())

if m1<=m2:
    print(max((h2-h1)*60+m2-m1-k),0)
else:
    print(max((h2-h1-1)*60+m2+60-m1-k,0))


### FIXED CODE ###

h1,m1,h2,m2,k=map(int,input().split())

if m1<=m2:
    print(max((h2-h1)*60+m2-m1-k,0))
else:
    print(max((h2-h1-1)*60+m2+60-m1-k,0))
x = int(input())
a = int(input())
b = int(input())

c = x-a
print(int(c%b())

### FIXED CODE ###

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

print((x-a)%b)
import copy

n = int(input())
l = list(map(int, input().split()))
#n = int(input())
#inputs = input().split(" ")
#l = [int(s) for s in inputs]

def calc(rl, ns, skip):
    v = rl.pop(len(rl)-1)
    # print(rl,v,ns)
    lrl = len(rl)
    
    if lrl == 0:
        return ns
    if lrl == 1:
        v1 = rl[len(rl)-1]
        return ns+abs(v-v1)
    if lrl == 2:
        v1 = rl[len(rl)-1]
        v2 = rl[len(rl)-2]
        ns1 = ns + abs(v-v2)
        ns2 = ns + abs(v-v1) + abs(v1-v2)
        # print("lrl 2:",v1,v2,ns1,ns2,ns)
        return min(ns1,ns2)
    else:
        v1 = rl[len(rl)-1]
        c1 = -1
        if skip == False:
            crl = copy.copy(rl)
            c1 = calc(crl,ns+abs(v-v1),True)
        v2 = rl[len(rl)-2]
        rl.pop(len(rl)-1)
        c2 = calc(rl,ns+abs(v-v2),False)
        if (c1 == -1):
            return c2
        else:
            return min(c1,c2)

print(calc(l,0,False))


### FIXED CODE ###

N = int(input())
h = list(map(int, input().split()))
 
suml = [1e5 for i in range(N)]
suml[0] = 0
suml[1] = abs(h[1] - h[0])
 
for e in range(2, N):
    suml[e] = min(
        abs(h[e]-h[e-1]) + suml[e-1],
        abs(h[e]-h[e-2]) + suml[e-2],
    )
 
# print(suml)
print(suml[N-1])
n = list(input())
ans = 0

a = (len(n) - 1) * 9 + int(n[0]) - 1

if a < sum(map(int, n)):
    ans = sum(n)
else:
    ans = a

print(ans)

### FIXED CODE ###

n = list(input())
ans = 0

a = (len(n) - 1) * 9 + int(n[0]) - 1

if a < sum(map(int, n)):
    ans = sum(map(int, n))
else:
    ans = a

print(ans)
import sys
for i in stdin.sys:
    a, b, c, d, e, f = map(float, raw_input().split()) 
    x = float(c*e - b*f)/(a*e - b*d)
    y = float(c*d - a*f)/(b*d - a*e)
    if x == -0:
        x = 0
    if y == -0:
        y = 0
    print ("%.3f %.3f" % (x, y))

### FIXED CODE ###

while True:
    try:
        a,b,c,d,e,f=map(float,raw_input().split())
        y=(d*c-a*f)*1.0/(d*b-a*e)
        print "%.3f %.3f" % ((c-b*y)/a, y)
    except:
        break
n = map(int, input())
data = list(map(int, input().split()))

a = 1
while i<n:
  a = a*data[i]
  i += 1
  if a > 10^18:
    a = -1

print(a)

### FIXED CODE ###

n = int(input())
data = list(map(int, input().split()))

flag = 0
if data.count(0) > 0:
	print(0)
else:
  a = data[0]
  for i in range(1,n):
    a = a*data[i]
    if a > 10**18:
      flag = 1
      break
      
  if flag == 1:
    print('-1')
  else:
    print(a)
s=list(int(input()))
ans=0
for i in s:
  if i==1:
    ans=ans+1
print(ans)

### FIXED CODE ###

s=list(input())
ans=0
for i in s:
  if i=="1":
    ans=ans+1
print(ans)
x,y,z,k=map(int,input().split());a,b,c=list(map(int,input().split())),list(map(int,input().split())),list(map(int,input().split()));a.sort(reverse=1);b.sort(reverse=1);c.sort(reverse=1);ma=a[0]+b[0]+c[0];d=[[0],[0],[0]]
for i in range(len(a)-1):d[0].append(d[0][-1]+a[i]-a[i+1])
for i in range(len(b)-1):d[1].append(d[1][-1]+b[i]-b[i+1])
for i in range(len(c)-1):d[2].append(d[2][-1]+c[i]-c[i+1])
e=d[0]+d[1]+d[2]
if x*y*z>3000:
  f,i=[0,0,0],0
  while f[0]*f[1]*f[2]<3000:
    for z in range(3):
      if f[z]<len(d[z]):
        while d[z][f[z]]==i:
          f[z]+=1
          if f[z]==len(d[z]):break
    i=min(d[0][f[0]],min(d[1][f[1]],d[2][f[2]]))
  for i in range(3):d[i]=d[i][:f[i]+1]
s=[]
for i in d[0]:
  for j in d[1]:
    for h in d[2]:s.append(i+h+j)
s.sort()
for i in range(k):print(ma-s[i])

### FIXED CODE ###

from heapq import heappop,heappush;import sys;input=sys.stdin.readline
x,y,z,k=map(int,input().split());a,b,c=list(map(int,input().split())),list(map(int,input().split())),list(map(int,input().split()))
q,h,l=[],[],0
for i in a:
  for j in b:heappush(q,-(i+j));l+=1
for _ in range(min(l,k)):
  t=heappop(q)
  for i in c:heappush(h,t-i)
for i in range(k):print(-heappop(h))
A,B,C=map(int,input().split())
D,E,F=map(int,input().split())
G,H,I=map(int,input().split())
N=int(input())
b=[input() for i in range(N-1)]
if b.count(A)>0 and b.count(B)>0 and b.count(C)>0:
    print("Yes")
    exit()
if b.count(D)>0 and b.count(E)>0 and b.count(F)>0:
    print("Yes")
    exit()
if b.count(G)>0 and b.count(H)>0 and b.count(I)>0:
    print("Yes")
    exit()
if b.count(A)>0 and b.count(D)>0 and b.count(G)>0:
    print("Yes")
    exit()
if b.count(B)>0 and b.count(E)>0 and b.count(H)>0:
    print("Yes")
    exit()
if b.count(C)>0 and b.count(F)>0 and b.count(I)>0:
    print("Yes")
    exit()
if b.count(A)>0 and b.count(E)>0 and b.count(I)>0:
    print("Yes")
    exit()
if b.count(C)>0 and b.count(E)>0 and b.count(G)>0:
    print("Yes")
    exit()
else:
    print("No")

    




### FIXED CODE ###

N=int(input())

print(-(-N//2))
import numpy as np

n,m = map(int, input().split())
p = np.array(list(map(int, input().split())))
p = p-1
q = np.zeros((m,2), dtype='uint32')
for i in range(m):
	q[i] = list(map(int, input().split()))
q=q-1
par = np.arange(n)
rank = np.zeros(n)

def root(x):
	if par[x] == x:
		return x
	else:
		return root(par[x])
def merge(x, y):
	x = root(x)
	y = root(y)
	if x == y:
		pass
	else:
		if rank[x] > rank[y]:
			par[y] = x
			rank[y] += 1
		else:
			par[x] = y
			rank[x] += 1
	pass

for x,y in q:
	merge(x,y)

ans = 0

for i in range(n):
	if root(p[i]) == root(i):
		ans += 1

print(ans)

### FIXED CODE ###

n,m = map(int, input().split())
p = list(map(int, input().split()))
par = [i for i in range(n)]
rank = [0 for x in range(n)]

def root(x):
	tmp = par[x]
	if tmp == x:
		return x
	else:
		a = root(tmp)
		par[x] = a
		return a

def merge(x, y):
	x = root(x)
	y = root(y)
	if x == y:
		return
	else:
		if rank[x] > rank[y]:
			par[y] = x
			rank[y] += rank[x]
		else:
			par[x] = y
			rank[x] += rank[y]
		return

for i in range(m):
	x, y = map(int, input().split())
	merge(x-1, y-1)

ans = 0

for i in range(n):
	if p[i]-1 == i:
		ans += 1
	elif root(p[i]-1) == root(i):
		ans += 1

print(ans)
n, k = map(int, input().split())

d = []
a = []
res = [0] * n

for i in range(k):
    d_tmp = int(input())
    a_tmp = map(int, input().split())
    d.append(d_tmp)
    a.append(a_tmp)

for aa in a:
    for aaa in aa:
        res[aaa - 1] += 1

count = 0

for i in range(k):
    if res[i] == 0:
        count += 1

print(count)


### FIXED CODE ###

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

d = []
a = []
res = [0] * n

for i in range(k):
    d_tmp = int(input())
    a_tmp = list(map(int, input().split()))
    d.append(d_tmp)
    a.append(a_tmp)

for aa in a:
    for aaa in aa:
        res[aaa - 1] += 1

count = 0

for i in range(n):
    if res[i] == 0:
        count += 1

print(count)
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

def yn(b):
    print("Yes" if b==1 else "No")
    return

def count_ones_by_bin(num):
    bin_num = bin(num)[2:]
    count = 0
    for i in bin_num:
            count += int(i)
    return count

def resolve():
    readline=sys.stdin.readline

    n=int(readline())
    x=readline().rstrip()

    #pc=[0]*(10**5+1)
    #for i in range(1,10**5):
    #    pc[i]=count_ones_by_bin(i)
    amr1=[0]*((10**5)*2 + 1)
    amr2=[0]*((10**5)*2 + 1)
    bits=[False]*((10**5)*2 + 1)

    bcnt=0
    j=0
    for i in x:
        if int(i)==1:
            bcnt += 1
            bits[j]=True
        j+=1

    base1=0
    base2=0
    for i in range(n):
        jo=n-i-1
        amr1[i]=pow(2,jo,bcnt+1)
        amr2[i]=pow(2,jo,bcnt-1)
        if bits[i]==True:
            base1+=amr1[i]
            base2+=amr2[i]
    for i in range(n):
        ans=0
        if bits[i]==True: #1->0
            base=(base2-amr2[i])%(bcnt-1)
        else:
            base=(base1+amr1[i])%(bcnt+1)
        ans+=1
        while base > 0:
            pp=count_ones_by_bin(base)
            base=base%pp
            ans+=1
        print(ans)
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

### FIXED CODE ###

### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

sys.setrecursionlimit(20000000)

def yn(b):
    print("Yes" if b==1 else "No")
    return

def count_ones_by_bin(num):
    bin_num = bin(num)[2:]
    count = 0
    for i in bin_num:
            count += int(i)
    return count

def resolve():
    readline=sys.stdin.readline

    n=int(readline())
    x=readline().rstrip()

    #pc=[0]*(10**5+1)
    #for i in range(1,10**5):
    #    pc[i]=count_ones_by_bin(i)
    amr1=[0]*((10**5)*2 + 5)
    amr2=[0]*((10**5)*2 + 5)
    bits=[False]*((10**5)*2 + 5)
    pc=[-1]*((10**5)*2 + 5)
    bcnt=0
    j=0
    for i in x:
        if int(i)==1:
            bcnt += 1
            bits[j]=True
        j+=1

    base1=0
    base2=0
    ni1=1
    ni2=1
    for j in range(n):
        i=n-1-j
        jo=n-i-1
        if j > 0:
            ni1*=2
            ni2*=2
        #amr1[i]=pow(2,jo,bcnt+1)
        ni1=ni1%(bcnt+1)
        amr1[i]=ni1
        if (bcnt-1)==0:
            amr2[i]=0 #pow(2,jo)
        else:
            #amr2[i]=pow(2,jo,bcnt-1)
            ni2=ni2%(bcnt-1)
            amr2[i]=ni2
        if bits[i]==True:
            base1+=amr1[i]
            base2+=amr2[i]
    for i in range(n):
        ans=0
        if bits[i]==True: #1->0
            if (bcnt-1)==0:
                base=0
            else:
                base=(base2-amr2[i])%(bcnt-1)
                ans+=1
        else:
            base=(base1+amr1[i])%(bcnt+1)
            ans+=1
        
        while base > 0:
            if pc[base]==-1:
                pc[base]=count_ones_by_bin(base)
            base=base%pc[base]
            ans+=1
        print(ans)
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------
n1 = int(input())
n2 = int(input())
 
if n1%500<n2:
  print(Yes)
else:
  print(No)

### FIXED CODE ###

n1 = int(input())
n2 = int(input())
 
if n1%500<=n2:
  print("Yes")
else:
  print("No")
import numpy as np
import math

def kochCurve(p1, p2, n):
  if n == 0:
    print(p2[0], p2[1])
    return

  v = (p2 - p1)/3
  s = p1 + v
  t = s + v

  theta = math.atan2(v[1], v[0])

  a = np.linalg.norm(t - s)
  h = 3**(1/2)*a/2
  u = s + (t - s)/2 + np.array([h*math.sin(theta), h*math.cos(theta)])

#  print(n, p1, s, u, t, p2)

  n -= 1
  kochCurve(p1, s, n)
  kochCurve(s, u, n)
  kochCurve(u, t, n)
  kochCurve(t, p2, n)

if __name__ == "__main__":
  n = int(input())
  print([0, 0])
  kochCurve(np.array([0, 0]), np.array([100, 0]), n)

### FIXED CODE ###

import math

def kochCurve(p1, p2, n):
  if n == 0:
    print(p2[0], p2[1])
    return

  v = [(p2[0]-p1[0])/3, (p2[1]-p1[1])/3]
  s = [p1[0]+v[0], p1[1]+v[1]]
  t = [s[0]+v[0], s[1]+v[1]]

  theta = math.atan2(v[1], v[0]) + math.pi/2

  a = math.sqrt((t[0]-s[0])**2+(t[1]-s[1])**2)
  h = 3**(1/2)*a/2
  u = [s[0]+(t[0]-s[0])/2+h*math.cos(theta), s[1]+(t[1]-s[1])/2+h*math.sin(theta)]

  n -= 1
  kochCurve(p1, s, n)
  kochCurve(s, u, n)
  kochCurve(u, t, n)
  kochCurve(t, p2, n)

if __name__ == "__main__":
  n = int(input())
  print(0, 0)
  kochCurve([0, 0], [100, 0], n)
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
S = [list(map(int, input().split())) for l in range(Q)]

l = [0] * 10**5
tot = 0
for i in range(N) :
    l[A[i]]+=1
    tot += A[i]
for i in range(Q):
    s0 = S[i][0]
    s1 = S[i][1]
    tot += s1 * (l[s0] + l[s1]) - (s0 * l[s0] + s1*l[s1])
    l[s1] += l[s0]
    l[s0] = 0
    print(tot)

### FIXED CODE ###

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

l = [0] * 10**6
tot = 0
for i in range(N) :
    l[A[i]]+=1
    tot += A[i]
for i in range(Q):
    s0 = S[i][0]
    s1 = S[i][1]
    tot += s1 * (l[s0] + l[s1]) - (s0 * l[s0] + s1*l[s1])
    l[s1] += l[s0]
    l[s0] = 0
    print(tot)
#n=int(input())
#s,t=input().split()
n,m = map(int, input().split())
#l=list(map(int, input().split()))
l=[0]*100005
r=[1000005]*100005
z=1000010
for i in range(m):
   l[i],r[i]=map(int,input().split()) 
mi=max(l)
ma=min(r)



if mi>ma:
    print(0)
else
    print(ma-mi+1)

### FIXED CODE ###

#n=int(input())
#s,t=input().split()
n,m = map(int, input().split())
#l=list(map(int, input().split()))
l=[0]*100005
r=[1000005]*100005
z=1000010
for i in range(m):
   l[i],r[i]=map(int,input().split()) 
mi=max(l)
ma=min(r)



if mi>ma:
    print(0)
else:
    print(ma-mi+1)