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

import heapq
from collections import deque

n, m, full = map(int, input().split())
edges = [[]*n for _ in range(n)]

for i in range(m):
    a, b, c = map(int, input().split())
    edges[a-1].append([b-1, c])
    edges[b-1].append([a-1, c])


def dijkstra(num_of_node, edge, start, limit):
    distance = [float('INF')] * num_of_node
    reachable = []
    distance[start] = 0
    todo = []
    heapq.heapify(todo)
    heapq.heappush(todo, [0, start])

    while todo:
        d, node = heapq.heappop(todo)
        if d > limit:
            break
        reachable.append(node)
        for new_node, cost in edge[node]:
            if distance[new_node] > d + cost:
                distance[new_node] = d + cost
                heapq.heappush(todo, [d+cost, new_node])

            else:
                continue
    return reachable


L_edges = [[]*n for _ in range(n)]

for i in range(n):
    L_edges[i] = dijkstra(n, edges, i, full)

dist = [[float('INF')] * n for _ in range(n)]

for start in range(n):
    dist[start][start] = 0
    todo = deque([])
    todo.append([-1, start])

    while todo:
        d, node = todo.popleft()

        for new_node in L_edges[node]:
            if dist[start][new_node] > d + 1:
                dist[start][new_node] = d + 1
                todo.append([d+1, new_node])

            else:
                continue

Q = int(input())
for i in range(Q):
    s, t = map(int, input().split())
    ans = dist[s-1][t-1]
    if ans == float('INF'):
        ans = -1
    print(ans)


### FIXED CODE ###

from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse.csgraph import floyd_warshall

n, m, energy = map(int, input().split())
edges = [[float('INF')]*n for _ in range(n)]

for i in range(m):
    a, b, c = map(int, input().split())
    edges[a-1][b-1] = c
    edges[b-1][a-1] = c

G = csgraph_from_dense(edges, null_value=float('INF'))
dist = floyd_warshall(G)

L_edges = [[float('INF')]*n for _ in range(n)]
for i in range(n-1):
    for j in range(i, n):
        if dist[i][j] <= energy:
            L_edges[i][j] = 1
            L_edges[j][i] = 1

G = csgraph_from_dense(L_edges, null_value=float('INF'))
answers = floyd_warshall(G)

Q = int(input())
for i in range(Q):
    s, t = map(int, input().split())
    ans = answers[s-1][t-1] - 1
    if ans == float('INF'):
        ans = -1
    print(int(ans))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

input = sys.stdin.readline


def I():
    return int(input())


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


n = I()

ans = 0
for i in range(1, n):
    q, r = divmod(make_divisors(n - i), 2)
    ans += q * 2 + 1 * r

print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
import numpy as np
import numba

input = sys.stdin.readline


def I():
    return int(input())


# @njit((i8[:],), cache=True)
@numba.jit
def main(n):
    table = np.zeros(n, np.int64)

    for i in range(1, n):
        table[::i] += 1

    ans = 0
    for n in table[1:]:
        q, r = divmod(n, 2)
        ans += q * 2 + 1 * r

    return ans


N = I()

print(int(main(N)))
### BUGGY CODE ###

import math
n = int(input())

def num_divisors_trial_division(n):
    num = 0
    for i in range(1, int(math.sqrt(n) + 1e-9) + 1):
        if n % i == 0:
            num += 1
            if n != i ** 2:
                num += 1
    return num

ans = 0
for i in range(1, n):
    ans += num_divisors_trial_division(i)
    #print(i , ans)
print(ans)


### FIXED CODE ###


n = int(input())

# def num_divisors_trial_division(n):
#     num = 0
#     for i in range(1, int(n ** (1 / 2)) + 1):
#         if n % i == 0:
#             num += 1
#             if n != i ** 2:
#                 num += 1
#     return num
#
# ans = 0
# for j in range(1, n):
#     ans += num_divisors_trial_division(j)
#     #print(i , ans)
# print(ans)

ans = 0
for i in range(1, n):
    ans += (n - 1) // i
print(ans)
### BUGGY CODE ###

n, y = map(int, input().split())
max_x = y // 10000
max_y = y // 5000
max_z = y // 1000

for i in range(max_x + 1):
    for j in range(max_y + 1):
        remain = y - 10000 * i - 5000 * j
        if remain < 0:
            continue
        if remain // 1000 == n - (i + j):
            print(i, j, (n - i - j))
            exit()
