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

n,m,Q = map(int,input().split())

lrl = []
for _ in range(m):
    l,r = map(int,input().split())
    lrl.append((l,r))
    
lrl = sorted(lrl)

import bisect

for _ in range(Q):
    ans = 0
    p,q = map(int,input().split())
    lidx = bisect.bisect_left(lrl, (p,p))
    ridx = bisect.bisect_right(lrl, (q,q))
    new_lrl = lrl[lidx:ridx]
    print(len([i[1] for i in new_lrl if i[1] <= q]))
    
    
    
    

### FIXED CODE ###

#a[i][j]
def da_generate(h,w,a):
    da = [[0]*w for j in range(h)]
    da[0][0] = a[0][0]
    for i in range(1,w):
        da[0][i] = da[0][i-1]+a[0][i]
    for i in range(1,h):
        cnt_w = 0
        for j in range(w):
            cnt_w += a[i][j]
            da[i][j] = da[i-1][j]+cnt_w
    return da

#da_calc(p,q,x,y):(p,q)~(x,y)の長方形の和
def da_calc(p,q,x,y,da):
    if p > x or q > y:
        return 0
    if p == 0 and q == 0:
        return da[x][y]
    if p == 0:
        return da[x][y]-da[x][q-1]
    if q == 0:
        return da[x][y]-da[p-1][y]
    return da[x][y]-da[p-1][y]-da[x][q-1]+da[p-1][q-1]

n,m,q = map(int,input().split())
lrl = [[0 for i in range(n)] for j in range(n)]
for _ in range(m):
   l,r = map(int,input().split())
   lrl[l-1][r-1] += 1

da = da_generate(n, n, lrl)

for _ in range(q):
   p,q = map(int,input().split())
   p -= 1
   q -= 1
   print(da_calc(p,p,q,q,da))
### BUGGY CODE ###

n = int(input())
ss = [sorted(input()) for _ in range(n)]
ans = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        if ss[i] == ss[j]:
            ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
ss = sorted([sorted(input()) for _ in range(n)])
ans = 0
cnt = 1
for i in range(n - 1):
    if ss[i] != ss[i + 1]:
        ans += cnt * (cnt - 1) // 2
        cnt = 0
    cnt += 1
ans += cnt * (cnt - 1) // 2
print(ans)
### BUGGY CODE ###

n,k=map(int, input().split())
h=list(map(int, input().split()))
dp=[0]*n
for i in range(1,n):
    dp[i]=min([dpj+abs(h[i]-hj) for dpj,hj in zip(dp[max(0,i-k):i],h[max(0,i-k):i])])
print(dp[-1])

### FIXED CODE ###

n,k=map(int, input().split())
h=list(map(int, input().split()))
dp=[0]*n
for i in range(1,n):
    dp[i]=min([dpj+abs(h[i]-hj) for dpj,hj in zip(dp[max(0,i-k):i],h[max(0,i-k):i])])
print(dp[-1])
### BUGGY CODE ###

# print('input >>')
N = input()
A = list(map(int,(input().split())))

# print('----------output----------')

for i, k in enumerate(A):
    print(A.index(i+1)+1, end=' ')

### FIXED CODE ###

# print('input >>')
N = input()
A = list(map(int,(input().split())))

A_tuple_list = []

for i in range(len(A)):
    A_tuple_list.append((i, A[i]))

A_tuple_list.sort(key= lambda x:x[1])

# print('----------output----------')
for a in A_tuple_list:
    print(a[0]+1, end=' ')
### BUGGY CODE ###

h,w=map(int,input().split())
grid=[None]*h
INF=10**6
stack=[]
for i in range(h):
  s=list(input())
  for j in range(len(s)):
    if s[j]=="#":
      stack.append([i,j,0])
    s[j]=INF
  grid[i]=s
      
while stack:
  v=stack.pop()
  y=v[0]
  x=v[1]
  p=v[2]
  grid[y][x]=p
  if y-1>=0 and p+1<grid[y-1][x]:
    stack.append([y-1,x,p+1])
  if y+1<h and p+1<grid[y+1][x]:
    stack.append([y+1,x,p+1])
  if x-1>=0 and p+1<grid[y][x-1]:
    stack.append([y,x-1,p+1])
  if x+1<w and p+1<grid[y][x+1]:
    stack.append([y,x+1,p+1])
    
