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

from fractions import gcd

N = int(input())
A = list(map(int,input().split()))
mod = 10**9+7

l = A[0]
for i in range(N-1):
    l = l*A[i+1]//gcd(l,A[i+1])

ans = 0
for i in range(N):
    ans = (ans + l//A[i]) % mod

print(ans)

### FIXED CODE ###

def main():
    from math import sqrt
    from fractions import gcd
    from collections import defaultdict
    from copy import deepcopy

    N = int(input())
    A = list(map(int, input().split()))
    mod = 10 ** 9 + 7

    p = [1] * (1001)
    P = []  # 1000までの素数表
    p[0] = p[1] = 0
    for x in range(2, int(sqrt(1000000)) + 1):
        if p[x]:
            P.append(x)
            for y in range(x * x, 1001, x):
                p[y] = 0

    B = [defaultdict(int) for i in range(N)]  # N個の数を素因数分解したもの
    lcm = defaultdict(int)  # N個の数のlcmを素因数分解したもの

    for i in range(N):
        for j in P:
            if A[i] % j == 0:
                while A[i] % j == 0:
                    A[i] //= j
                    B[i][j] += 1
            lcm[j] = max(lcm[j], B[i][j])
        if A[i] != 1:
            B[i][A[i]] = 1
            lcm[A[i]] = 1

    l = 1  # N個の数のlcm
    for i in lcm.keys():
        l = (l * pow(i, lcm[i], mod)) % mod

    ans = 0
    # l/A[i]の和を求めていく
    for i in range(N):
        r = l
        for j in list(B[i].keys()):
            r = (r * pow(j, mod - B[i][j] - 1, mod)) % mod
        ans = (ans + r) % mod

    print(ans)

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

# coding: utf-8
a = int(input())
b = list(map(int, input().split()))
c = 1
for i in b:
  c = c * i
if c > 10 ** 18:
  print(-1)
else:
  print(c)

### FIXED CODE ###

# coding: utf-8
a = int(input())
b = list(map(int, input().split()))
c = 1
if 0 in b:
    print(0)
else:
  while c < 10 ** 18 and len(b) != 0:
    c = c * b[0]
    del b[0]
  if c > 10 ** 18:
    print(-1)
  else:
    print(c)
### BUGGY CODE ###

A = list(map(int, input().split())) 
N = A[0]
K = A[1]
Q = A[2]
n = [K for _ in range(N)]
for _ in range(Q):
    answer = int(input()) - 1
    for i in range(N):
        if(i != answer):
            n[i] -= 1

for i in range(N):
    if(n[i] > 0):
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

A = list(map(int, input().split())) 
N = A[0]
K = A[1]
Q = A[2]
n = [K for _ in range(N)]
for i in range(N):
    n[i] -= Q
for _ in range(Q):
    ans = int(input()) - 1
    n[ans] += 1
for i in range(N):
    if(n[i] > 0):
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

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


for i in range(k):
    if a>=1:
        a -=1
    elif a<1 & b>=1:
        b -=1
    else:
        a=b=0
print(a,b)


### FIXED CODE ###

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

if a>=k:
    a = a-k
    k = 0
    print(a,b)
elif a<k:
    k =k-a
    a =0
    print(0, max(0,b-k))
### BUGGY CODE ###

K,S = [int(i) for i in input().split()]
ans = 0
for X in range(K+1):
  for Y in range(K+1):
    Z = S-X-Y
    if 0<=Z<=K and X+Y+Z==S:
      ans += 1
print(ans)

### FIXED CODE ###

K,S = [int(i) for i in input().split()]
ans = 0
for X in range(K+1):
  for Y in range(K+1):
    Z = S-X-Y
    if 0<=Z<=K:
      ans += 1
print(ans)
### BUGGY CODE ###

n, d, a = map(int, input().split())
m = [list(map(int, input().split())) for _ in range(n)]
m.sort()
bomb = [0 for _ in range(n)]
r = 1
d *= 2
for i in range(n):
    while r < n and m[i][0] + d >= m[r][0]:
        r += 1
    bomb[i] = r - 1
res = 0
for i in range(n):
    if m[i][1] > 0:
        tres = (m[i][1] + a - 1) // a
        res += tres
        dh = tres * a
        for j in range(i, bomb[i] + 1):
            m[j][1] -= dh
print(res)


### FIXED CODE ###

from collections import deque
n, d, a = map(int, input().split())
m = [list(map(int, input().split())) for _ in range(n)]
m.sort()
r = 1
d *= 2
q=deque([])
for i in range(n):
    while r < n and m[i][0] + d >= m[r][0]:
        r += 1
    m[i].append(r)
    m[i][1] = (m[i][1] + a - 1) // a
res = 0
tdamage = 0
for i in range(n):
    while q and q[0][0] <= i:
        minus = q.popleft()
        tdamage -= minus[1]
    m[i][1] -= tdamage
    if m[i][1] > 0:
        res += m[i][1]
        tdamage += m[i][1]
        q.append([m[i][2],m[i][1]])
print(res)
### BUGGY CODE ###

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

c = 0
hoge = []

for i in range(len(A)):
  hoge.append(max(A[0:i+1]))

print(sum(hoge)-sum(A))

### FIXED CODE ###

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

c = 0
mae = A[0]

for i in A:
  if i < mae:
    c += mae - i
  else:
    mae = i

print(c)
### BUGGY CODE ###

n, m = map(int, input().split())
Gr = {}
R = []
for i in range(m):
    l, r, d = map(int, input().split())
    Gr[(l - 1, r - 1)] = d
    Gr[(r - 1, l - 1)] = -d
    if l - 1 not in R:
        R.append(l - 1)
    if r - 1 not in R:
        R.append(r - 1)


rec = True
for i in Gr:
    for k in R:
        if (i[0], k) in Gr and (k, i[1]) in Gr:
            if Gr[i] != Gr[(i[0], k)] + Gr[(k, i[1])]:
                rec = False

if rec:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

import sys
sys.setrecursionlimit(200002)
N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    l, r, q = map(int, input().split())
    G[l - 1].append((r - 1, q))
    G[r - 1].append((l - 1, -q))
X = [None] * N


def dfs(u):
    global X, G
    for w, d in G[u]:
        if X[w] is None:
            X[w] = X[u] + d
            if not dfs(w):
                return False
        else:
            if X[w] != X[u] + d:
                return False

    return True


flag = True
for i in range(N):
    if X[i] is None:
        X[i] = 0
        flag &= dfs(i)

if flag:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
nega=[i for i in a if i<0]
zera=[i for i in a if i==0]
posa=[i for i in a if i>0]

def cnt(x):
  y=0
  if x>=0:
    y+=n*len(zera)
  
  for i in posa:
    y+=len([j for j in a if j*i<=x])
  
  for i in nega:
    y+=len([j for j in a if j*i<=x])
  
  y-=len([j for j in a if j*j<=x])
  return y//2

r=10**18
l=-r-1
while r-l>1:
  c=(r+l)//2
  if cnt(c)>=k:
    r=c
  else:
    l=c
print(r)

### FIXED CODE ###

import numpy as np
n,k=map(int,input().split())
a=list(map(int,input().split()))
a=np.array(a)
a.sort()
nega=a[a<0]
zera=a[a==0]
posa=a[a>0]

def cnt(x):
  y=0
  if x>=0:
    y+=n*len(zera)
  y+=np.searchsorted(a,x//posa,side="right").sum()
  y+=n*len(nega)-np.searchsorted(a,-(-x//nega)).sum() 
  y-=len(a[a*a<=x])
  return y//2

r=10**18
l=-r-1
while r-l>1:
  c=(r+l)//2
  if cnt(c)>=k:
    r=c
  else:
    l=c
print(r)
### BUGGY CODE ###

from math import sqrt
from collections import deque

h = {1: 'COUNTER_CLOCKWISE',
       2: 'CLOCKWISE',
       3: 'ONLINE_BACK',
       4: 'ONLINE_FRONT',
       5: 'ON_SEGMENT',}

def dot(a, b):
    return sum([i * j for i,j in zip(a, b)])

def sub(a, b):
    return [a[0] - b[0],a[1] - b[1]]

def cross(a, b):
    return  a[0] * b[1] - a[1] * b[0]

def _abs(a):
    return sqrt(a[0] ** 2 + a[1] ** 2)

def ccw(a, b, c):
    x = sub(b, a)
    y = sub(c, a)
    if cross(x, y) > 0: return 1
    if cross(x, y) < 0: return 2
    if dot(x, y) < 0: return 3
    if _abs(x) < _abs(y): return 4
    return 5

def CCW(a,b,c):
    return h[ccw(a,b,c)]

n = int(input())
c = [list(map(int, input().split())) for i in range(n)]
c.sort(key=lambda x: (x[0], x[1]))
U = deque(c[:2])

for i in range(2, n):
    j = len(U)
    while j >= 2 and CCW(U[-1],U[-2],c[i])  == "COUNTER_CLOCKWISE":
        U.pop()
        j -= 1
    U.append(c[i])

c = c[::-1]
L = deque(c[:2])

for i in range(2, n):
    j = len(L)
    while j >= 2 and CCW(L[-1], L[-2], c[i])  == "COUNTER_CLOCKWISE":
        L.pop()
        j -= 1
    L.append(c[i])

ans = []
for x,y in U:
    ans.append([x,y])
for x, y in L:
    if not [x,y] in U:
        ans.append([x,y])
print(len(ans))

first = sorted(ans,key=lambda x: (x[1], x[0]))[0]
i = ans.index(first)
for x,y in ans[i:] + ans[:i]:
    print(x, y)


### FIXED CODE ###

from math import sqrt
from collections import deque

def sub(a, b):
    return [a[0] - b[0],a[1] - b[1]]

def cross(a, b):
    return  a[0] * b[1] - a[1] * b[0]

def ccw(a, b, c):
    x = sub(b, a)
    y = sub(c, a)
    return cross(x, y) > 0

n = int(input())
c = [list(map(int, input().split())) for i in range(n)]
c.sort(key=lambda x: (x[0], x[1]))
U = deque(c[:2])

for i in range(2, n):
    j = len(U)
    while j >= 2 and ccw(U[-1],U[-2],c[i]):
        U.pop()
        j -= 1
    U.append(c[i])

c = c[::-1]
L = deque(c[:2])

for i in range(2, n):
    j = len(L)
    while j >= 2 and ccw(L[-1], L[-2], c[i]):
        L.pop()
        j -= 1
    L.append(c[i])

ans = U
for i in range(1,len(L)-1):
    x, y = L[i]
    ans.append([x,y])

print(len(ans))
i = ans.index(sorted(ans, key=lambda x: (x[1],x[0]))[0])
ans = list(ans)
for x,y in ans[i:] + ans[:i]:
    print(x, y)
### BUGGY CODE ###

X=input()
a=list()
for i in range(len(X)):
    a.append(int(X[i:len(X)])%2019)
S=a.count(0)
for j in range(1,2018):
    b=a.count(j)
    S+=int(b*(b-1)/2)
print(S)  


### FIXED CODE ###

s=list(input())
mod=2019
A=[0]*2019
a=0
b=1
for i in range(len(s)):
  a=(a+int(s[-1-i])*b)%mod
  A[a]+=1
  b=b*10%mod
ans=A[0]*(A[0]+1)//2
for i in range(1,2019):
  if A[i]!=0:
    ans=ans+(A[i]-1)*A[i]//2
print(ans)
### BUGGY CODE ###

n, k, *hs = [int(x) for x in open(0).read().split()]           
l = len(hs)                                                    
delta = lambda a, b: abs(hs[a] - hs[b])                        
dp = [0]                                                       
for i in range(1, l):                                          
    cs = [dp[j] + delta(i, j) for j in range(max(0, i - k), i)]
    v = min(cs)                                                
    dp.append(v)                                               
print(dp[-1])                                                  

### FIXED CODE ###

def main():
    n, k, *h = map(int, open(0).read().split())
    dp = [float("inf")] * n
    dp[0] = 0
    for i in range(1, n):
        min_j = max(0, i-k)
        dp[i] = min([dp[j] + abs(h[i] - h[j]) for j in range(min_j, i)])
    print(dp[n-1])

main()
### BUGGY CODE ###

from collections import defaultdict

n, k = map(int, input().split())
hhh = list(map(int, input().split()))
INF = 10 ** 18
dp = defaultdict(lambda: INF)
dp[0, 0] = 0
for h in hhh:
    ndp = defaultdict(lambda: INF)
    for (changed, prev_h), operate in dp.items():
        if h == prev_h:
            ndp[changed, h] = min(ndp[changed, h], operate)
        elif h > prev_h:
            ndp[changed, h] = min(ndp[changed, h], operate + h - prev_h)
            if changed < k:
                ndp[changed + 1, prev_h] = min(ndp[changed + 1, prev_h], operate)
        else:
            ndp[changed, h] = min(ndp[changed, h], operate)
            if changed < k:
                ndp[changed + 1, prev_h] = min(ndp[changed + 1, prev_h], operate)
    dp = ndp
print(min(dp.values()))


### FIXED CODE ###

from collections import defaultdict

n, k = map(int, input().split())
hhh = list(map(int, input().split()))
INF = 10 ** 18
dp = defaultdict(lambda: INF)
dp[0] = 0
mask1 = (1 << 10) - 1
mask2 = ((1 << 63) - 1) ^ mask1

for h in hhh:
    ndp = defaultdict(lambda: INF)
    h_key = h << 10
    for changed_prev_h, operate in dp.items():
        changed = changed_prev_h & mask1
        prev_h = changed_prev_h >> 10
        if h == prev_h:
            key = h_key + changed
            ndp[key] = min(ndp[key], operate)
        elif h > prev_h:
            key = h_key + changed
            ndp[key] = min(ndp[key], operate + h - prev_h)
            if changed < k:
                key = changed_prev_h + 1
                ndp[key] = min(ndp[key], operate)
        else:
            key = h_key + changed
            ndp[key] = min(ndp[key], operate)
            if changed < k:
                key = changed_prev_h + 1
                ndp[key] = min(ndp[key], operate)
    # print(h)
    # print(dict(dp))
    # print(dict(ndp))
    dp = ndp
print(min(dp.values()))
### BUGGY CODE ###

import heapq

N, M = [int(_) for _ in input().split(' ')]
ABs = {}
r = 0

for i in range(N):
    A, B = [int(x) for x in input().split()]

    if A in ABs:
        heapq.heappush(ABs[A], -B)
    else:
        ABs[A] = [-B]
        heapq.heapify(ABs[A])

for m in range(M, 0, -1):
    B_max = -1
    A_max = -1

    for a in range(m, 0, -1):
        if not (a in ABs) or len(ABs[a]) == 0:
            continue

        b = - ABs[a][0]
        if B_max < b:
            A_max = a
            B_max = b

    if A_max != -1:
        r -= heapq.heappop(ABs[A_max])

print(r)


### FIXED CODE ###

import heapq

N, M = [int(_) for _ in input().split()]
ABs = [[] for _ in range(M + 1)]
r = 0

for i in range(N):
    A, B = [int(x) for x in input().split()]
    if A <= M:
        ABs[A].append(-B)

q = []

for m in range(1, M + 1):
    if ABs[m] != 0:
        for b in ABs[m]:
            heapq.heappush(q, b)

    if len(q) != 0:
        r -= heapq.heappop(q)

print(r)
### BUGGY CODE ###

n ,k = map(int,input().split())
h = list(map(int,input().split()))
flag = 0
ans = 0
for i in range(k):
  if n <= k:
    break
  re = max(h)
  h.remove(re)
  flag += 1
for i in range(n - flag):
  if n <= k:
    ans = 0
  else:
    ans += h[i]
print(ans)

### FIXED CODE ###

n, k = map(int,input().split())
h = list(map(int,input().split()))
ans = 0
sort = sorted(h)
for i in range(n-k):
  ans += sort[i]
print(ans)
### BUGGY CODE ###

import sys
N, M = map(int, input().split())
X = [int(_) for _ in input().split()]
X.sort()
A = []
if N >= M:
    print(0)
    sys.exit()
else:
    for i in range(M - 1):
        A.append(X[i + 1] - X[i])
    for i in range(N - 1):
        A.remove(max(A))
sum = sum(A)
print(sum)

### FIXED CODE ###

import sys
N, M = map(int, input().split())
X = sorted(list(map(int,input().split())))
A = []
sum = 0
if N >= M:
    print(0)
    sys.exit()
else:
    for i in range(M - 1):
        A.append(X[i + 1] - X[i])
    A = sorted(A, reverse = True)
    for k in A[N - 1:]:
        sum += k
print(sum)
### BUGGY CODE ###

from collections import deque
import copy
H, W = map(int,input().split())

A = [[False for _ in range(W)] for _ in range(H)]

Start = []
for y in range(H):
    S = input()
    for x, s in enumerate(S):
        if s == "#":
            Start.append((y, x))
            A[y][x] = True
Q = deque(Start)

ans = 0
while True:
    ans += 1
    NQ = deque()
    while Q:
        y, x = Q.popleft()
        if x > 0 and A[y][x-1] == False:
            A[y][x-1] = True
            NQ.append((y,x-1))
        if x < W-1 and A[y][x+1] == False:
            A[y][x+1] = True
            NQ.append((y,x+1))
        if y > 0 and A[y-1][x] == False:
            A[y-1][x] = True
            NQ.append((y-1, x))
        if y < H-1 and A[y+1][x] == False:
            A[y+1][x] = True
            NQ.append((y+1,x))
    if NQ:
        Q = copy.copy(NQ)
    else:
        break

print(ans-1)

### FIXED CODE ###

def main():
    H, W = map(int,input().split())

    A = [[False for _ in range(W)] for _ in range(H)]

    Q = []
    for y in range(H):
        S = input()
        for x, s in enumerate(S):
            if s == "#":
                Q.append((y, x))
                A[y][x] = True

    ans = 0
    while Q:
        ans += 1
        NQ = []
        for y, x in Q:
            if x > 0 and A[y][x-1] == False:
                A[y][x-1] = True
                NQ.append((y,x-1))
            if x < W-1 and A[y][x+1] == False:
                A[y][x+1] = True
                NQ.append((y,x+1))
            if y > 0 and A[y-1][x] == False:
                A[y-1][x] = True
                NQ.append((y-1, x))
            if y < H-1 and A[y+1][x] == False:
                A[y+1][x] = True
                NQ.append((y+1,x))
        if NQ:
            Q = NQ
        else:
            break

    print(ans-1)

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

N = int(input())
A = [int(input()) for i in range(N)]
# maxA = max(A)
for x in range(len(A)):
    a_tmp = A[x]
    A[x] = 0
    print(max(A))
    A[x] = a_tmp


### FIXED CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
maxA = max(A)
copy_A = A[:]
copy_A.remove(maxA)
secondA = max(copy_A)
for x in A:
    if x == maxA:
        print(secondA)
    else:
        print(maxA)
### BUGGY CODE ###

import sys
from collections import deque

def main():
    input = sys.stdin.readline
    N = int(input())
    ans = 0
    q = deque()
    first_b = 0
    last_a = 0
    for _ in range(N):
        s = str(input().strip())
        for i in range(len(s)):
            if s[i:i+2] == 'AB':
                ans += 1

        if s[0] == 'B' or s[-1] == 'A':
            if s[0] == 'B':
                first_b += 1
            if s[-1] == 'A':
                last_a += 1
            q.append(s)

    while first_b * last_a != 0 and len(q) > 1:
        q_ = deque()
        s = q.popleft()
        while len(q) > 0:
            s1 = q.popleft()

            if s[-1] == 'A' and s1[0] == 'B':
                ans += 1
                last_a -= 1
                first_b -= 1
                s = s[0] + s1[-1]
            elif s[0] == 'B' and s1[-1] == 'A':
                ans += 1
                last_a -= 1
                first_b -= 1
                s = s1[0] + s[-1]
            else:
                q_.append(s1)

        q_.append(s)
        q = q_

    return ans


if __name__ == '__main__':
    print(main())


### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    ans = 0
    ba = 0  # Num. of str that the first letter is B and the last one is A.
    xa = 0  # Num. of str that the last letter is A and the first one is not B.
    bx = 0  # Num. of str that the first letter is B and the last one is not A.
    for _ in range(N):
        s = str(input().strip())

        # Count the number of AB contained in the initial strings.
        for i in range(len(s)):
            if s[i:i+2] == 'AB':
                ans += 1

        if s[0] == 'B' and s[-1] == 'A':
            ba += 1
        elif s[-1] == 'A':
            xa += 1
        elif s[0] == 'B':
            bx += 1

    if ba == 0:
        # One xa ans one bx make one new "AB".
        #   xa + bx -> xABx
        ans += min(xa, bx)

    elif max(xa, bx) == 0:
        # N of ba make N-1 new "AB".
        # BxxA + BxxA + ... + BxxA -> BxxABxxAB...ABxxA
        ans += ba - 1

    else:  # There is at least one bx or ax and at least one ba.
        # N of ba make N-1 new "AB" and a ba.
        #   ba + ba + ... + ba -> baba...ba = ba
        # The last remaining ba and bx/ax make a new "AB" and a new bx/ax.
        #   ba + bx -> bABx = bx,  xa + ba -> xABa = xa
        # Then, bx and xa make a new "AB".
        #   xa + bx -> xABx 
        ans += ba + min(xa, bx)

    return ans


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

N = int(input())
A = list(map(int,input().split()))
Adic={}
for i in range(N):
  if A[i] not in Adic:
    Adic[A[i]] = 1
  else:
    Adic[A[i]] += 1
Aset = set(A)
if 1 in Aset: #1がある場合
  if Adic[1] == 1:
    print(1)
  else:
    print(0)
  exit()
ans = 0
for j in range(N):
  Flag = True
  temp = A[j]
  i = 2
  if Adic[temp] >= 2:
    continue
  for i in range(2, int(temp**0.5)+1):
    #print(i,temp)
    if temp%i == 0:
      #print(i,temp//i,temp)
      if i in Aset or temp//i in Aset:
        Flag = False
        #print(i,temp//i,"X")
        break
    #if temp%2 !=0: #奇数の時
    #  if i == 2:
    #    i = 3
    #  else:
    #    i += 2
    #else:
    #  i += 1
  if not Flag:
    continue
  ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
MAX = max(A) #Aの中の最大値
Adic={}
for i in range(N):
  if A[i] not in Adic:
    Adic[A[i]] = 1
  else:
    Adic[A[i]] += 1
Aset = set(A)
if 1 in Aset: #1がある場合
  if Adic[1] == 1:
    print(1)
  else:
    print(0)
  exit()
ans = 0
for j in range(N):
  temp = A[j]
  if Adic[temp] >= 2: #同じ数が複数ある場合には削除
    if temp in Aset:
      Aset.remove(temp)
  fmax = MAX//temp
  #print(fmax,temp)
  for i in range(2,fmax+10): #fmaxまで見る
    now = temp*i
    if now in Aset:
      Aset.remove(now)
#print(Aset)
print(len(Aset))
### BUGGY CODE ###

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

NN = 18
KK = (1 << (1 << NN)) - 1
I0 = KK // 3
I1 = KK // 5
I2 = KK // 17
I3 = KK // 257
I4 = KK // 65537
def popcount(x):
    x -= (x >> 1) & I0
    x = (x & I1) + ((x >> 2) & I1)
    x = (x + (x >> 4)) & I2
    x = (x + (x >> 8)) & I3
    x = (x + (x >> 16)) & I4
    for k in range(5, 18):
        x += x >> 2**k
    return x & 0x3ffff

N, M, Q = MAP()

# 出発前の列車の集合
S1 = [(1<<M)-1] * (N+1)
# 終着後の列車の集合
S2 = [0] * (N+1)
for i in range(M):
    l, r = MAP()
    l -= 1; r -= 1
    S1[l+1] ^= 1<<i
    S2[r] |= 1<<i
for i in range(1, N+1):
    S1[i] &= S1[i-1]
    S2[i] |= S2[i-1]

for i in range(Q):
    p, q = MAP()
    p -= 1; q -= 1
    pq = S1[p] & S2[q]
    print(popcount(pq))


### FIXED CODE ###

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

"""
参考：https://img.atcoder.jp/abc106/editorial.pdf
　　　https://www.hamayanhamayan.com/entry/2018/08/18/234325
・累積和
"""

N, M, Q = map(int, input().split())
lM, rM = [0] * M, [0] * M
pQ, qQ = [0] * Q, [0] * Q
LR = [[0] * N for i in range(N)]
# 都市番号を0-indexed
for i in range(M):
    l, r = map(int, input().split())
    lM[i], rM[i] = l-1, r-1
    LR[l-1][r-1] += 1
for i in range(Q):
    p, q = map(int, input().split())
    pQ[i], qQ[i] = p-1, q-1

# 始点固定で終点を動かした累積和を出す
cnt = [[0] * N for i in range(N)]
for i in range(N):
    cnt[i][i] = LR[i][i]
    for j in range(1, N):
        cnt[i][j] = cnt[i][j-1] + LR[i][j]

for i in range(Q):
    ans = 0
    for j in range(pQ[i], qQ[i]+1):
        # ある終点についてもう和が出てるので、
        # ここでは始点を動かして最終的な合計にする
        ans += cnt[j][qQ[i]]
    print(ans)