print(-1, -1, -1)


### FIXED CODE ###

N, Y=list(map(int, input().split()))
ans=[-1, -1, -1]
flag=False
for x in range(N, -1, -1):
    for y in range(N-x, -1, -1):
        if 10000*x+5000*y+1000*(N-x-y)==Y:
            ans=[x,y,N-x-y]
            flag=True
            break
        if flag==True:
            break
    if flag==True:
        break
print(ans[0],ans[1],ans[2])
### BUGGY CODE ###

def main():
    A, B, C, D = map(int, input().split())
    num = 0
    for i in range(A, B+1):
        if i % C != 0 and i % D != 0:
            num +=1
    print(num)

if __name__  == '__main__':
    main()

### FIXED CODE ###

import fractions
def main():
    A, B, C, D = map(int, input().split())
    num = (B - A + 1)  - (get_num(B, C, D) - get_num(A-1, C, D))
    print(num)

def get_num(x, C, D):
    num_C = x // C
    num_D = x // D
    f = fractions.gcd(C, D)
    f2 = C*D//f
    num_CD = x // f2
    return num_C  + num_D - num_CD

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

def main():
    n = int(input())
    mod = 0
    pow10 = 1
    for i in range(20*n):
        mod = (mod+7*pow10) % n
        if mod == 0:
            print(i+1)
            return
        pow10 = pow10*10 % n
    print(-1)


main()


### FIXED CODE ###

def main():
    n = int(input())
    mod = 0
    pow10 = 1
    for i in range(20*n):
        mod = (mod+7*pow10) % n
        if mod == 0:
            print(i+1)
            return
        pow10 = pow10*10 % n
    print(-1)


main()
### BUGGY CODE ###

mod=10**9+7
n=int(input())
T=[int(i) for i in input().split()]
A=[int(i) for i in input().split()]
Tres=[0]*n
Ares=[0]*n
Tres[0]=(0,T[0])
Ares[n-1]=(0,A[n-1])
for i in range(1,n):
  if T[i]!=T[i-1]:
    Tres[i]=(0,T[i])
  else:
    Tres[i]=(1,T[i])
  if A[n-i-1]!=A[n-i]:
    Ares[n-i-1]=(0,A[n-i-1])
  else:
    Ares[n-i-1]=(1,A[n-i-1])
ans=1
for i in range(n):
  ta,tb=Tres[i]
  aa,ab=Ares[i]  
  if ta==aa==1:
    ans*=min(tb,ab)%mod
  elif ta==0 and aa==1 and tb>ab:
    ans=0
  elif ta==1 and aa==0 and tb<ab:
    ans=0
  elif ta==0 and aa==0 and tb!=ab:
    ans=0
print(ans%mod)

### FIXED CODE ###

mod=10**9+7
n=int(input())
T=[int(i) for i in input().split()]
A=[int(i) for i in input().split()]
Tres=[0]*n
Ares=[0]*n
Tres[0]=(0,T[0])
Ares[n-1]=(0,A[n-1])
for i in range(1,n):
  if T[i]>Tres[i-1][1]:
    Tres[i]=(0,T[i])
  else:
    Tres[i]=(1,T[i])
  if A[n-i-1]>Ares[n-i][1]:
    Ares[n-i-1]=(0,A[n-i-1])
  else:
    Ares[n-i-1]=(1,A[n-i-1])
if Tres[0]<=Ares[0]:
  ans=1
else:
  ans=0
for i in range(1,n):
  ta,tb=Tres[i]
  aa,ab=Ares[i]  
  if ta==aa==1:
    ans=ans*min(tb,ab)%mod
  elif ta==0 and aa==1 and tb>ab:
    ans=0
  elif ta==1 and aa==0 and tb<ab:
    ans=0
  elif ta==0 and aa==0 and tb!=ab:
    ans=0
print(ans%mod)
### BUGGY CODE ###

A,B,C,K = map(int,input().split())

t = 1
while t<=K:
    a = B+C
    b = A+C
    C = a+b-2*C
    A = a
    B = b
    t+=1

ans = A - B

if ans<=10^18:
    print(ans)
else:
    print('Unfair')

### FIXED CODE ###

A,B,C,K = map(int,input().split())

if K % 2 == 0:
    m = A-B
else:
    m = B-A

print(m)
### BUGGY CODE ###

N = int(input())
ans = 0