ans=0
for i in range(len(grid)):
  ans=max(ans,max(grid[i]))
print(ans)


### FIXED CODE ###

H,W=map(int,input().split())
INF=10**4
import numpy as np
a=np.full((H,W),INF,dtype=int)
for i in range(H):
  s=input()
  for j in range(len(s)):
    if s[j]=="#":
      a[i,j]=0

for i in range(0,W-1):
  np.minimum(a[:,i]+1,a[:,i+1],out=a[:,i+1])
for i in range(W-1,0,-1):
  np.minimum(a[:,i]+1,a[:,i-1],out=a[:,i-1])
for j in range(0,H-1):
  np.minimum(a[j,]+1,a[j+1,],out=a[j+1,])
for j in range(H-1,0,-1):
  np.minimum(a[j,]+1,a[j-1,],out=a[j-1,])

print(a.max())
### BUGGY CODE ###

import numpy as np
import sys
def input():
    return sys.stdin.readline()[:-1]

S = [int(x) if x!="?" else -1 for x in input()]

div_num = 1000000007
arr = np.arange(13, dtype = np.uint64)
dp = np.zeros([2, 13], dtype = np.uint64)

div13_list = [1]
for ii in range(1, len(S)):
    n = div13_list[-1] * 10 % 13
    if n in div13_list:
        break
    else:
        div13_list.append(n)
div13_mat = np.array([div13_list] * 10, dtype = int)
div13_mat = (div13_mat * np.arange(10)[:, None] % 13).T

if S[-1] == -1:
    dp[0, :10] = 1
else:
    dp[0, S[-1]] = 1

for ii in range(1, len(S)):
    ind = -ii-1
    tmp = div13_mat[ii%6]
    if S[ind] == -1:
        for n in range(10):
            # res = (div13_list[ii] * n + arr) % 13
            # res = (tmp[n] + arr) % 13
            res = np.roll(arr, -tmp[n])
            dp[1, res] += dp[0, arr]
    else:
        # res = (div13_list[ii] * S[ind] + arr) % 13
        # res = (tmp[S[ind]] + arr) % 13
        res = np.roll(arr, -tmp[S[ind]])
        dp[1, res] += dp[0, arr]
    dp[0] = dp[1] % div_num
    dp[1] = 0


print (dp[0, 5])


### FIXED CODE ###

import numpy as np
import sys
def input():
    return sys.stdin.readline()[:-1]

# S = [int(x) if x!="?" else -1 for x in input()]

# print (S)

# div_num = 1000000007
# arr = np.arange(13, dtype = np.uint64)
# # dp = np.zeros([2, 13], dtype = np.uint64)

# div13_list = [1]
# for ii in range(1, len(S)):
#     n = div13_list[-1] * 10 % 13
#     if n in div13_list:
#         break
#     else:
#         div13_list.append(n)
# div13_mat = np.array([div13_list] * 10, dtype = int)
# div13_mat = (div13_mat * np.arange(10)[:, None] % 13).T

# if S[-1] == -1:
#     dp[0, :10] = 1
# else:
#     dp[0, S[-1]] = 1

# for ii in range(1, len(S)):
#     # ind = -ii-1
#     # tmp = div13_mat[ii%6]
#     # if S[ind] == -1:
#     #     for n in range(10):
#     #         res = np.roll(arr, -tmp[n])
#     #         # dp[1, res] += dp[0, arr]
#     # else:
#     #     res = np.roll(arr, -tmp[S[ind]])
#     #     # dp[1, res] += dp[0, arr]
#     dp[0] = dp[1] % div_num
#     dp[1] = 0


# print (dp[0, 5])

#
# 大きい方の桁からやってく方法
#

MOD = 1000000007;

S = [int(x) if x!="?" else -1 for x in input()]
n = len(S)

# r[i]
# 現在考えてる一つ前の桁数で、余りが i になる整数の個数
r = [0] * 13

