Harryxun/stf_run huggingface dataset:
N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]
BC.sort(reverse=True, key=lambda x:x[1])
A.sort()

ans = []
for b,c in BC:
  n = len(ans)
  for i in range(b):
    if A[n] < c:
      ans.append(c)
      n += 1
    else: break

print(sum(ans) + sum(A[len(ans):]))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]
BC.sort(reverse=True, key=lambda x:x[1])
A.sort()

ans = []
for b,c in BC:
  n = len(ans)
  for i in range(b):
    if n >  N-1: break
    if A[n] < c:
      ans.append(c)
      n += 1
    else: break

print(sum(ans) + sum(A[len(ans):]))
a, b = map(int, input())
print(max(a+b, a-b, a*b))

### FIXED CODE ###

a, b = map(int, input().split())
print(max(a+b, a-b, a*b))
a,b = map(int,input().split())
cnt = 0
for i in range(a,b+1):
    lst = list(i)
    if lst[0] == lst[-1] and lst[1] == lst[-2]:
        cnt += 1
plint(cnt)

### FIXED CODE ###

a,b = map(int,input().split())
cnt = 0
for i in range(a,b+1):
    lst = list(str(i))
    if lst[0] == lst[-1] and lst[1] == lst[-2]:
        cnt += 1
print(cnt)
# coding: utf-8
# Your code here!

N=list(input())

for i in range(10):
    if 111*i<N<=111*(i+1):
        print(111*(i+1))


### FIXED CODE ###

N=list(input())
for i in range(3):
    if int(N[i])==1:
        N[i]='9'
    else:
        N[i]='1'
print(''.join(N))
a,b,c=map(int,input(),split())
if c<=a+b:
    print(b+c)
else:
    print(a+2*b)

### FIXED CODE ###

a,b,c=map(int,input().split())
if c<=a+b+1:
    print(b+c)
else:
    print(a+2*b+1)
import sys
sys.setrecursionlimit(10**6)

s = input()

ans = [0]*len(s)

for _ in range(2):
    cnt = 0
    for i in range(n):
        if s[i] == 'R': cnt += 1
        else:
            ans[i] += cnt//2
            ans[i-1] += (cnt-1)//2
            cnt = 0
        
    ans.sort()
    s = s[::-1]
    for i in range(n):
        if s[i] == 'L': s[i] = 'R'
        else: s[i] = 'L'