def c_i_j(n, i, j):
    counter = 0
    for num in range(1, n + 1):
        if int(str(num)[0]) == i and int(str(num)[-1]) == j:
            counter += 1
    return counter

for i in range(1, 10):
    for j in range(1, 10):
        ans += c_i_j(N, i, j) * c_i_j(N, j, i)

print(ans)


### FIXED CODE ###

N = int(input())
ans = 0

"""
def c_i_j(n, i, j):
    counter = 0
    for num in range(1, n + 1):
        if int(str(num)[0]) == i and int(str(num)[-1]) == j:
            counter += 1
    return counter

for i in range(1, 10):
    for j in range(1, 10):
        ans += c_i_j(N, i, j) * c_i_j(N, j, i)

print(ans)
"""
table = list([0] * 10 for i in range(10))

for i in range(1, N + 1):
    table[int(str(i)[0])][int(str(i)[-1])] += 1

for i in range(1, 10):
    for j in range(1, 10):
        ans += table[i][j] * table[j][i]

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

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

friend = [[] for _ in range(n)]
block = [[] for _ in range(n)]

for _ in range(m):
  a, b = map(int, input().split())
  friend[a-1].append(b-1)
  friend[b-1].append(a-1)
  
for _ in range(k):
  c, d = map(int, input().split())
  block[c-1].append(d-1)
  block[d-1].append(c-1)
  
groups = []
active = [True] * n
belong = [0] * n
g_index = 0
while any(active):
  idx = active.index(True)
  g = [idx]
  active[idx] = False
  belong[idx] = g_index
  stack = [idx]
  while stack:
    v = stack.pop()
    for i in friend[v]:
      if active[i]:
        stack.append(i)
        active[i] = False
        belong[i] = g_index
        g.append(i)
  groups.append(g)
  g_index += 1
  
for i in range(n):
  size = len(groups[belong[i]]) - 1 - len(friend[i])
  for j in block[i]:
    if j in groups[belong[i]]:
      size -= 1
  print(size, end=' ')

### FIXED CODE ###

class UnionFind:
  def __init__(self, n: int):
    self.parent = list(range(n))
    self.size = [1] * n
    self.rank = [1] * n
    
  def find(self, i: int) -> int:
    if self.parent[i] != i:
      self.parent[i] = self.find(self.parent[i])
    return self.parent[i]
  
  def unite(self, i: int, j: int):
    ri = self.find(i)
    rj = self.find(j)
    if ri != rj:
      if self.rank[ri] < self.rank[rj]:
        self.parent[ri] = rj
        self.size[rj] += self.size[ri]
      else:
        self.parent[rj] = ri
        self.size[ri] += self.size[rj]
        if self.rank[ri] == self.rank[rj]:
          self.rank[ri] += 1


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

n_friend = [1 for _ in range(n)]
block = [[] for _ in range(n)]
friendship = UnionFind(n)

for _ in range(m):
  a, b = map(int, input().split())
  n_friend[a-1] += 1
  n_friend[b-1] += 1
  friendship.unite(a-1, b-1)
  
for _ in range(k):
  c, d = map(int, input().split())
  block[c-1].append(d-1)
  block[d-1].append(c-1)
  
for i in range(n):
  r = friendship.find(i)
  cand = friendship.size[r] - n_friend[i]
  for j in block[i]:
    if r == friendship.find(j):
      cand -= 1
  print(cand, end=' ')
### BUGGY CODE ###

A,B,C,D = map(int, input().split())
ans=0
for x in range(A,B+1):
    if x%C!=0 and x%D!=0:
        ans+=1
print(ans)

### FIXED CODE ###


import fractions

A,B,C,D = map(int, input().split())
ans=B-A+1


E=D * C // fractions.gcd(C, D)

if A%C==0:
    nC_initial=A//C
else:
    nC_initial=A//C+1
    
if A%D==0:
    nD_initial=A//D
else:
    nD_initial=A//D+1

    
if A%E==0:
    nE_initial=A//E
else:
    nE_initial=A//E+1
    
nC_final=B//C
nD_final=B//D
nE_final=B//E
if nC_final<nC_initial:
    nC_final=nC_initial
if nD_final<nD_initial:
    nD_final=nD_initial
if nE_final<nE_initial:
    nE_final=nE_initial
nc=(nC_final-nC_initial+1)
nd=(nD_final-nD_initial+1)
ne=(nE_final-nE_initial+1)
if B<C:
    nc=0
    ne=0