# まず一つ目の値が１の位とする
s = S[0]
if (s != -1):
    r[s] = 1
else:
    for i in range(10): r[i] = 1

# 桁を進めながら個数をカウント
for i in range(1, n):
    # dp[j]
    # 現在考えている桁(i)を除く、余りが j となる整数の個数
    dp = [0] * 26

    # 桁が一つ上がるので、一つ前の余りが 10 倍になる
    for j in range(13):
        dp[j*10%13] += r[j] % MOD

    # アクセスを高速にするため２倍の長さとる (dp[i] == dp[i + 13])
    dp[13:26] = dp[0:13]

    r = [0]*13

    s = S[i]
    if (s == -1):
        w = sum(dp[4:14])
        for j in range(13):
            r[j] += w
            w += dp[j + 1]-dp[j + 4]
    else:
        for j in range(13):
            r[j] += dp[13-s+j]
print (r[5]%MOD)
### BUGGY CODE ###

H,W=map(int,input().split())
A=[[False]*(W+2)]+\
  [[False] + [i=="." for i in input()] + [False] for _ in range(H)] + \
  [[False]*(W+2)]

q,r=[[] for _ in range(2000)],[]
for i in range(1,H+1):
    for j in range(1,W+1):
        if A[i][j]==False:
            q[0].append((i,j))
if len(q[0])==H*W:
    print(0)
    import sys
    sys.exit()
for k in range(2000):
    f=True
    for i,j in q[k]:
        if A[i-1][j]:
            A[i-1][j]=False
            q[k+1].append((i-1,j))
            f=False
        if A[i+1][j]:
            A[i+1][j]=False
            q[k+1].append((i+1,j))
            f=False
        if A[i][j-1]:
            A[i][j-1]=False
            q[k+1].append((i,j-1))
            f=False
        if A[i][j+1]:
            A[i][j+1]=False
            q[k+1].append((i,j+1))
            f=False
    if f:
        break
print(k)

### FIXED CODE ###

H,W = list(map(int,input().split()))
A = [list(str(input())) for i in range(H)]
 
black = []
 
cnt = 0
 
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            black.append([i,j])
 
length = len(black)
            
while (length < H*W):
    gray = []
    for l in black:
        if l[1] != 0:
            c1 = (l[0],l[1]-1)
            if A[c1[0]][c1[1]] == ".":
                gray.append(c1)
                A[c1[0]][c1[1]] = "#"
        if l[1] != W-1:
            c2 = (l[0],l[1]+1)
            if  A[c2[0]][c2[1]] == ".":
                gray.append(c2)
                A[c2[0]][c2[1]] = "#"
        if l[0] != 0:
            c3 = (l[0]-1,l[1])
            if  A[c3[0]][c3[1]] == ".":
                gray.append(c3)
                A[c3[0]][c3[1]] = "#"
        if l[0] != H-1:
            c4 = (l[0]+1,l[1])
            if  A[c4[0]][c4[1]] == ".":
                gray.append(c4)
                A[c4[0]][c4[1]] = "#"
    
    gray = list(set(gray))
    black = [l for l in gray]
    
    cnt += 1
    length += len(black)
    
print(cnt)
### BUGGY CODE ###

import numpy as np
n = int(input())
p_list = np.array(list(map(int, input().split())))
cnt = 0
for i in range(n):
  pi = p_list[i]
  if (p_list[:i] < pi).sum() == 0:  # piより前の値全てがpiより小さいとき
    cnt += 1
print(cnt)

### FIXED CODE ###

import numpy as np
n = int(input())
p_list = np.array(list(map(int, input().split())))
cnt = 0
minimum = np.inf
for i in range(n):
  pi = p_list[i]
  if minimum > pi:
    cnt += 1
    minimum = pi
print(cnt)
### BUGGY CODE ###