print(*ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

s = input()

ans = [0]*len(s)

i = 0
len_left = 1
len_right = 0
intersec_left = 0
now_left = True

while i < len(s)-1:
    if s[i] == s[i+1] and now_left:
        len_left += 1
    elif s[i] != s[i+1] and now_left:
        len_right += 1
        intersec_left = i
        now_left = False
    elif s[i] == s[i+1]:
        len_right += 1
    else:
        if len_left%2 == 0:
            ans[intersec_left] += len_left//2
            ans[intersec_left+1] += len_left//2
        else:
            ans[intersec_left] += len_left//2+1
            ans[intersec_left+1] += len_left//2
        if len_right%2 == 0:
            ans[intersec_left] += len_right//2
            ans[intersec_left+1] += len_right//2
        else:
            ans[intersec_left] += len_right//2
            ans[intersec_left+1] += len_right//2+1
        len_left = 1
        len_right = 0
        intersec_left = i+1
        now_left = True
    i += 1
else:
    if len_left%2 == 0:
        ans[intersec_left] += len_left//2
        ans[intersec_left+1] += len_left//2
    else:
        ans[intersec_left] += len_left//2+1
        ans[intersec_left+1] += len_left//2
    if len_right%2 == 0:
        ans[intersec_left] += len_right//2
        ans[intersec_left+1] += len_right//2
    else:
        ans[intersec_left] += len_right//2
        ans[intersec_left+1] += len_right//2+1
    
print(*ans)
vals = [int(i) for i in input().split()]
    a = vals[0]
    b = vals[1]
    c = vals[2]
    d = vals[3]
    res2 = a//d + (1 if(a % d > 0) else 0)
    res1 = c//b + (1 if(c % b > 0) else 0)
    res = "Yes" if(res1 <= res2) else "No"
    print(res)

### FIXED CODE ###

vals = [int(i) for i in input().split()]
a = vals[0]
b = vals[1]
c = vals[2]
d = vals[3]
res2 = a//d + (1 if(a % d > 0) else 0)
res1 = c//b + (1 if(c % b > 0) else 0)
res = "Yes" if(res1 <= res2) else "No"
print(res)
i=0

while True:
    c = int(input())
    ifc==0:
      break
    i = i+1
    print "Case %d: %d" %  (i,c)

### FIXED CODE ###

i=0

while True:
    a = int(input())
    if(a==0):
      break
    i = i+1
    print "Case %d: %d" %  (i,a)
count = 0
i = 0
while (n>i):
    for bi in range(b):
        count += 1
        i += 1
        if n <= i:
            break
    for ri in range(r):
        i += 1
        if n<=i:
            break
print(count)

### FIXED CODE ###

n, b, r = map(int, input().split())
i = 0
hoge = n // (b+r)
count = hoge*b
n = n - hoge*(b+r)
if n == 0:
    print(count)
while (n>i):
    count += b
    i += b
    if n<=i:
        print(count - (i-n))
        break
    i += r
    if n<=i:
        print(count)
a = int(input().split()[0])
alle = []
counter = 0
output = []
for i in range(a):
	p = input().split()
	p = [int(j)%2 for j in p]
	for j in range(len(p) - 1):
		if p[j] % 2 == 1:
			output.append([i + 1, j + 1, i + 1, j + 2])
			counter += 1
			p[j + 1] += 1
	alle.append(p[-1])
	
for i in range(a - 1):
	if alle[i] % 2 == 1:
		output.append([i + 1, len(p[0]),  i + 2, len(p[0])])
		counter += 1
		alle[i + 1] = alle[i] + 1
		
print (counter)
for i in output:
	print (i[0],i[1],i[2],i[3])

### FIXED CODE ###

a = int(input().split()[0])
alle = []
counter = 0
output = []
for i in range(a):
	p = input().split()
	p = [int(j)%2 for j in p]
	for j in range(len(p) - 1):
		if p[j] % 2 == 1:
			output.append([i + 1, j + 1, i + 1, j + 2])
			counter += 1
			p[j + 1] += 1
	alle.append(p[-1])
	
for i in range(a - 1):
	if alle[i] % 2 == 1:
		output.append([i + 1, len(p),  i + 2, len(p)])
		counter += 1
		alle[i + 1]  += 1
		
print (counter)
for i in output:
	print (i[0],i[1],i[2],i[3])
n,x= list(map(int, input().split()))

L=list(map(int, input().split()))
d=0

for i in range(1,n+2):
    d+=L[i-1]
    if d>x:
        ans=i
        break
print(ans)

### FIXED CODE ###

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

L=list(map(int, input().split()))
D=[0]
for i in range(0,n):
    D.append(D[i]+L[i])
ans=0
for i in range(n+1):
    if D[i]<=x:
        ans+=1
    else:
        break

print(ans)
# coding: utf-8
# Here your code !

def calculate_minkowski_distances():
    _ = input()
    data = []
    for i in range(2):
        data.append([float(value) for value in input().rstrip().split()])

    for exponent in (1, 2, 3, float("inf")):
        print("{0:.8f}".format(minkowski_distance(*data, exponent)))

def minkowski_distance(vector_x, vector_y, exponent):
    abs_xy = [ abs(pair[0] - pair[1]) for pair in zip(vector_x, vector_y) ]

    m_dis = 0
    if exponent == float("inf") :
        m_dis = max(abs_xy)
    elif exponent == 0 :
        m_dis = nan
    else :
        m_dis = ( sum([ elem**exponent for elem in abs_xy ])**(1/exponent) )
    
    return m_dis

if __name__ == "__main__" :
    calculate_minkowski_distances()
    
    

### FIXED CODE ###

# coding: utf-8
# Here your code !

def calculate_minkowski_distances():
    _ = input()
    data = []
    for i in range(2):
        data.append([float(value) for value in input().rstrip().split()])

    for exponent in (1, 2, 3, float("inf")):
        print(minkowski_distance(data[0],data[1], exponent))
#        print("{0:.8f}".format(minkowski_distance(*data, exponent)))

def minkowski_distance(vector_x, vector_y, exponent):
#    abs_xy = [ abs(pair[0] - pair[1]) for pair in zip(vector_x, vector_y) ]
    abs_xy = [abs(vector_x[i] - vector_y[i]) for i in range(len(vector_x))]
    
    m_dis = 0
    if exponent == float("inf") :
        m_dis = max(abs_xy)
    elif exponent == 0 :
        m_dis = nan
    else :
        m_dis = sum([ elem**exponent for elem in abs_xy ])**(1/exponent)
    
    return m_dis

if __name__ == "__main__" :
    calculate_minkowski_distances()
sa=list(input())
sb=list(input())
sc=list(input())

n=sa.pop(0)
while True:
    if n == 'a':
        if len(sa)==0:
            print('A')
            break
        n=sa.pop(0)
    elif n == 'b':
        if len(sa)==0:
            print('B')
            break
        n=sb.pop(0)
    elif n == 'c':
        if len(sa)==0:
            print('C')
            break
        n=sc.pop(0)

### FIXED CODE ###

sa=list(input())
sb=list(input())
sc=list(input())

n=sa.pop(0)
while True:
    if n == 'a':
        if len(sa)==0:
            print('A')
            break
        n=sa.pop(0)
    elif n == 'b':
        if len(sb)==0:
            print('B')
            break
        n=sb.pop(0)
    elif n == 'c':
        if len(sc)==0:
            print('C')
            break
        n=sc.pop(0)
import math
def c(n, r):
    a = math.factorial(n)
    b = math.factorial(n-r)
    c = math.factorial(r)
    return (a // b * c)

N,K = [int(i) for i in input().split()]
for i in range(1,K+1):
    num1 = c(K-1,i-1) % (10**9+7)
    num2 = c(N-K+1,i) % (10**9+7)
    ans = (num1*num2) % (10**9+7)
    print(ans)

### FIXED CODE ###

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

mod = 10**9+7 #出力の制限
N = 10**4
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

N,K = [int(i) for i in input().split()]
for i in range(1,K+1):
    num1 = c(K-1,i-1,mod)
    num2 = c(N-K+1,i,mod)
    ans = (num1*num2) % (10**9+7)
    print(ans)
import math

N = int(input())
K = int(input())
mod = N % K
  
if(abs(mod-K) < mod)
  mod = abs(mod-K);
  
print(mod)


### FIXED CODE ###

import math
 
N, K = map(int, input().split())
mod = N % K
  
if abs(mod-K) < mod:
  mod = abs(mod-K)
  
print(mod)
r = int(input())
ptinr(r**2)

### FIXED CODE ###

r = int(input())
print(r**2)
a op b = (str(i) for i in input().split())
if op == '+':print(int(a) + int(b))
if op == '-':print(int(a) - int(b))
if op == '*':print(int(a) * int(b))
if op == '/':print(int(a) / int(b))
else:print(int(a) % int(b))

### FIXED CODE ###

a_list = []
b_list = []
op_list = []
count = 0
while True:
  a, op, b = (str(i) for i in input().split())
  if op != '?':
    a_list.append(int(a))
    b_list.append(int(b))
    op_list.append(op)
    count += 1
  else :
    break
for i in range(0,count):
  if op_list[i] == '+':
    print(a_list[i] + b_list[i])
  elif op_list[i] == '-':
    print(a_list[i] - b_list[i])
  elif op_list[i] == '*':
    print(a_list[i] * b_list[i])
  elif op_list[i] == '/':
    print(a_list[i] // b_list[i])
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

sa = sum(A)

for i, b in enumerate(B):
    tmp = min(A[i], b)  # 削り取れる分
    A[i] -= tmp　　# 削り取る
    A[i + 1] -= min(A[i + 1], b - tmp)　　# i+1から削れる分はここで削っておく。b-tmpがi時点でのA[i+1]への攻撃力

print(sa - sum(A))　　# 全量から削れなかった分を引く

### FIXED CODE ###

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

sa = sum(A)

for i, b in enumerate(B):
    tmp = min(A[i], b)  # 削り取れる分
    A[i] -= tmp  # 削り取る
    A[i + 1] -= min(A[i + 1], b - tmp)  # i+1から削れる分はここで削っておく。b-tmpがi時点でのA[i+1]への攻撃力

print(sa - sum(A))  # 全量から削れなかった分を引く
n, k = map(int, input().split())
list_original = list(map(int, input().split()))

list_original.append(0)
list = sorted(list_original)
point = list.index(0)

if k <= point and point <= n-k+1:
    if abs(list[point-k]) <= list[point+k]:
        print(abs(list[point-k]))
    else:
        print(list[point])
elif point < k:
    print(list[point+k])
else:
    print(abs(list[point-k]))

### FIXED CODE ###

n, k = map(int, input().split())
x = list(map(int, input().split()))
ans = []

for i in range(n-k+1):
    if x[i+k-1] < 0:
        ans.append(abs(x[i]))
    elif x[i] > 0:
        ans.append(abs(x[i+k-1]))
    else:
        ans.append(min(abs(x[i])*2+abs(x[i+k-1]), abs(x[i])+abs(x[i+k-1])*2))

print(min(ans))
n = input()
if n%2==0:
  print(n/2)
else:
  print(n//2+1)

### FIXED CODE ###

#n = int(input())
#l = list(map(int, input().split()))

'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)a
    B.append(b)'''

#def sol(n,):    
    
def main():
    import sys
    input = sys.stdin.readline
    

    n = int(input())
    if n % 2 == 0:
        print(int(n/2))
    else:
        print(int(n//2+1))





if __name__ == "__main__":
    main()
N = int(input())
A = [int(i) for i in input().split(' ')]
for i in range(N):
 if sum([i%2 for i in A])>0:
  print(i)
  break
 else: A = [i//2 for i in A]

### FIXED CODE ###

import numpy
S = input()
print(numpy.array([i=='1' for i in S]).sum())
a,b,c,k = map(int,input().split())
sum=0
if(k==0):
  print(sum)
  exit()
if(a>k):
  sum+=k
  print(sum)
  exit()
else:
  sum+=a
  k=k-a
  if(k==0):
    print(sum)
    exit()
  if(b>k):
    print(sum)
    exit()
  else:
    k = k-b
    if(k==0):
      print(sum)
      exit()
    if(c>k):
      sum-=k
      print(sum)
    else:
      sum-=c
      print(sum)


### FIXED CODE ###

a = input()
b = input()
last_char = b[len(b)-1]
if (a+last_char == b):
  print("Yes")
else:
  print("No")
from collections import Counter
n = int(input())
lista = list(map(int, input().split()))

count = Counter(lista)
lista.sort()

M = 1000001
P = [0] * (M)
ans = 0

for i in lista:
    if P[i] == 0:
        for j in range(M):
            x = i * j
            if x > M:
                break
            P[x] = 1
        if count[i] == 1:
            ans += 1

print(ans)

### FIXED CODE ###

from collections import Counter
import bisect
N = int(input())
A = list(map(int,input().split()))
cnt = Counter(A)
A.sort()
ans = 0
MX = 10**6
P = [0] * (MX+1)
for a in A:
    if P[a]==0:
        for i in range(MX+1):
            x = a*i
            if x > MX:
                break
            P[x] = 1
        if cnt[a]==1:
            ans+=1
print (ans)
K,X = map(int, input().split())
if K*500 >= X:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

l = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',]
C = input()
print(l[l.index(C)+1])
import sys
 
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n,x=na()
l=na()

count=0
pos=0
for i in range(n+1):
    count+=1
    pos+=l[i]
    if pos>x:
        break
print(count)

### FIXED CODE ###

import sys
 
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n,x=na()
l=na()
l.append(0)

count=0
pos=0
for i in range(n+1):
    count+=1
    pos+=l[i]
    if pos>x:
        break
print(count)
import sys
import fractions as fl

#a, b, c, d = list(input().split())
a = int(a)
b = int(b)
c = int(c)
d = int(d)

#全体の個数
all = b - a + 1
#cとdの最小公倍数
e = c * d // fl.gcd(c, d)
# a以下でcまたはdで割れる個数
r1 = (a-1) // c + (a-1) // d - (a-1) // e
# b以下でcまたはdで割れる個数
r2 = b // c + b // d - b // e
ans = all - (r2 - r1)
print(ans)

### FIXED CODE ###

import sys
import fractions as fl

a, b, c, d = input().split()
a = int(a)
b = int(b)
c = int(c)
d = int(d)

#全体の個数
all = b - a + 1
#cとdの最小公倍数
e = c * d // fl.gcd(c, d)
# a以下でcまたはdで割れる個数
r1 = (a-1) // c + (a-1) // d - (a-1) // e
# b以下でcまたはdで割れる個数
r2 = b // c + b // d - b // e
ans = all - (r2 - r1)
print(ans)
def quicksort(lst):
	if lst == []: return []
	elif len(lst) == 1: return lst
	else:
		pivot = lst[0][0]
		leftlist = []
		rightlist = []
		for i in range(0, len(lst)):
			if lst[i][0] < pivot:
				leftlist.append(lst[i])
			else:
				rightlist.append(lst[i])
		newleft = quicksort(leftlist)
		newright = quicksort(rightlist)
		newleft.extend(newright)
		return newleft

N, M = map(int, raw_input().split())
drinklist = []
for i in range(0, N):
	drinklist.append(map(int, raw_input().split()))
drinklist = quicksort(drinklist)
print drinklist
sum = 0
drink = M
for i in range(0, N):
	if drink < drinklist[i][1]:
		sum += drink * drinklist[i][0]
		break
	else:
		sum += drinklist[i][1] * drinklist[i][0]
		drink -= drinklist[i][1]

print sum

### FIXED CODE ###

from operator import itemgetter

N, M = map(int, raw_input().split())
drinklist = []
for i in range(0, N):
	drinklist.append(map(int, raw_input().split()))
drinklist = sorted(drinklist, key=itemgetter(0))
sum = 0
drink = M
for i in range(0, N):
	if drink < drinklist[i][1]:
		sum += drink * drinklist[i][0]
		break
	else:
		sum += drinklist[i][1] * drinklist[i][0]
		drink -= drinklist[i][1]

print sum
a,b,c = map(int,raw_input().split())
lst = []
for i in range(a,b+1):
	if c%i == 0:
		lst.append(i)
return len(lst)

### FIXED CODE ###

a,b,c = map(int,raw_input().split())
lst = []
for i in range(a,b+1):
	if c%i == 0:
		lst.append(i)
print len(lst)
N = int(input())
V = list(map(int, input().split()))

even_idx_cnt = {}
odd_idx_cnt = {}
for idx, v in enumerate(V):
    if idx % 2 == 0:
        if v not in even_idx_cnt:
            even_idx_cnt[v] = 0
        even_idx_cnt[v] += 1
    else:
        if v not in odd_idx_cnt:
            odd_idx_cnt[v] = 0
        odd_idx_cnt[v] += 1

if len(even_idx_cnt) == 1 and len(odd_idx_cnt) == 1:
    if even_idx_cnt.keys() == odd_idx_cnt.keys():
        print(N - even_idx_cnt[V[0]])
    else:
        print(0)
    exit()

even_idx_cnt = sorted(even_idx_cnt.items(), key=lambda  x:x[1], reverse=True)
odd_idx_cnt = sorted(odd_idx_cnt.items(), key=lambda  x:x[1], reverse=True)

if even_idx_cnt[0][0] != odd_idx_cnt[0][0]:
    print(N - even_idx_cnt[0][1] - odd_idx_cnt[0][1])
elif even_idx_cnt[0][0] > odd_idx_cnt[0][0]:
    print(N - even_idx_cnt[0][1] - odd_idx_cnt[1][1])
else:
    print(N - even_idx_cnt[1][1] - odd_idx_cnt[0][1])
N = int(input())
V = list(map(int, input().split()))

even_idx_cnt = {}
odd_idx_cnt = {}
for idx, v in enumerate(V):
    if idx % 2 == 0:
        if v not in even_idx_cnt:
            even_idx_cnt[v] = 0
        even_idx_cnt[v] += 1
    else:
        if v not in odd_idx_cnt:
            odd_idx_cnt[v] = 0
        odd_idx_cnt[v] += 1

if len(even_idx_cnt) == 1 and len(odd_idx_cnt) == 1:
    if even_idx_cnt.keys() == odd_idx_cnt.keys():
        print(N - even_idx_cnt[V[0]])
    else:
        print(0)
    exit()

even_idx_cnt = sorted(even_idx_cnt.items(), key=lambda  x:x[1], reverse=True)
odd_idx_cnt = sorted(odd_idx_cnt.items(), key=lambda  x:x[1], reverse=True)

if even_idx_cnt[0][0] != odd_idx_cnt[0][0]:
    print(N - even_idx_cnt[0][1] - odd_idx_cnt[0][1])
elif len(even_idx_cnt[0][0]) == 1:
    print(N - even_idx_cnt[0][1] - odd_idx_cnt[1][1])
elif len(odd_idx_cnt[0][0]) == 1:
    print(N - even_idx_cnt[1][1] - odd_idx_cnt[0][1])
else:
    if even_idx_cnt[1][0] > odd_idx_cnt[1][0]:
        print(N - even_idx_cnt[0][1] - odd_idx_cnt[1][1])
    else:
        print(N - even_idx_cnt[1][1] - odd_idx_cnt[0][1])


### FIXED CODE ###

from collections import Counter
import heapq

N = int(input())
Vs = list(map(int,input().split()))

if len(set(Vs)) == 1:
  print(N//2)
  exit()

Veve, Vodd = [],[]
idx = 0
for v in Vs:
  if idx%2 == 0: Veve.append(v)
  else: Vodd.append(v)
  idx += 1

Veve_cnt, Vodd_cnt = [], []
[heapq.heappush(Veve_cnt, [-num,val]) for val, num in Counter(Veve).items()]
[heapq.heappush(Vodd_cnt, [-num,val]) for val, num in Counter(Vodd).items()]

neg_num, val = heapq.heappop(Veve_cnt)
eve_val = val
eve_num = -neg_num

neg_num, val = heapq.heappop(Vodd_cnt)
odd_val = val
odd_num = -neg_num

if eve_val != odd_val:
  print(N-eve_num-odd_num)
else:
  if len(Vodd_cnt) != 0:odd_num2 = -heapq.heappop(Vodd_cnt)[0]
  else:odd_num2 = -float('inf')

  if len(Veve_cnt) != 0:eve_num2 = -heapq.heappop(Veve_cnt)[0]
  else:eve_num2 = -float('inf')

  print(min(N-eve_num2-odd_num,N-eve_num-odd_num2))
n = int(input())
a_list = list(map(int, input().split()))
q = int(input())
change_list = [list(map(int, input().split())) for _ in range(q)]

cnt = [0] * 10**5
tot = sum(a_list)

for i in range(n):
    cnt[a_list[i]] += 1
#print(cnt)

for j in range(q):
    tot += cnt[change_list[j][0]] * (change_list[j][1]-change_list[j][0])
    cnt[change_list[j][1]] += cnt[change_list[j][0]]
    cnt[change_list[j][0]] = 0
    print(tot)

### FIXED CODE ###

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

cnt = [0] * 10**6
tot = sum(a_list)

for i in range(n):
    cnt[a_list[i]] += 1
#print(cnt)

for j in range(q):
    tot += cnt[change_list[j][0]] * (change_list[j][1]-change_list[j][0])
    cnt[change_list[j][1]] += cnt[change_list[j][0]]
    cnt[change_list[j][0]] = 0
    print(tot)
import numpy as np
n=int(input())
lista=list(map(int,input().split()))
lista=sorted(lista)
for i in range(n-1):
    lista.append((lista[i]+lista[i+1])/2)
    lista.pop(i+1)
    lista.pop(i)
print(lista[0])

### FIXED CODE ###

import numpy as np
n=int(input())
lista=list(map(int,input().split()))
lista.sort()

for i in range(n-1):
    lista.append((lista[0]+lista[1])/2)
    lista.pop(0)
    lista.pop(0)
    lista.sort()
    
print(lista[0])
a, b = input().split(' ')
if int(a) * int(b) % 2 == 0:
    print('Even')
    continue
print('Odd')

### FIXED CODE ###

a, b = input().split(' ')
if int(a) * int(b) % 2 == 0:
    print('Even')
else:
    print('Odd')
import sys
sys.setrecursionlimit(10**7)
# input = sys.stdin.readline().rstrip

"""
まず一般に剰余込みでの組み合わせの計算。
n!, (n!)^{-1} mod pの値を配列にまとめておき、nCr = (n!)/(r!)((n-r)!)をO(1)で計算する。

max = (用意する配列の最大長)
mod = （剰余）

(n!)^{-1}の計算は¥Prod_i i^{-1}を計算して求める。
i^{-1} mod pの計算はフェルマーの小定理より、mod pにおいて
0 = p = (p // i) * i + (p % i)
0 = (p // i) + (p % i) * i^{-1}
i^{-1} = -(p // i) * (p % i)^{-1}
"""

max = 10**6
mod = 10**9+7
fact = [1, 1] # fact[n] = (n! mod p)
factinv = [1, 1] # factinv[n] = ((n!)^{-1} mod p)
inv = [0, 1] # inv[n] = (n^{-1} mod p)

for i in range(2, max+1):
    fact.append(fact[-1] * i % mod)
    inv.append(-inv[mod % i] * (mod // i) % mod)
    factinv.append(factinv[-1] * inv[-1] % mod)

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


"""
いよいよ本題。
まずは¥Sum_{0¥le i¥le x, 0¥le j¥le y} _{i+j}C_iを計算する。
実際今回の問題は容易にこれに帰着可能。

¥Sum_{0¥le i¥le x, 0¥le j¥le y} _{i+j}C_i
    = ¥Sum_i (¥Sum_j _{i+j}C_i)
    = ¥Sum_i {(T+1)^i + (T+1)^{i+1} + ... + (T+1)^{i+y})のT^iの係数}
    = ¥Sum_i {¥frac{(1+T)^{i+y+1} - (1+T)^i}{T}のT^iの係数}
    = ¥Sum_i _{i+y+1}C_{i+1}

    = ¥Sum_i _{i+y+1}C_y
    = _{y+1}C_y + _{y+2}C_y + ... + _{y+x+1}C_y
    = {(1+T)^{y+1} + (1+T)^{y+2} + ... (1+T)^{y+x+1}のT^yの係数}
    = {¥frac{(1+T)^{x+y+2} - (1+T)^{y+1}}{T}のT^yの係数}
    = _{x+y+2}C_{y+1} - 1
"""
r1, c1, r2, c2 = map(int, input().split())
a = cmb(r2+c2+2, c2+1) - 1
b = cmb(r1+c2+1, c2+1) - 1
c = cmb(r2+c1+1, r2+1) - 1
d = cmb(r1+c1, r1) - 1
ans = a - b - c + d
print(ans)


### FIXED CODE ###

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

"""
まず一般に剰余込みでの組み合わせの計算。
n!, (n!)^{-1} mod pの値を配列にまとめておき、nCr = (n!)/(r!)((n-r)!)をO(1)で計算する。

max = (用意する配列の最大長)
mod = （剰余）

(n!)^{-1}の計算は¥Prod_i i^{-1}を計算して求める。
i^{-1} mod pの計算はフェルマーの小定理より、mod pにおいて
0 = p = (p // i) * i + (p % i)
0 = (p // i) + (p % i) * i^{-1}
i^{-1} = -(p // i) * (p % i)^{-1}
"""

max = 10**6 * 2 + 3 # ここでRE出しまくってた。。。
mod = 10**9+7
fact = [1, 1] # fact[n] = (n! mod p)
factinv = [1, 1] # factinv[n] = ((n!)^{-1} mod p)
inv = [0, 1] # inv[n] = (n^{-1} mod p)

for i in range(2, max+1):
    fact.append(fact[-1] * i % mod)
    inv.append(-inv[mod % i] * (mod // i) % mod)
    factinv.append(factinv[-1] * inv[-1] % mod)

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


"""
いよいよ本題。
まずは¥Sum_{0¥le i¥le x, 0¥le j¥le y} _{i+j}C_iを計算する。
実際今回の問題は容易にこれに帰着可能。

¥Sum_{0¥le i¥le x, 0¥le j¥le y} _{i+j}C_i
    = ¥Sum_i (¥Sum_j _{i+j}C_i)
    = ¥Sum_i {(T+1)^i + (T+1)^{i+1} + ... + (T+1)^{i+y})のT^iの係数}
    = ¥Sum_i {¥frac{(1+T)^{i+y+1} - (1+T)^i}{T}のT^iの係数}
    = ¥Sum_i _{i+y+1}C_{i+1}

    = ¥Sum_i _{i+y+1}C_y
    = _{y+1}C_y + _{y+2}C_y + ... + _{y+x+1}C_y
    = {(1+T)^{y+1} + (1+T)^{y+2} + ... (1+T)^{y+x+1}のT^yの係数}
    = {¥frac{(1+T)^{x+y+2} - (1+T)^{y+1}}{T}のT^yの係数}
    = _{x+y+2}C_{y+1} - 1
"""
r1, c1, r2, c2 = map(int, input().split())
a = cmb(r2+c2+2, c2+1) - 1
b = cmb(r1+c2+1, c2+1) - 1
c = cmb(r2+c1+1, r2+1) - 1
d = cmb(r1+c1, r1) - 1
ans = a - b - c + d
print(ans % mod)