if B<D:
    nd=0
    ne=0
if B<E:
    ne=0


#print(ans,nC_initial,nC_final,nD_initial,nD_final, nE_initial,nE_final)
#print(ans,nc,nd,ne)
print(ans-nc-nd+ne)
### BUGGY CODE ###

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

list_ = []
for i in range(N):
  if i != 0:
	  print(A.count(i))
print(0)

### FIXED CODE ###

import numpy as np

N = int(input())
A = list(map(int, input().split()))
ans = [0]*N

A.append(0)

for i in range(0, N-1):
  ans[A[i]] += 1
for i in range(1, N):
  print(ans[i])
print(0)
### BUGGY CODE ###

def nc2(n):
	if n<2:
		return 0
	else:
		return (n * (n-1))//2
n = int(input())
li = list(map(int, input().split()))
import collections as cl
d = cl.Counter(li)
# print(d)
for i in li:
	ans = 0
	for k,v in d.items():
		if k!=i:
			ans+=nc2(v)
		else:
			ans+=nc2(v-1)
	print(ans)

### FIXED CODE ###

def nc2(n):
	if n<2:
		return 0
	else:
		return (n * (n-1))//2
n = int(input())
li = list(map(int, input().split()))
s=0; 
d2={}
import collections as cl
d = cl.Counter(li)
for k, v in d.items():
	d2[k] = [nc2(v), nc2(v-1)]
	for v in d2[k]:
		s+=v
		break
# print(d2,s)
for i in li:
	print(s-(d2[i][0])+d2[i][1])
# print(d)
# for i in li:
# 	ans = 0
# 	for k,v in d.items():
# 		if k!=i:
# 			ans+=nc2(v)
# 		else:
# 			ans+=nc2(v-1)
# 	print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(s) for s in input().split()]

ans = 1
for a in A:
    ans *= a

if ans > 10**18:
    ans = -1

print(ans)

### FIXED CODE ###

N = int(input())
A = [int(s) for s in input().split()]

ans = 1
if 0 in A:
    ans = 0
else:
    for a in A:
        ans *= a

        if ans > 10 ** 18:
            ans = -1
            break

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

from collections import defaultdict
import math
def comb(n, r):
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

count = defaultdict(int)
for a in A:
    count[a] += 1

combi = defaultdict(int)
for a in count:
    combi[a] = comb(count[a],2)

for i in range(n):
    print(sum(list(combi.values())) - combi[A[i]] + comb(count[A[i]]-1, 2))

### FIXED CODE ###

from collections import defaultdict
import math
def comb(n, r):
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

count = defaultdict(int)
for a in A:
    count[a] += 1

combi = defaultdict(int)
for a in count:
    combi[a] = comb(count[a],2)

total = sum(list(combi.values()))
for i in range(n):
    print(total - (count[A[i]] - 1))
### BUGGY CODE ###

N = int(input())
List = list(input())
ListR = []
ListG = []
ListB = []

for i in range(N):
  if List[i]=="R":
    ListR.append(i)
  elif List[i]=="G":
    ListG.append(i)
  else:
    ListB.append(i)
    