def main():
  N = int(input())
  A = list(map(int, input().split()))
  MOD = 10 ** 9 + 7
  ones = [sum(1 for a in A if a&(1<<i)) for i in range(60)]
  res = 0
  for j in range(N):
    a = A[j]
    for i in range(60):
      if (a >> i) & 1 == 0:
        res += ones[i] * ((2 ** i)%MOD)
      else:
        res += (N-ones[i]-j) * ((2 ** i)%MOD)
        ones[i] -= 1
      res %= MOD
  
  print(res)
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
  N = int(input())
  A = list(map(int, input().split()))
  MOD = 10 ** 9 + 7
  ones = [sum(1 for a in A if a&(1<<i)) for i in range(60)]
  res = 0
  for i in range(60):
    res += ones[i] * (N - ones[i]) * ((2 ** i) % MOD)
    res %= MOD
  print(res)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def int_to_bits(x):
    return [ 1 if 2**i & x != 0 else 0 for i in range(60) ]

def inv(x, MOD):
    return pow(x, MOD-2, MOD)

MOD = 10**9+7

debug = False

if debug:
    n = 50000
    A = list(range(n))
else:
    n,*A = get_all_int()




# ビットごとの出現回数 2**i
bits = [0] * 60

for a in A:
    for i in range(60):
        if 2**i & a != 0:
            bits[i] += 1

# log("bits:", bits)

ans = 0

for a in A:
    a_bits = int_to_bits(a)

    for i in range(60):
        ans += 2**i * abs(bits[i] - a_bits[i]*n)

    # a_dash = list(map(lambda a: a*(n-1), a_bits))

    # log("a_dash", a_dash)

    # bits_dash = [ bits[i] - a_bits[i] for i in range(60)]
    # log("bits_dash", bits_dash)
    # ans += sum( ( 2**i * abs(bits_dash[i]-2*a_dash[i])) for i in range(60) )

    # ans += sum( ( 2**i * abs(bits[i]-2*a_dash[i])) for i in range(60) )

    # for i in range(60):
    #     ans = (ans + 2**i * abs(bits_dash[i] - a_dash[i])) % MOD
    # log(a, ans)

