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

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K=int(input())

i=1
r=0

while(i<K+1):
  j=1
  while(j<K+1):
    k=1
    while(k<K+1):
      if(i==1 or j==1 or k==1):
        r+=1
      elif(i==j and j==k):
        r+=i
      elif(i==j):
        r+=math.gcd(j,k)
      elif(j==k):
        r+=math.gcd(i,j)
      elif(i==k):
        r+=math.gcd(i,j)
      else:
        r+=gcd(i, j, k)
      k+=1
    j+=1
  i+=1

print(r)

### FIXED CODE ###

import math

K=int(input())
r=0

for i in range(1,K+1):
  for j in range(1,K+1):
    a=math.gcd(i,j)
    for k in range(1,K+1):
      b=math.gcd(a,k)
      r+=b
print(r)
### BUGGY CODE ###

x,y = map(int,input().split())

def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p

if (x+y)%3!=0:
    print(0)
else:
    a = (2*x - y) // 3
    b = (2*y - x) // 3

    print(comb(a+b, a, 10**9+7))

### FIXED CODE ###

x,y = map(int,input().split())

class ModComb:
    def __init__(self, MAX, mod=10 ** 9 + 7):
        fac = [1, 1]
        finv = [1, 1]
        inv = [0, 1]
        for i in range(2, MAX):
            fac.append(fac[i - 1] * i % mod)
            inv.append(mod - inv[mod % i] * (mod // i) % mod)
            finv.append(finv[i - 1] * inv[i] % mod)
        self.fac, self.finv, self.mod = fac, finv, mod
 
    def nCk(self, n, k):
        if n < k or n < 0 or k < 0:
            return 0
        fac, finv, mod = self.fac, self.finv, self.mod
        return fac[n] * (finv[k] * finv[n - k] % mod) % mod

if (x+y)%3!=0:
    print(0)
else:
    a = (2*x - y) // 3
    b = (2*y - x) // 3

    mod = 10 ** 9 + 7
    mc = ModComb(1000000, mod=mod) 

    print(mc.nCk(a + b, a) % mod)
### BUGGY CODE ###

import sys
input=sys.stdin.readline

def calc():
  mod=998244353
  n,s=map(int,input().split())
  arr=list(map(int,input().split()))
  dp=[[[0]*(s+1) for _ in range(n+1)] for _ in range(n+1)]
  dp[0][0][0]=1
  for i in range(1,n+1):
    val=arr[i-1]
    for j in range(i,-1,-1):
      for k in range(s,-1,-1):
        dp[i][j][k]=dp[i-1][j][k]
        if k-val>=0 and dp[i-1][j-1][k-val]!=0:
          dp[i][j][k]+=dp[i-1][j-1][k-val]
          dp[i][j][k]%=mod
  ans=0
  for i in range(1,n+1):
    ans+=dp[n][i][s]*pow(2,n-i,mod)
    ans%=mod
  print(ans)
calc()

### FIXED CODE ###

import sys
input=sys.stdin.readline

def calc():
  mod=998244353
  n,s=map(int,input().split())
  arr=list(map(int,input().split()))
  dp=[0]*(s+1)
  dp[0]=1
  ans=0
  for i in range(1,n+1):
    val=arr[i-1]
    for k in range(s,-1,-1):
      dp[k]*=2
      dp[k]%=mod
      if k>=val and dp[k-val]!=0:
        dp[k]+=dp[k-val]
        dp[k]%=mod
  print(dp[s]%mod)
calc()
### BUGGY CODE ###

K = int(input())

mod_ini = 7%K
mod = 0
cnt = 0

while True:
    cnt += 1
    mod = (mod*10 + 7)%K
    #print(mod)
    
    if mod == 0:
        print(cnt)
        break
    elif mod == mod_ini and cnt != 1:
        print(-1)
        break

### FIXED CODE ###

K = input()
K_1 = int(K[-1])
K = int(K) 

mod_ini = 7%K
mod = 0
cnt = 0

while True:
    if K%2 == 0 or K_1 == 5:
        print(-1)
        break
    
    cnt += 1
    mod = (mod*10 + 7)%K
    #print(mod)
    
    if mod == 0:
        print(cnt)
        break
    elif mod == mod_ini and cnt != 1:
        print(-1)
        break
### BUGGY CODE ###

N, K = map(int, input().split())
h = [i for i in map(int, input().split())]
memo = [0]*N
for i in range(N):
    mini = 10**10
    for j in range(i-min(i, K), i, 1):
        if memo[j] + abs(h[i]-h[j]) < mini:
            mini = memo[j] + abs(h[i]-h[j])
    if i != 0:
        memo[i] = mini
print(memo[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = [i for i in map(int, input().split())]
memo = [0]*N
for i in range(N):
    mini = 10**10
    for j in range(i-min(i, K), i, 1):
        if memo[j] + abs(h[i]-h[j]) < mini:
            mini = memo[j] + abs(h[i]-h[j])
    if i != 0:
        memo[i] = mini
print(memo[N-1])
### BUGGY CODE ###

n,k = map(int,input().split())
low = [0]*(10**5 * 3 + 1) #iで終わる長さ
for i in range(n):
    a = int(input())
    low[a] = max(low[max(0,a-k):a+k+1]) + 1
ans = max(low)
print(ans)

### FIXED CODE ###

# セグ木
# 使う操作
#####segfunc#####
def segfunc1(x, y):
    return max(x, y)
#################

#####ide_ele#####
ide_ele1 = -float('inf')
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

n,k = map(int,input().split())
low = [0]*(10**5 * 3 + 1)
seg = SegTree(low, segfunc1, ide_ele1)
for i in range(n):
    a = int(input())
    ma = seg.query(max(0,a-k), min(a+k+1,10**5 * 3 + 1))
    seg.update(a, ma+1)
ans = seg.query(0,10**5 * 3 + 1)
print(ans)
### BUGGY CODE ###

def main():
    N = int(input())
    S = list(str(input()))
    print()
    sum = 0
    for i in range(0, N-2):
        for j in range(i, N-1):
            for k in range(j, N):
                if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
                    if j - i != k -j:
                        sum += 1
    print(sum)



main()

### FIXED CODE ###

def main():
    N = int(input())
    S = list(str(input()))
    sum = S.count("R") * S.count("G") * S.count("B")
    for i in range(0, N-2):
        si = S[i]
        for j in range(i+1, N-1):
            sj = S[j]
            k = 2*j -i  # Nを超える
            if k < N:
                sk = S[k]
                #if j - i != k -j and si != sj and si != sk and sj != sk:
                if si != sj and si != sk and sj != sk:
                    sum -= 1
    print(sum)

    # 提出 #11871188


main()
### BUGGY CODE ###

n = int(input())
a = [int(x) for x in input().split()]

print(min(abs(sum(a[:i]) - sum(a[i:])) for i in range(1, n)))

### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]

left = 0
right = sum(a)

diff = []

for i in range(n - 1):
    left += a[i]
    right -= a[i]
    diff.append(abs(left - right))

print(min(diff))
### BUGGY CODE ###

n = int(input())
li = []
for i in range(n):
  li.append(input())
dic = {}
li_a = []
for x in li:
  if x not in li_a:
    dic[x] = 1
    li_a.append(x)
  else:
    dic[x] += 1
li_s = sorted(li_a)
li_ans = []
for x in li_s:
  li_ans.append(dic[x])
for i in range(len(li_ans)):
  if li_ans[i] == max(li_ans):
    print(li_s[i])
               
  

### FIXED CODE ###

n = int(input())
li = []
for i in range(n):
  li.append(input())
from collections import Counter
s = Counter(li)
a = list(s.values())
b = list(s.keys())
ans = []
m = 0
for x in a:
  m = max(m, x)
for i in range(len(a)):
  if a[i] == m:
    ans.append(b[i])
ans_a = sorted(ans)
ans_b = "\n".join(ans_a)
print(ans_b)
### BUGGY CODE ###

def divitorCount(n):
    count = 0
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            count+=1
            if i != n // i:
                count+=1
    return count

N = int(input())
sum = 0
for i in range(N):
  sum += (i+1)*divitorCount(i+1)

print(sum)

### FIXED CODE ###

def sumOfNaturalNumber(n):
  return n*(n+1)/2

N = int(input())

ans=0
for i in range(1,N + 1):
  n = N//i
  ans += sumOfNaturalNumber(n)*i
print(int(ans))
### BUGGY CODE ###

N, M = map(int, input().split())
A = [int(i) for i in input().split()]
B = [0] * M
C = [0] * M
Y = []
for i in range(M):
    B[i], C[i] = map(int, input().split())
    Y += [C[i]] * B[i]

A.extend(Y)
A.sort(reverse=True)
print(sum(A[:N]))

### FIXED CODE ###

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
CB = []
for i in range(M):
    B, C = list(map(int, input().split()))
    CB.append([C, B])
 
A.sort()
A.reverse()
CB.sort()
CB.reverse()
 
ans = 0
a_index = 0
cb_index = 0
f = 0
 
while True:
    if f == 1 or A[a_index] >= CB[cb_index][0]:
        ans += A[a_index]
        a_index += 1
        N -= 1
        if N == 0:
            break
    else:
        if N <= CB[cb_index][1]:
            ans += CB[cb_index][0] * N
            break
        else:
            ans += CB[cb_index][0] * CB[cb_index][1]
            N -= CB[cb_index][1]
            cb_index += 1
            if len(CB) == cb_index:
              f = 1
 
print(ans)
### BUGGY CODE ###

n,a,b,k=[int(i) for i in input().split()]
c=a+b
mod=998244353
ans=0

g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  #逆元テーブル
inverse = [0, 1]  #逆元テーブル計算用テーブル

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

#以下のcom関数を用いて組み合わせを計算
def com(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

#test=2*3*com(4, 2, mod) + com(4,3,mod)
#print(test)

for i in range(n+1):
    if (k-b*i)%a==0 and k-b*i>=0:
        n_a=(k-b*i)//a
        n_b=i
        
        n_c=min(n_a,n_b)
        n_a, n_b=n_a-min(n_a,n_b), n_b-min(n_a,n_b)

        while n_a + n_b + n_c <=n and n_c>=0 and n_b>=0 and n_a>=0:
            ans+=com(n, n_c, mod) * com(n-n_c, n_b, mod) * com(n-n_c-n_b, n_a, mod)
            n_c-=1
            n_b+=1
            n_a+=1

print(ans%mod)

### FIXED CODE ###

n,a,b,k=[int(i) for i in input().split()]
c=a+b
mod=998244353
ans=0

g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  #逆元テーブル
inverse = [0, 1]  #逆元テーブル計算用テーブル

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

#以下のcom関数を用いて組み合わせを計算
def com(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

for i in range(n+1):
    if (k-b*i)%a==0 and k-b*i>=0:
        n_a=(k-b*i)//a
        n_b=i
        if  max(n_a, n_b) <=n:
            ans+=com(n, n_a, mod) * com(n, n_b, mod)  %mod

print(ans%mod)
### BUGGY CODE ###

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

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

p = lcm_list(al)

ans = 0

for a in al:
    ans += p // a
    ans %= 10**9 + 7

print(ans)

### FIXED CODE ###

import fractions
n = int(input())
al = list(map(int,input().split()))
al = sorted(al)
p = al[0]
for i in range(1, n):
    p = p * al[i] // fractions.gcd(p, al[i])

ans = 0

for a in al:
    ans += p // a

print(ans % (10**9 + 7))
### BUGGY CODE ###

import numpy as np


N, W = map(int, input().split())
w_v = [[int(_) for _ in input().split()] for _ in range(N)]
dp = np.zeros([N, W+1], dtype=int)
dp[0][w_v[0][0]:] = w_v[0][1]

for i in range(1, N):
    for w in range(W+1):
        dp[i][w] = (dp[i-1][w] if w - w_v[i][0] < 0 else max(dp[i-1][w], dp[i-1][w - w_v[i][0]] + w_v[i][1]))

 
print(dp[N-1][W])

### FIXED CODE ###

import numpy as np


N, W = map(int, input().split())
w_v = [[int(_) for _ in input().split()] for _ in range(N)]
dp = np.zeros([N, W+1], dtype=int)
dp[0][w_v[0][0]:] = w_v[0][1]

for i in range(1, N):
    key = w_v[i][0]
    dp[i][:key] = dp[i-1][:key]
    dp[i][key:] = np.maximum(dp[i-1][key:], dp[i-1][:-key] + w_v[i][1])

print(dp[-1][-1])
### BUGGY CODE ###

from collections import deque
import math
import bisect

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

while M > 0:
    tmp = A.pop()
    tmp = tmp // 2
    index = bisect.bisect_right(A, tmp)
    A.insert(index, tmp)
    M -= 1
print(sum(A))


### FIXED CODE ###

import heapq
import sys

input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    A = list(map(lambda x: int(x) * (-1), input().split()))
    heapq.heapify(A)

    for _ in range(M):
        tmp = heapq.heappop(A)
        tmp *= -1
        tmp = tmp // 2
        heapq.heappush(A, tmp * (-1))
    print(sum(A) * (-1))


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

A,B,N = map(int,input().split())
S = 0
for i in range(N+1):
    S = max(S,(A*i)//B - A * (i//B))
print(S)


### FIXED CODE ###

A,B,N = map(int,input().split())
S = 0
n = N // B
r = N % B
if B > N:
    S = (A*N)//B
else:
    if  r == 0:
        S = (A*(N-1))//B - A * ((N-1)//B)
    elif r == B - 1:
        S = (A*N)//B - A * (N//B)
    else:
        S = (A*(n*B-1))//B - A * ((n*B-1)//B)

print(S)
### BUGGY CODE ###

n = int(input())

ans = 1
for i in range(2,n+1):
    ans *= i

print(ans % (10**9 + 7))

### FIXED CODE ###

n = int(input())

ans = 1
for i in range(1, n+1):
    ans *= i
    ans %= 10**9 + 7

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

from itertools import combinations
N,K=map(int,input().split())

xs = set()
ys = set()
inl = []

for i in range(N):
    x,y=map(int,input().split())
    inl.append((x,y))
    xs.add(x)
    ys.add(y)

xs = list(xs)
ys = list(ys)
xs.sort()
ys.sort()

res = 9223372036854775807
for xlow, xhi in combinations(xs,2):
    for ylow, yhi in combinations(ys,2):
        cnt = 0
        for x, y in inl:
            cnt += (x >= xlow and x <= xhi and y >= ylow and y <= yhi)
        if cnt == K:
            res = min(res,(xhi - xlow) * (yhi - ylow))
print(res)


### FIXED CODE ###

from itertools import combinations
N,K=map(int,input().split())

xs = set()
ys = set()
inl = []

for i in range(N):
    x,y=map(int,input().split())
    inl.append((x,y))
    xs.add(x)
    ys.add(y)

xs = list(xs)
ys = list(ys)
xs.sort()
ys.sort()

res = 9223372036854775807
for xlow, xhi in combinations(xs,2):
    for ylow, yhi in combinations(ys,2):
        cnt = 0
        for x, y in inl:
            cnt += (x >= xlow and x <= xhi and y >= ylow and y <= yhi)
        if cnt == K:
            res = min(res,(xhi - xlow) * (yhi - ylow))
print(res)
### BUGGY CODE ###

def main(): #グローバル名前空間で大きな処理を書かない
    n,k=map(int,input().split())
    H=["dammy"]+list(map(int,input().split()))
    dp=[0]*(n+1)
    for i in range(2,min(k+2,n+1)):
        dp[i]=min(dp[j]+abs(H[i]-H[j]) for j in range(1,i))
    for i in range(k+2,n+1):
        dp[i] = min(dp[i-j]+abs(H[i]-H[i-j]) for j in range(1,k+1)) #TLEになる.
    print(dp[n])
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    H = list(map(int, input().split()))
    dp = [0] * n
    for i, Hi in enumerate(H):
        if i == 0:
            continue
        s = max(0, i-k) # iがk以下かどうかで処理が変わる.
        dp[i] = min([dl + abs(hl - Hi) for dl, hl in zip(dp[s:i], H[s:i])])
    print(dp[-1])
main()
### BUGGY CODE ###

a,b = map(int,input().split())
c = a*b
d = 1
ans  = 0
while d%a != 0 or d%b != 0:
    for i in range(1,c+1):
        if b%c != 0:
            d = d+1
        
print(d)

### FIXED CODE ###

a,b = map(int,input().split())
#最大公約数
def gcd(a,b):#a<=b
    while a != 0:
        a,b = b%a,a
    return b
#最小公約数
def lcm(a,b):
    return a*b // gcd(a,b)
print(lcm(a,b))
### BUGGY CODE ###

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

today = 0

after = []
money = []

for i in range(n):
    a, b = map(int, input().split())
    after.append(a)
    money.append(b)

sum_money = 0
for day in range(m, -1, -1):
    # print('day',day)
    # print('after', after)
    maxi = [-1, 0]
    for i, x in enumerate(after):
        if x <= (m - day):
            if maxi[1] < money[i]:
                maxi = [i, money[i]]
    if maxi[0] == -1:
        continue
    # print('maxi', maxi)
    del after[maxi[0]]
    del money[maxi[0]]
    sum_money += maxi[1]

print(sum_money)


### FIXED CODE ###

import heapq

n, m = map(int, input().split())
jobs = dict()

for i in range(n):
    a, b = map(int, input().split())
    if not a in jobs.keys():
        jobs[a] = [-b]
    else:
        jobs[a].append(-b)
# print(jobs)
sum_money = 0
money_list = [0]
heapq.heapify(money_list)
for i in range(1, m+1):
    if i in jobs.keys():
        for money in jobs[i]:
            heapq.heappush(money_list, money)
    # print(money_list)
    max_money = -heapq.heappop(money_list)
    sum_money += max_money
    if max_money == 0:
        heapq.heappush(money_list, 0)
print(sum_money)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
n, q = map(int,input().split())
d = {}
for i in range(n-1):
    ai, bi = map(int,input().split())
    if ai-1 in d:
        d[ai-1] += [bi-1]
    else:
        d[ai-1] = [bi-1]
    if bi-1 in d:
        d[bi-1] += [ai-1]
    else:
        d[bi-1] = [ai-1]
#point
px = {}
for i in range(q):
    pi,xi = map(int,input().split())
    if pi- 1 in px:
        px[pi-1] += xi
    else:
        px[pi-1] = xi
sp = [0 for i in range(n)]

def f(v,vp,p):
    if v in px:
        su = p + px[v]
    else:
        su = p
    sp[v] = su
    if v in d:
        for di in d[v]:
            if not di == vp:
                f(di,v,su)
f(0,0,0)
for i in range(n):
    print(sp[i])

### FIXED CODE ###

from collections import deque
n, q = map(int,input().split())
d = [[] for i in range(n)]
for i in range(n-1):
    ai, bi = map(int,input().split())
    d[ai-1].append(bi-1)
    d[bi-1].append(ai-1)
#point
px = [0 for i in range(n)]
for i in range(q):
    pi,xi = map(int,input().split())
    px[pi-1] += xi
sp = [0 for i in range(n)]
s = deque()
s.append(0)
visited = [False for i in range(n)]
while len(s) > 0:
    x = s.popleft()
    visited[x] = True
    sp[x] += px[x]
    for xc in d[x]:
        if not visited[xc]:
            s.append(xc)
            sp[xc] += sp[x]
for i in range(n):
    print(sp[i])
### BUGGY CODE ###

from collections import deque

def bfs(count,adj):
    st = deque([(0,-1)])
    while st:
        n,par = st.popleft()
        val = count[n]   
        for node in adj[n]:
            if node == par:
                continue
            else:
                count[node] += val
                st.append([node,n])
    return count

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

for _ in range(N-1):
    a,b = map(int, input().split())
    A[a-1] += (b-1,)
    A[b-1] += (a-1,)

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

cnt = bfs(cnt,A)

print(*cnt)

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
        
N,Q = (int(i) for i in input().split())
A = [[] for _ in range(N)]

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

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

st = deque([(0,-1)])
while st:
    n,par = st.popleft()
    val = cnt[n]   
    for node in A[n]:
        if node == par:
            continue
        else:
            cnt[node] += val
            st.append([node,n])

print(*cnt)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Apr 29 14:42:43 2018

@author: maezawa
"""

def print_array(g):
    ans = str(g[0])
    if len(g) > 1:
        for i in range(1,len(g)):
            ans += ' '+str(g[i]) 
    print(ans)

name=[]
time=[]
current_time = 0

n, q = list(map(int, input().split()))
for i in range(n):
    s = input().split()
    name.append(s[0])
    time.append(int(s[1]))
# =============================================================================
# print(n,q)
# print(name)
# print(time)
# =============================================================================
finished = []
fin_time = []
i=0
remain = n
while True:
    if time[i] == 0:
        i += 1
        if i == n:
            i = 0
        continue
    if time[i] <= q:
        current_time += time[i]
        finished.append(name[i])
        fin_time.append(current_time)
        time[i] = 0
        remain -= 1
        if remain == 0:
            break
    else:
        time[i] -= q
        current_time += q
        i += 1
        if i == n:
            i = 0

for i in range(n):
    print("{} {}".format(finished[i], fin_time[i]))


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Apr 29 18:04:22 2018
ALDS1_3b_r リングバッファによる実装
@author: maezawa
"""

def fifo_enque(data):
    global tail
    global fifo
    fifo[tail] = data
    tail = (tail+1)%fifo_size
    
def fifo_deque():
    global head
    global fifo
    data = fifo[head]
    head = (head+1)%fifo_size
    return data

fifo_size = 100000
fifo = [0 for _ in range(fifo_size)]
head = 0
tail = 0

n, q = list(map(int, input().split()))
for i in range(n):
    s = input().split()
    data = [s[0], int(s[1])]
    fifo_enque(data)
    
current_time = 0
finished = []
fin_time = []

while True:
    data = fifo_deque()
    if data[1] > q:
        current_time += q
        data[1] -= q
        fifo_enque(data)
    else:
        current_time += data[1]
        finished.append(data[0])
        fin_time.append(current_time)
    if head == tail:
        break

for i in range(n):
    print("{} {}".format(finished[i], fin_time[i]))
### BUGGY CODE ###

N,M,Q=map(int,input().split())
lr=[]
for i in range(M):
  lr.append(list(map(int,input().split())))
pq=[]
for i in range(Q):
  pq.append(list(map(int,input().split())))
ans=[0]*Q
for i in range(Q):
  for j in range(M):
    if pq[i][0]<=lr[j][0] and lr[j][1]<=pq[i][1]:
      ans[i]+=1
for i in range(Q):
  print(ans[i])

### FIXED CODE ###

N,M,Q=map(int,input().split())
L,R=[],[]
for i in range(M):
  l,r=map(int,input().split())
  L.append(l)
  R.append(r)
Pl,Ql=[],[]
for i in range(Q):
  pq=list(map(int,input().split()))
  Pl.append(pq[0])
  Ql.append(pq[1])
c=[[0 for i in range(N+1)] for i in range(N+1)]
for i in range(M):
  c[L[i]][R[i]]+=1
for i in range(1,N+1):
  for j in range(1,N+1):
    c[i][j]+=c[i][j-1]
for i in range(1,N+1):
  for j in range(1,N+1):
    c[i][j]+=c[i-1][j]
for i in range(Q):
  ans=c[Ql[i]][Ql[i]]-c[Pl[i]-1][Ql[i]]-c[Ql[i]][Pl[i]-1]+c[Pl[i]-1][Pl[i]-1]
  print(ans)