ans = len(ListR)*len(ListG)*len(ListB)
for a in ListR:
  for i in range(1,max([a//2, 2000-a//2, min([a,4000-a])])):
    if a+i in ListG:
      if a+2*i in ListB:
        ans -=1
      if a-i in ListB:
        ans -=1
    if a-i in ListG:
      if a-2*i in ListB:
        ans -=1
      if a+i in ListB:
        ans -=1
    if a+2*i in ListG:
      if a+i in ListB:
        ans -=1
    if a-2*i in ListG:
      if a-i in ListB:
        ans -=1
print(ans)

### FIXED CODE ###

N = int(input())
List = list(input())
ans = (List.count("R"))*(List.count("G"))*(List.count("B"))

for i in range(1,2000):
  for j in range(N-i*2):
    if {List[j], List[j+i], List[j+2*i]} == {"R","G","B"}:
      ans -=1
print(ans)
### BUGGY CODE ###

N = int(input())
sum = 0
for i in range(N):
    sum += i
print(sum)

### FIXED CODE ###

#n = int(input())
#L = list(map(int, input().split()))
import math
import sys
import fractions
N = int(input())
print(N*(N-1)//2)
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))

for i in range(n):
    p[i] -= 1
def score(a, k):
    now = p[a]
    s = c[now]
    cnt = 1
    l = [s]
    while now != a and cnt < k:
        now = p[now]
        s += c[now]
        l.append(s)
        cnt += 1
    if cnt == k:
        return max(l)
    if 2 * cnt >= k:
        s = (k // cnt - 1) * s
        k %= cnt
        k += cnt
    else:
        k -= cnt
    cnt = 0
    while cnt < k:
        now = p[now]
        s += c[now]
        l.append(s)
        cnt += 1
    return max(l)
print(max(score(i, k) for i in range(n)))

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))

for i in range(n):
    p[i] -= 1
def score(a, k):
    now = p[a]
    s = c[now]
    cnt = 1
    l = [s]
    while now != a and cnt < k:
        now = p[now]
        s += c[now]
        l.append(s)
        cnt += 1
    if cnt == k:
        return max(l)
    l.append((k // cnt - 1) * s + max(l))
    s = (k // cnt) * s
    k %= cnt
    cnt=0
    while cnt < k:
        now = p[now]
        s += c[now]
        l.append(s)
        cnt += 1
    return max(l)
print(max(score(i, k) for i in range(n)))
### BUGGY CODE ###

#!/usr/bin/env python3
n = int(input())
h = list(map(int, input().split()))
ans = 0
for i in range(n):
    tmp = 0
    for j in range(i, n - 1):
        if h[j] < h[j + 1]:
            tmp = 0
        else:
            tmp += 1
        ans = max(ans, tmp)
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
n = int(input())
h = list(map(int, input().split()))
ans = 0
tmp = 0
for i in range(n - 1):
    if h[i] < h[i + 1]:
        tmp = 0
    else:
        tmp += 1
    ans = max(ans, tmp)
print(ans)
### BUGGY CODE ###

N = int(input())

S = [input() for _ in range(N)]
PS = ["".join([c + str(s.count(c)) for c in sorted(list(set(s)))]) for s in S]

t = 0
for ps in set(PS):
    n = PS.count(ps)
    t += n * (n - 1) // 2

print(t)

### FIXED CODE ###

N = int(input())

S = [input() for _ in range(N)]
PS = sorted(["".join([c + str(s.count(c)) for c in sorted(list(set(s)))]) for s in S])

t = 0
i = 0
while i < len(PS):
    j = i + 1
    while j < len(PS) and PS[j] == PS[i]:
        j += 1
    n = j - i

    t += n * (n - 1) // 2

    i = j

print(t)
### BUGGY CODE ###

n,k=map(int,input().split())
if n==1 and k==1:
    print(1)
    exit()
if k==1:
    print(0)
    exit()
g=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
mod=10**9+7
pk2=[0]*(k-1)
pk2[0]=1
for i in range(k-2):
    pk2[i+1]=pk2[i]*(k-2-i)%mod
def p(n,r):
    if n<r:
        return 0
    return pk2[r]
ans=k
q=[0]
v=[0]*n
v[0]=1
vc=1
while q and vc<n:
    s=q.pop(0)
    c=0
    if s==0:
        kai=k-1
    else:
        kai=k-2
    for es in g[s]:
        if v[es]==0:
            v[es]=1
            vc+=1
            c+=1
            q.append(es)
            ans*=kai
            ans%=mod
            kai-=1
print(ans%mod)


### FIXED CODE ###

from collections import deque
n,k=map(int,input().split())
if n==1 and k==1:
    print(1)
    exit()
if k==1:
    print(0)
    exit()
g=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
mod=10**9+7
ans=k
q=deque([0])
v=[0]*n
v[0]=1
vc=1
while q and vc<n:
    s=q.popleft()
    c=0
    if s==0:
        kai=k-1
    else:
        kai=k-2
    for es in g[s]:
        if v[es]==0:
            v[es]=1
            vc+=1
            c+=1
            q.append(es)
            ans*=kai
            ans%=mod
            kai-=1
print(ans%mod)
### BUGGY CODE ###

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

max1 = max(A)
A_ = A.copy()
A_.remove(max1)
max2 = max(A_)
ln = max1 + max2
ret = 0
for i in range(len(A)-1):
    for j in range(i+1, min(i + ln + 1, len(A) )):
        if A[j] + A[i] == j - i:
            ret += 1
print(ret)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
L1 = list()
D2 = dict()
ret = 0
for i in range(len(A)):
    num1 = i + 1 - A[i]
    num2 = i + 1 + A[i]
    L1.append(num1)
    if num2 not in D2:
        D2[num2] = 1
    else:
        D2[num2] += 1
ret = 0
retlist = dict()
for l in L1:
    if l in D2.keys():
        ret += D2[l]
print(ret)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	B_fix
# CreatedDate:  2020-03-07 22:34:34 +0900
# LastModified: 2020-03-07 22:46:29 +0900
#




def main():
    N,A,B=map(int,input().split())
    s=int(N/(A+B))
    tmp = s*(A+B)
    count=A*s
    for i in range(A):
        if(tmp==N):
            break
        tmp+=1
        count+=1
    print(count)




if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	B
# CreatedDate:  2020-08-30 14:36:32 +0900
# LastModified: 2020-08-30 14:45:15 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd


def main():
    n, a, b = map(int, input().split())
    tmp = n - n // (a+b) * (a+b)
    ans = n//(a+b) * a
    if tmp <= a:
        print(ans+tmp)
    else:
        print(ans+a)


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

#!/usr/bin/env python3
#n,p = map(int,input().split())
s = input()
p = 2019
n = len(s)
u_i = []
ans = 0
l = [0 for i in range(p)]
l[0] = 1
for i in range(n):
    l[int(s[i:])%p] += 1

for i in l:
    ans+= i*(i-1)//2
print(ans)


### FIXED CODE ###

p = 2019
s = input()
n = len(s)
l = [0 for i in range(p)]
l[0] = 1
ten = 1
cnt = 0
 
ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i+1
else:
    for i in range(n):
        cnt = (cnt + int(s[-i-1]) * ten) % p
        l[cnt] += 1
        ten = (ten * 10) % p
    for i in l:
        if i > 1:
            ans += i * (i - 1) // 2
print(ans)
### BUGGY CODE ###


def resolve():
    N, M, Q = map(int, input().split())
    cum_A = [[0]*(N+1) for _ in range(N+1)]
    for _ in range(M):
        l, r = map(int, input().split())
        for i in range(r, N+1):
            cum_A[l][i] += 1

    for _ in range(Q):
        ans = 0
        l, r = map(int, input().split())
        for i in range(l, r+1):
            ans += cum_A[i][r] - cum_A[i][l-1]
        print(ans)

if __name__ == "__main__":
    resolve()

### FIXED CODE ###


def resolve():
    N, M, Q = map(int, input().split())
    cum_A = [[0]*(N+1) for _ in range(N+1)]
    for _ in range(M):
        l, r = map(int, input().split())
        cum_A[l][r] += 1

    # 二次元累積和
    for i in range(1, N+1):
        for j in range(1, N+1):
            cum_A[i][j] += cum_A[i-1][j] + cum_A[i][j-1] - cum_A[i-1][j-1]

    for _ in range(Q):
        ans = 0
        l, r = map(int, input().split())
        ans = cum_A[r][r] - cum_A[r][l-1] - cum_A[l-1][r] + cum_A[l-1][l-1]

        print(ans)

if __name__ == "__main__":
    resolve()
### BUGGY CODE ###

N, Y = [int(k) for k in input().split(' ') if k]
Y //= 1000
x = Y // 10
Y -= x * 10
y = Y // 5
Y -= y * 5
z = Y
checked = []
def find(nx, ny, nz):
	if nx + ny + nz > N:
		return
	if (nx, ny, nz) in checked:
		return
	if nx + ny + nz == N:
		print(nx, ny, nz)
		exit()
	if nx > 0:
		find(nx - 1, ny + 2, nz)
	if ny > 0:
		find(nx, ny - 1, nz + 5)
	checked.append((nx, ny, nz))
find(x, y, z)
print(-1, -1, -1)

### FIXED CODE ###

N, Y = [int(k) for k in input().split(' ') if k]
Y //= 1000
x = Y // 10
Y -= x * 10
y = Y // 5
Y -= y * 5
z = Y
if N < x + y + z:
	print(-1, -1, -1)
	exit()
d = N - x - y - z
for dx in range(min(d, x) + 1):
	nx = x - dx
	ny = y + 2 * dx
	nd = N - nx - ny - z
	dy = min(nd // 4, ny)
	ny = ny - dy
	nz = z + dy * 5
	if nx + ny + nz == N:
		print(nx, ny, nz)
		exit()
print(-1, -1, -1)