print(ans//2 % MOD)


### FIXED CODE ###

import sys
import time

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def int_to_bits(x):
    return [ 1 if 2**i & x != 0 else 0 for i in range(60) ]

def inv(x, MOD):
    return pow(x, MOD-2, MOD)

start = time.time()

MOD = 10**9+7

debug = False

if debug:
    n = 30 * 10000
    A = list(range(n))
else:
    n,*A = get_all_int()

# ビットごとの出現回数 2**i
bits = [0] * 60

for a in A:
    for i in range(60):
        if 2**i & a != 0:
            bits[i] += 1

# log("bits:", bits)
# log("bits.", time.time() - start)

# ans = 0

ans = sum(( pow(2, i, MOD) * bits[i] * (n-bits[i]) for i in range(60))) % MOD

# for a in A:
#     # a_bits = [ 1 if 2**i & a != 0 else 0 for i in range(60) ]

#     for i in range(60):
#         ans += 2**i * abs(bits[i] - (1 if 2**i & a != 0 else 0) *n)

#     # a_dash = list(map(lambda a: a*(n-1), a_bits))

#     # log("a_dash", a_dash)

#     # bits_dash = [ bits[i] - a_bits[i] for i in range(60)]
#     # log("bits_dash", bits_dash)
#     # ans += sum( ( 2**i * abs(bits_dash[i]-2*a_dash[i])) for i in range(60) )

#     # ans += sum( ( 2**i * abs(bits[i]-2*a_dash[i])) for i in range(60) )

#     # for i in range(60):
#     #     ans = (ans + 2**i * abs(bits_dash[i] - a_dash[i])) % MOD
#     # log(a, ans)

# print(ans//2 % MOD)
print(ans)
# log("end.", time.time() - start)
### BUGGY CODE ###

from functools import reduce

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

for i in range(n):
  b[i] = reduce(lambda x,y : x^y,a[0:i+1]+a[i:])

print(" ".join(list(map(str,b))))

### FIXED CODE ###

from functools import reduce

n = int(input())
a = list(map(int,input().split()))
b = [0]*n
a_xor=reduce(lambda x,y : x^y,a)
for i in range(n):
  b[i]=a[i]^a_xor  
##  b[i] = reduce(lambda x,y : x^y,a[0:i+1]+a[i:])

print(" ".join(list(map(str,b))))
### BUGGY CODE ###

#ABC118C-MonstersBattleRoyale.py

from sys import stdin

input = stdin.readline

N = int(input())

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

A = set(A)
A = list(A)

a = 0

while len(A) != 1:
    A.sort()
    for i in range(1,len(A)):
        A[i] = A[i] - A[0]
    if A[0] == 0:
        A.pop(0)
    if len(A) <= N/10000:
        break

i = 0
while True:
    if A[i] != 0:
        print(A[i])
        break
    i += 1


### FIXED CODE ###

#ABC118C-MonstersBattleRoyale.py

from sys import stdin
from functools import reduce
import fractions

input = stdin.readline

N = int(input())

A = list(set(map(int,input().split())))

answer = reduce(fractions.gcd, A)
print(answer)
### BUGGY CODE ###

def bin_search1(L1,L2,l):#長すぎる辺の個数を返す
    low = 0
    high = len(l)-1
    while high-low>1:
        mid = (low+high)//2
        if (L1+L2<=l[mid]):#長すぎ
            high = mid
        else:
            low = mid
    if L1+L2>l[high]:#全部ok
        return 0
    elif L1+L2<=l[low]:#全部ng
        return len(l)
    else:
        return len(l)-high

def bin_search2(L1,L2,l):#短すぎる辺の個数を返す
    low = 0
    high = len(l)-1
    while high-low>1:
        mid = (low+high)//2
        if (abs(L1-L2)>=l[mid]):
            low = mid
        else:
            high = mid
    if abs(L1-L2)<l[low]:
        return 0
    elif abs(L1-L2)>=l[high]:
        return len(l)
    else:
        return high

N = int(input())
L = list(map(int,input().split()))
L.sort()

ans = 0

for i in range(N):
    for j in range(N):
        if i!=j:
            L_temp = L.copy()
            if i<j:
                L_temp.pop(j)
                L_temp.pop(i)
            else:
                L_temp.pop(i)
                L_temp.pop(j)

            ans += (N-2-bin_search1(L[i],L[j],L_temp)-bin_search2(L[i],L[j],L_temp))
         
        
ans = ans//6

print(ans)

### FIXED CODE ###

from bisect import bisect＿left

N = int(input())
L = list(map(int,input().split()))
L.sort()

ans = 0

for i in range(N-1):
    for j in range(i+1,N):
        ans += bisect_left(L,L[i]+L[j])-(j+1)

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

def check(ans, s):
    ret = 0
    for k, v in sumdic.items():
        if ans & k != ans:
            continue
        ret += v
        if ret >= s:
            return True
    return False


n, k = map(int, input().split())
A = list(map(int, input().split()))
sumA = [0]
for i in range(len(A)):
    sumA.append(sumA[i] + A[i])

sumdic = {}
for i in range(len(A)):
    for j in range(i + 1, len(A) + 1):
        tmp = sumA[j] - sumA[i]
        sumdic[tmp] = sumdic.get(tmp, 0) + 1
        # print(i, j)

# print(A)
# print(sumdic)

for i in reversed(range(len(format(sumA[-1], "b")))):
    # print(i)
    if check(2 ** i, k) is True:
        ans = 2 ** i
        tmp = i
        break
else:
    print(0)
    exit()

tmp -= 1
while(tmp != 0):
    if check(ans + 2 ** tmp, k) is True:
        ans += 2 ** tmp
    tmp -= 1
print(ans)

### FIXED CODE ###

def check(ans, s):
    ret = 0
    for k in sumdic:
        if ans & k != ans:
            continue
        ret += 1
        if ret >= s:
            return True
    return False


n, k = map(int, input().split())
A = list(map(int, input().split()))
sumA = [0]
for i in range(len(A)):
    sumA.append(sumA[i] + A[i])

sumdic = [0] * (n * (n + 1) // 2)
kk = 0
for i in range(len(A)):
    # print(kk, sumdic)
    for j in range(i + 1, len(A) + 1):
        tmp = sumA[j] - sumA[i]
        sumdic[kk + j - 1 - i] = tmp
        # print(i, j)
    kk += n - i

# print(A)
# print(Counter(sumdic))
# Sumdic = Counter(sumdic)

for i in reversed(range(len(format(sumA[-1], "b")))):
    # print(i)
    if check(2 ** i, k) is True:
        ans = 2 ** i
        tmp = i
        break
else:
    print(0)
    exit()

tmp -= 1
while(tmp != -1):
    if check(ans + 2 ** tmp, k) is True:
        ans += 2 ** tmp
    tmp -= 1
print(ans)
### BUGGY CODE ###

def expected_value(arr):
    return [(1 + ele) / 2 for ele in arr]

n, k = [int(x) for x in input().split()]
arr = list(map(int,input().split()))
ev = expected_value(arr)

sum_tmp = [sum(arr[i:i+k]) for i in range(n - (k - 1))]
max_v = max(sum_tmp)
max_i = sum_tmp.index(max_v)
print(sum(ev[0:max_i+k]) - sum(ev[0:max_i]))


### FIXED CODE ###

n, k = [int(x) for x in input().split()]
arr = list(map(int,input().split()))

m = sum(arr[0:k])
sump = m

for i in range(1, n-k+1):
    sump = sump - arr[i-1] + arr[i+k-1]
    if m < sump:
        m = sump

ans = (m + k) / 2

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

from math import factorial as fact
from itertools import combinations as comb


def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    ans = [0,0]
    tmp = 0
    for i,j in comb(a,2):
        t = fact(max(i,j))//(fact(max(i,j)-min(i,j))*fact(min(i,j)))
        if tmp < t:
            ans = [max(i,j),min(i,j)]
            tmp = t
    print(ans[0],ans[1])


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    ma = max(a)
    diff = 100000000000000
    ans = 0
    for aa in a:
        t = abs(ma//2-aa)
        if ma != aa and diff > t:
            diff = t
            ans = aa
    print(ma,ans)

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

n=int(input())
l=[int(k) for k in input().split()]
lnew={}
for i in l:
  if i in lnew:
    lnew[i]+=1
  else:lnew[i]=1

k=int(input())
for i in range(k):
  a,b=input().split()
  a=int(a)
  b=int(b)
  if a in lnew:
    c=0
    if b in lnew:
      c=lnew[b]
    lnew[b]=c+lnew[a]
  lnew.pop(a,None)
  Sum=0
  for num,val in lnew.items():
    Sum+=num*val
  print(Sum)

### FIXED CODE ###

n=int(input())
l=[int(k) for k in input().split()]
lnew={}
for i in l:
  if i in lnew:
    lnew[i]+=1
  else:lnew[i]=1
Sum=0
for num,val in lnew.items():
    Sum+=num*val
k=int(input())
for i in range(k):
  a,b=input().split()
  a=int(a)
  b=int(b)
  if a in lnew:
    Sum-=lnew[a]*a
    c=0
    if b in lnew:
      c=lnew[b]
      Sum-=lnew[b]*b
    lnew[b]=c+lnew[a]
    Sum+=lnew[b]*b
  lnew.pop(a,None)
  
  print(Sum)
### BUGGY CODE ###

MOD = 10**9+7
factmemo = [{} for _ in range((10**6+1))]
def fact(n):
    dict = factmemo[n]
    if dict!={}:
        return factmemo[n]
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            dict[i] = cnt

    if temp!=1:
        dict[temp] = 1

    if dict=={}:
        dict[n] = 1

    factmemo[n] = dict

    return dict

def lcm(arr):
    # 素因数分解をもとにarr全体のLCMを求める
    lcm = 1
    factor = {}
    for a in arr:
        f = fact(a)
        for k,v in f.items():
            if k in factor:
                tmp = factor[k]
                factor[k] = max(factor[k],v)
                lcm *= pow(k,max(0, v-tmp),MOD)
            else:
                factor[k] = v
                lcm *= pow(k,v,MOD)

    return lcm

def main():
    N = int(input())
    A = list(map(int, input().split()))
    # 方針.A全体のlcmをLとすると、ans=Σ(i=[0,N])x/Ai
    ans = 0
    L = lcm(A)
    for a in A:
        ans += (L//a)%MOD
        ans %= MOD
    print(ans)

main()


### FIXED CODE ###

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

def main():
    n=int(input())
    a=list(map(int,input().split()))
    mod=pow(10,9)+7
    lcma={}
    for ai in a:
      f=factorization(ai)
      for fi in f:
        if fi[0] in lcma:
          lcma[fi[0]]=max(lcma[fi[0]],fi[1])
        else:
          lcma[fi[0]]=fi[1]
    l=1
    for k,v in lcma.items():
      l*=pow(k,v,mod)
      l%=mod
    ans=0
    for ai in a:
      ans+=l*pow(ai,mod-2,mod)
      ans%=mod
    print(ans)

main()
### BUGGY CODE ###

import itertools
K, S = map(int, input().split())
ans = 0
for i in itertools.product(range(S+1), repeat=3):
  if sum(i) == S and all([j <= K for j in i]):
    ans += 1
print(ans)

### FIXED CODE ###

import itertools
K, S = map(int, input().split())
ans = 0
for i in itertools.product(range(K+1), repeat=2):
    Z = S - sum(i)
    if 0 <= Z <= K:
      ans += 1
print(ans)
# for x in range(K+1):
#  for y in range(K+1):
#    z = S - x - y
#    if 0 <= z <= K:
#      ans += 1
### BUGGY CODE ###

A, B, Q = map(int, input().split())
Sh = [int(input()) for _ in range(A)]
Te = [int(input()) for _ in range(B)]
inf = 10 ** 11 + 9
def move(x, s, t, d):
  ress = inf
  rest = inf
  if s >= 1:
    if t >= 1:
      #print(d, "dです")
      return d
  mins = inf
  tempi = 0
  temp = inf
  if s == 0:
    ress = 0
    for i in range(A):
      temp = min(mins, abs(x - Sh[i]))
      if mins != temp: tempi = i
      mins = temp
    #print(Sh[tempi], "ress")
    ress += move(Sh[tempi], s + 1, t + 0, d + abs(x - Sh[tempi]))
  
  tempi = 0
  temp = inf
  mint = inf
  if t == 0:
    rest = 0
    for i in range(B):
      temp = min(mint, abs(x - Te[i]))
      if mint != temp: tempi = i
      mint = temp
    #print(Te[tempi], "rest")
    rest += move(Te[tempi], s + 0, t + 1, d + abs(x - Te[tempi]))
  #print(ress, rest)
  return min(ress, rest)
for _ in range(Q):
  print(move(int(input()), 0, 0, 0))

### FIXED CODE ###

from bisect import bisect_left as bl
A, B, Q = map(int, input().split())
inf = 10 ** 11
Sh = [-1 * inf] + [int(input()) for _ in range(A)] + [inf]
Te = [-1 * inf] + [int(input()) for _ in range(B)] + [inf]
for _ in range(Q):
  x = int(input())
  b, d = bl(Sh, x), bl(Te, x)
  res = inf
  for S in [Sh[b - 1], Sh[b]]:
    for T in [Te[d - 1], Te[d]]:
      d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
      res = min(res, d1, d2)
  print(res)
### BUGGY CODE ###

import numpy as np

def main():
    N = int(input())
    A = np.array([None]*N)
    B = np.array([None]*N)
    for i in range(N):
        A[i],B[i] = map(int,input().split())
    ans = 0
    for i in range(N-1,-1,-1):
        if A[i]%B[i] == 0:
            continue
        ans += (B[i] - A[i]%B[i])
        A += (B[i] - A[i]%B[i])
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N = int(input())
    A = [None]*N
    B = [None]*N
    for i in range(N):
        A[i],B[i] = map(int,input().split())
    tmp = 0
    ans = 0
    for i in range(N-1,-1,-1):
        if (A[i]+tmp)%B[i] == 0:
            continue
        ans += (B[i] - (A[i]+tmp)%B[i])
        tmp += (B[i] - (A[i]+tmp)%B[i])
    print(ans)

if __name__ == '__main__':
    main()