AtCoder Beginner Contest 106 - AtCoder Express 2

In Takahashi Kingdom, there is a east-west railroad and N cities along it, numbered 1, 2, 3, ..., N from west to east.
A company called AtCoder Express possesses M trains, and the train i runs from City L_i to City R_i (it is possible that L_i = R_i).
Takahashi the king is interested in the following Q matters:
 - The number of the trains that runs strictly within the section from City p_i to City q_i, that is, the number of trains j such that p_i \leq L_j and R_j \leq q_i.
Although he is genius, this is too much data to process by himself. Find the answer for each of these Q queries to help him.

-----Constraints-----
 - N is an integer between 1 and 500 (inclusive).
 - M is an integer between 1 and 200 \ 000 (inclusive).
 - Q is an integer between 1 and 100 \ 000 (inclusive).
 - 1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)
 - 1 \leq p_i \leq q_i \leq N (1 \leq i \leq Q)

-----Input-----
Input is given from Standard Input in the following format:
N M Q
L_1 R_1
L_2 R_2
:
L_M R_M
p_1 q_1
p_2 q_2
:
p_Q q_Q

-----Output-----
Print Q lines. The i-th line should contain the number of the trains that runs strictly within the section from City p_i to City q_i.

-----Sample Input-----
2 3 1
1 1
1 2
2 2
1 2

-----Sample Output-----
3

As all the trains runs within the section from City 1 to City 2, the answer to the only query is 3.

Source: atcoder | Difficulty: MEDIUM_HARD


Solutions:
(n, m, q) = list(map(int, input().split()))
G = [[0] * (n + 1) for i in range(n + 1)]
for i in range(m):
	(l, r) = list(map(int, input().split()))
	G[l][r] += 1
S = [[0] * (n + 1) for i in range(n + 1)]
for i in range(1, n + 1):
	for j in range(1, n + 1):
		S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + G[i][j]
for i in range(q):
	(s, f) = list(map(int, input().split()))
	print(S[f][f] - S[s - 1][f] - S[f][s - 1] + S[s - 1][s - 1])


from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

def main():
	(N, M, Q) = list(map(int, input().split()))
	ans = [[0] * N for _ in range(N)]
	for i in range(M):
		(L, R) = [int(x) - 1 for x in input().split()]
		ans[L][R] += 1
	for i in range(N):
		if i != N - 1:
			for j in range(N):
				ans[N - 2 - i][j] += ans[N - 1 - i][j]
		for j in range(N - 1):
			ans[N - 1 - i][j + 1] += ans[N - 1 - i][j]
	for i in range(Q):
		(p, q) = list(map(int, input().split()))
		print(ans[p - 1][q - 1])

def __starting_point():
	main()
__starting_point()


import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60

def main():
	(N, M, Q) = map(int, readline().split())
	A = [[0] * N for _ in range(N)]
	for _ in range(M):
		(l, r) = map(int, readline().split())
		A[l - 1][r - 1] += 1
	B = [[0] * (N + 1) for _ in range(N + 1)]
	for i in range(N):
		for j in range(N):
			B[i + 1][j + 1] = B[i][j + 1] + B[i + 1][j] - B[i][j] + A[i][j]
	ans = [0] * Q
	for i in range(Q):
		(p, q) = map(int, readline().split())
		p -= 1
		q -= 1
		ans[i] = B[q + 1][q + 1] - B[q + 1][p] - B[p][q + 1] + B[p][p]
	print(*ans, sep='\n')
	return

def __starting_point():
	main()
__starting_point()


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


import numpy as np
(N, M, Q) = map(int, input().split())
table = [[0] * N for _ in range(N)]
for _ in range(M):
	(L, R) = map(lambda n: int(n) - 1, input().split())
	table[L][R] += 1
table = np.rot90(np.rot90(table, k=-1).cumsum(axis=0).cumsum(axis=1), k=1).tolist()
for _ in range(Q):
	(p, q) = map(lambda n: int(n) - 1, input().split())
	print(table[p][q])


(N, M, Q) = map(int, input().split())
mem = [[0 for _ in range(N)] for _ in range(N)]
for _ in range(M):
	(L, R) = map(int, input().split())
	mem[L - 1][R - 1] += 1
for L in range(N):
	for R in range(1, N):
		mem[L][R] += mem[L][R - 1]
for R in range(N):
	for L in range(1, N):
		mem[L][R] += mem[L - 1][R]
res = []
for _ in range(Q):
	(QL, QR) = map(int, input().split())
	if QL == 1:
		r = mem[QR - 1][QR - 1]
	else:
		r = mem[QR - 1][QR - 1] - mem[QL - 2][QR - 1]
	res.append(r)
for r in res:
	print(r)


import sys
input = lambda : sys.stdin.readline().rstrip()
(n, m, q) = map(int, input().split())
T = [[0] * (n + 2) for _ in range(n + 2)]
for _ in range(m):
	(l, r) = map(int, input().split())
	T[l][r] += 1
for i in range(1, n + 1)[::-1]:
	for j in range(1, n + 1):
		T[i][j + 1] += T[i][j]
for j in range(1, n + 1):
	for i in range(1, n + 1)[::-1]:
		T[i - 1][j] += T[i][j]
for _ in range(q):
	(p, q) = map(int, input().split())
	print(T[p][q])


(n, m, q) = map(int, input().split())
table = [[0] * (n + 1) for i in range(n + 1)]
for i in range(m):
	(a, s) = map(int, input().split())
	table[a][s] += 1
from itertools import accumulate
for (i, v) in enumerate(table):
	table[i] = list(accumulate(v))
for i in range(n):
	for j in range(n):
		table[j + 1][i + 1] += table[j][i + 1]
for i in range(q):
	(a, s) = map(int, input().split())
	a -= 1
	print(table[s][s] + table[a][a] - table[s][a] - table[a][s])


import sys
input = sys.stdin.readline
(N, M, Q) = map(int, input().split())
lst = [[0 for e in range(N + 1)] for f in range(N + 1)]
for i in range(M):
	(L, R) = map(int, input().split())
	for j in range(1, L + 1):
		lst[j][R] += 1
for j in range(N):
	for i in range(N + 1):
		lst[i][j + 1] += lst[i][j]
for i in range(Q):
	(p, q) = map(int, input().split())
	print(lst[p][q])


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


(n, m, q) = map(int, input().split())
M = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(m):
	(l, r) = map(int, input().split())
	M[r][l] += 1
D = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
	for j in range(1, n + 1):
		D[i][j] = M[i][j] + D[i][j - 1] + D[i - 1][j] - D[i - 1][j - 1]
for i in range(q):
	(p, q) = map(int, input().split())
	ans = D[q][q] - D[q][p - 1] - D[p - 1][p] + D[p - 1][p - 1]
	print(ans)


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


(N, M, Q) = map(int, input().split())
list = [[0 for i in range(N + 1)] for j in range(N + 1)]
for _ in range(M):
	(L, R) = map(int, input().split())
	list[L][R] += 1
for i in range(N):
	for j in range(N):
		list[i + 1][j + 1] += list[i + 1][j] + list[i][j + 1] - list[i][j]
for _ in range(Q):
	(p, q) = map(int, input().split())
	ans = list[q][q] - list[p - 1][q] - list[q][p - 1] + list[p - 1][p - 1]
	print(ans)


(n, m, q) = map(int, input().split())
mmap = [[0 for j in range(n + 1)] for i in range(n + 1)]
for i in range(m):
	(s, e) = map(int, input().split())
	mmap[s][e] += 1
for i in range(n + 1):
	for j in range(1, n + 1):
		mmap[i][j] = mmap[i][j] + mmap[i][j - 1]
for j in range(n + 1):
	for i in range(n - 1, 0, -1):
		mmap[i][j] = mmap[i][j] + mmap[i + 1][j]
for i in range(q):
	(s, e) = map(int, input().split())
	print(mmap[s][e])


(n, m, qu) = map(int, input().split())
ans = [[0] * (n + 1) for __ in range(n + 1)]
for _ in range(m):
	(l, r) = map(int, input().split())
	ans[l][r] += 1
for i in range(n + 1):
	for j in range(n):
		ans[i][j + 1] += ans[i][j]
for i in range(n):
	for j in range(n + 1):
		ans[i + 1][j] += ans[i][j]
for qq in range(qu):
	(p, q) = map(int, input().split())
	print(ans[q][q] - ans[p - 1][q] - ans[q][p - 1] + ans[p - 1][p - 1])


(N, M, Q) = map(int, input().split())
dp = [[0] * N for i in range(N)]
for i in range(M):
	(l, r) = map(int, input().split())
	dp[r - 1][l - 1] += 1
for i in range(N):
	for j in range(N - 1, 0, -1):
		dp[i][j - 1] += dp[i][j]
for j in range(N):
	for i in range(N - 1):
		dp[i + 1][j] += dp[i][j]
for i in range(Q):
	(p, q) = map(int, input().split())
	print(dp[q - 1][p - 1])


import sys
sys.setrecursionlimit(10 ** 8)

def ii():
	return int(sys.stdin.readline())

def mi():
	return map(int, sys.stdin.readline().split())

def li():
	return list(map(int, sys.stdin.readline().split()))

def li2(N):
	return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

def dp2(ini, i, j):
	return [[ini] * i for _ in range(j)]
from itertools import accumulate
(N, M, Q) = mi()
LR = li2(M)
dp = dp2(0, N, N)
for (l, r) in LR:
	dp[l - 1][r - 1] += 1
for i in range(N):
	dp[i] = list(accumulate(dp[i]))
for i in reversed(range(N - 1)):
	for j in range(N):
		dp[i][j] += dp[i + 1][j]
for _ in range(Q):
	(f, t) = mi()
	print(dp[f - 1][t - 1])


(n, m, q) = map(int, input().split())
d = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(m):
	(a, b) = map(int, input().split())
	d[a][b] += 1
for i in range(n + 1):
	for j in range(n):
		d[i][j + 1] += d[i][j]
for i in range(n):
	for j in range(n + 1):
		d[i + 1][j] += d[i][j]
for i in range(q):
	(a, b) = map(int, input().split())
	print(d[n][b] - d[a - 1][b])


(N, M, Q) = map(int, input().split())
S = [[0] * (N + 1) for _ in range(N + 1)]
for m in range(M):
	(L, R) = map(int, input().split())
	S[L][R] += 1
for l in range(1, N + 1):
	for r in range(1, N + 1):
		S[l][r] += S[l - 1][r] + S[l][r - 1] - S[l - 1][r - 1]
for i in range(Q):
	(p, q) = map(int, input().split())
	print(S[q][q] - S[p - 1][q] - S[q][p - 1] + S[p - 1][p - 1])


(N, M, Q) = map(int, input().split())
(L, R) = (0, 0)
X = [[0] * N for i in range(N)]
for i in range(M):
	(L, R) = map(int, input().split())
	X[L - 1][R - 1] += 1
Y = [[0] * (N + 1) for i in range(N + 1)]
for i in range(N):
	for j in range(N):
		Y[i + 1][j + 1] = X[i][j] + Y[i + 1][j] + Y[i][j + 1] - Y[i][j]
for i in range(Q):
	(L, R) = list(map(int, input().split()))
	print(Y[N][R] - Y[L - 1][R])


(n, m, q) = list(map(int, input().split()))
M = [list(map(int, input().split())) for i in range(m)]
Q = [list(map(int, input().split())) for i in range(q)]
LR = [[0] * (n + 1) for _ in range(n + 1)]
for m in M:
	LR[m[0] - 1][m[1]] += 1
for l in range(n, -1, -1):
	for r in range(0, n, 1):
		LR[l - 1][r + 1] = LR[l - 1][r + 1] + LR[l - 1][r] + LR[l][r + 1] - LR[l][r]
for q in Q:
	print(LR[q[0] - 1][q[1]])


import itertools
(n, m, q) = map(int, input().split())
lr = [[0 for i in range(n)] for j in range(n)]
for _ in range(m):
	(l, r) = map(int, input().split())
	lr[l - 1][r - 1] += 1
acc_lr = []
for l in lr:
	acc_lr.append([0] + list(itertools.accumulate(l)))
for _ in range(q):
	(l, r) = map(int, input().split())
	ans = 0
	for ls in acc_lr[l - 1:r]:
		ans += ls[r] - ls[l - 1]
	print(ans)


import sys
from itertools import accumulate, islice
(n, m, q) = map(int, input().split())
ipt = (map(int, line.split()) for line in sys.stdin.readlines())
rails = [[0] * n for _ in range(n)]
for (l, r) in islice(ipt, m):
	rails[l - 1][r - 1] += 1
rails = [list(accumulate(reversed(s))) for s in zip(*(accumulate(s) for s in rails))]
print('\n'.join((str(rails[q - 1][n - p]) for (p, q) in ipt)))


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


from numpy import *
(N, M, Q) = map(int, input().split())
G = zeros((N, N), int)
for m in range(M):
	(l, r) = map(int, input().split())
	G[N - l][r - 1] += 1
G = cumsum(cumsum(G, axis=0), axis=1)
for n in range(Q):
	(p, q) = map(int, input().split())
	print(G[N - p][q - 1])


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left, bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil, pi, factorial
from operator import itemgetter

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

def MI():
	return map(int, input().split())

def LI():
	return list(map(int, input().split()))

def LI2():
	return [int(input()) for i in range(n)]

def MXI():
	return [[LI()] for i in range(n)]

def SI():
	return input().rstrip()

def printns(x):
	print('\n'.join(x))

def printni(x):
	print('\n'.join(list(map(str, x))))
inf = 10 ** 17
mod = 10 ** 9 + 7
(n, m, que) = MI()
lis = [[0] * n for i in range(n)]
for i in range(m):
	(l, r) = MI()
	lis[l - 1][r - 1] += 1
for i in range(n):
	lis[i] = list(accumulate(lis[i]))
for i in range(n):
	for j in range(n - 1):
		lis[j + 1][i] += lis[j][i]
for i in range(que):
	(p, q) = MI()
	if p == 1:
		ans = lis[q - 1][q - 1]
	else:
		ans = lis[q - 1][q - 1] - lis[p - 2][q - 1]
	print(ans)


import numpy as np
(n, m, q) = [int(i) for i in input().split()]
trains = np.zeros([n + 1, n + 1], dtype=np.int32)
(l, r) = np.split(np.array([input().split() for _ in range(m)], dtype=np.int32), 2, 1)
(p, q) = np.split(np.array([input().split() for _ in range(q)], dtype=np.int32), 2, 1)
np.add.at(trains, (l, r), 1)
ans_arr = np.cumsum(np.cumsum(trains, axis=0), axis=1)
p -= 1
ans = ans_arr[q, q] - ans_arr[p, q] - ans_arr[q, p] + ans_arr[p, p]
print('\n'.join(ans.astype(str).flatten()))


import sys
sys.setrecursionlimit(10 ** 8)

def ii():
	return int(sys.stdin.readline())

def mi():
	return map(int, sys.stdin.readline().split())

def li():
	return list(map(int, sys.stdin.readline().split()))

def li2(N):
	return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

def dp2(ini, i, j):
	return [[ini] * i for _ in range(j)]
from itertools import accumulate

class BIT:

	def __init__(self, n):
		self.n = n
		self.data = [0] * (n + 1)
		self.el = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.data[i]
			i -= i & -i
		return s

	def add(self, i, x):
		self.el[i] += x
		while i <= self.n:
			self.data[i] += x
			i += i & -i

	def get(self, i, j=None):
		if j is None:
			return self.el[i]
		return self.sum(j) - self.sum(i)
(N, M, Q) = mi()
bit = BIT(N)
lrpq = dp2(0, 3, M + Q)
for i in range(M):
	(l, r) = mi()
	lrpq[i][1] = l - 1
	lrpq[i][2] = r - 1
for i in range(M, M + Q):
	(p, q) = mi()
	lrpq[i][0] = i
	lrpq[i][1] = p - 1
	lrpq[i][2] = q - 1
lrpq = sorted(lrpq, key=lambda x: (x[2], x[0]))
ans = [0] * Q
for i in range(M + Q):
	if lrpq[i][0] == 0:
		bit.add(lrpq[i][1] + 1, 1)
	else:
		bit.sum(lrpq[i][2])
		if lrpq[i][1] > 0:
			ans[lrpq[i][0] - M] = bit.sum(lrpq[i][2] + 1) - bit.sum(lrpq[i][1])
		else:
			ans[lrpq[i][0] - M] = bit.sum(lrpq[i][2] + 1)
for num in ans:
	print(num)


import sys
sin = sys.stdin.readlines()
(N, M, Q) = map(int, sin[0].split())
LR = [[0 for _ in range(N + 2 - i)] for i in range(N + 2)]
for line in sin[1:M + 1]:
	(L, R) = map(int, line.split())
	LR[L][R - L + 1] += 1
for i in range(2, N + 2):
	for j in range(1, N - i + 2):
		LR[j][i] += LR[j][i - 1] + LR[j + 1][i - 1] - LR[j + 1][i - 2]
for line in sin[M + 1:]:
	(p, q) = map(int, line.split())
	print(LR[p][q - p + 1])


(n, m, q) = map(int, input().split())
d = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for _ in range(m):
	(l, r) = map(int, input().split())
	d[l][r] += 1
for y in range(1, n + 1):
	for x in range(1, n + 1):
		d[y][x] += d[y][x - 1] + d[y - 1][x] - d[y - 1][x - 1]
for _ in range(q):
	(p, q) = map(int, input().split())
	print(d[q][q] - d[q][p - 1] - d[p - 1][q] + d[p - 1][p - 1])


(N, M, Q) = map(int, input().split())
L = [[0 for x in range(N + 1)] for x in range(N + 1)]
for i in range(M):
	(x, y) = map(int, input().split())
	L[x][y] += 1
for x in range(N + 1):
	for y in range(N):
		L[x][y + 1] += L[x][y]
for y in range(N + 1):
	for x in range(N):
		L[x + 1][y] += L[x][y]
for _ in range(Q):
	(x, y) = map(int, input().split())
	print(L[N][y] - L[x - 1][y])


import sys
input = sys.stdin.readline
from itertools import accumulate
(N, M, Q) = [int(x) for x in input().split()]
train = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
for i in range(M):
	(L, R) = [int(x) for x in input().split()]
	train[L][R] += 1
cum = [list(accumulate(train[i])) for i in range(N + 1)]
del train
cum = list(zip(*cum))
cum = [list(accumulate(cum[j])) for j in range(N + 1)]
for _ in range(Q):
	(p, q) = [int(x) for x in input().split()]
	print(cum[q][N] - cum[q][p - 1])


(N, M, Q) = map(int, input().split())
imos = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
	(l, r) = map(int, input().split())
	imos[l][r] += 1
for l in range(N - 1, -1, -1):
	for r in range(N + 1):
		imos[l][r] += imos[l + 1][r]
for r in range(1, N + 1):
	for l in range(N + 1):
		imos[l][r] += imos[l][r - 1]
for _ in range(Q):
	(p, q) = map(int, input().split())
	print(imos[p][q])


(N, M, Q) = map(int, input().split())
trains = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
	(L, R) = map(int, input().split())
	trains[L][R] += 1
for i in range(1, N + 1):
	for j in range(1, N + 1):
		trains[i][j] += trains[i - 1][j]
for i in range(1, N + 1):
	for j in range(1, N + 1):
		trains[i][j] += trains[i][j - 1]
ans = [0] * Q
for k in range(Q):
	(p, q) = map(int, input().split())
	ans[k] = trains[q][q] - trains[p - 1][q] - trains[q][p - 1] + trains[p - 1][p - 1]
for A in ans:
	print(A)


(N, M, Q) = map(int, input().split())
x = [[0] * N for i in range(N)]
for i in range(M):
	(L, R) = map(lambda x: int(x) - 1, input().split())
	x[L][R] += 1
cum = [[0] * (N + 1) for i in range(N + 1)]
for l in range(N):
	for r in range(N):
		cum[l][r + 1] = cum[l][r] + x[l][r]
for i in range(Q):
	(p, q) = map(lambda x: int(x) - 1, input().split())
	res = 0
	for l in range(p, q + 1):
		res += cum[l][q + 1] - cum[l][p]
	print(res)


import sys
sys.setrecursionlimit(10 ** 8)

def ii():
	return int(sys.stdin.readline())

def mi():
	return map(int, sys.stdin.readline().split())

def li():
	return list(map(int, sys.stdin.readline().split()))

def li2(N):
	return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

def dp2(ini, i, j):
	return [[ini] * i for _ in range(j)]
from itertools import accumulate

def segfunc(a, b):
	return a + b

def init(init_val):
	for i in range(n):
		seg[i + num - 1] = init_val[i]
	for i in range(num - 2, -1, -1):
		seg[i] = segfunc(seg[2 * i + 1], seg[2 * i + 2])

def update(k, x):
	k += num - 1
	seg[k] = x
	while k:
		k = (k - 1) // 2
		seg[k] = segfunc(seg[k * 2 + 1], seg[k * 2 + 2])

def query(p, q):
	if q <= p:
		return ide_ele
	p += num - 1
	q += num - 2
	res = ide_ele
	while q - p > 1:
		if p & 1 == 0:
			res = segfunc(res, seg[p])
		if q & 1 == 1:
			res = segfunc(res, seg[q])
			q -= 1
		p = p // 2
		q = (q - 1) // 2
	if p == q:
		res = segfunc(res, seg[p])
	else:
		res = segfunc(segfunc(res, seg[p]), seg[q])
	return res
(n, M, Q) = mi()
ide_ele = 0
num = 2 ** (n - 1).bit_length()
seg = [ide_ele] * 2 * num
L = [0] * n
init(L)
lrpq = dp2(0, 3, M + Q)
for i in range(M):
	(l, r) = mi()
	lrpq[i][1] = l - 1
	lrpq[i][2] = r - 1
for i in range(M, M + Q):
	(p, q) = mi()
	lrpq[i][0] = i
	lrpq[i][1] = p - 1
	lrpq[i][2] = q - 1
lrpq = sorted(lrpq, key=lambda x: (x[2], x[0]))
ans = [0] * Q
for i in range(M + Q):
	if lrpq[i][0] == 0:
		update(lrpq[i][1], seg[lrpq[i][1] + num - 1] + 1)
	else:
		ans[lrpq[i][0] - M] = query(lrpq[i][1], lrpq[i][2] + 1)
for num in ans:
	print(num)


import numpy as np
(N, M, Q, *LRpq) = list(map(int, open(0).read().split()))
(LR, pq) = (LRpq[:2 * M], LRpq[2 * M:])
del LRpq
acc = np.zeros((N + 1, N + 1), dtype=np.int64)
for (L, R) in zip(*[iter(LR)] * 2):
	acc[L][R] += 1
acc = np.cumsum(acc, axis=0)
acc = np.cumsum(acc, axis=1)
for (p, q) in zip(*[iter(pq)] * 2):
	print(acc[q][q] + acc[p - 1][p - 1] - acc[p - 1][q] - acc[q][p - 1])


(N, M, Q) = map(int, input().split())
LR = [[0 for _ in range(N + 2 - i)] for i in range(N + 2)]
for i in range(M):
	(L, R) = map(int, input().split())
	LR[L][R - L + 1] += 1
for i in range(2, N + 2):
	for j in range(1, N - i + 2):
		LR[j][i] += LR[j][i - 1] + LR[j + 1][i - 1] - LR[j + 1][i - 2]
A = []
for i in range(Q):
	(p, q) = map(int, input().split())
	A.append(LR[p][q - p + 1] - LR[q + 1][0])
print('\n'.join(map(str, A)))


(N, M, Q) = map(int, input().split())
LR = [list(map(int, input().split())) for i in range(M)]
pq = [list(map(int, input().split())) for i in range(Q)]
res = [[0] * N for i in range(N)]

def lsadd(L, R):
	L -= 1
	R -= 1
	for i in range(0, L + 1):
		res[i][R] += 1
for (l, r) in LR:
	lsadd(l, r)
for (p, q) in pq:
	print(sum(res[p - 1][:q]))


(n, m, q) = list(map(int, input().split()))
table = [[0] * n for i in range(n)]
for i in range(m):
	(l, r) = list(map(int, input().split()))
	l -= 1
	r -= 1
	table[r][l] += 1
for i in range(n):
	for j in range(1, n):
		table[i][j] = table[i][j] + table[i][j - 1]
for i in range(n):
	for j in range(1, n):
		table[j][i] = table[j][i] + table[j - 1][i]
for i in range(q):
	(l, r) = list(map(int, input().split()))
	l -= 1
	r -= 1
	if l != 0:
		ans = table[r][r] - table[r][l - 1]
	else:
		ans = table[r][r]
	print(ans)


def main():
	import numpy as np
	from sys import stdin
	input = stdin.readline
	(N, M, Q) = list(map(int, input().split()))
	cumsum = np.zeros((N + 1, N + 1), dtype=np.int64)
	for _ in range(M):
		(left, right) = list(map(int, input().split()))
		cumsum[left, right] += 1
	np.cumsum(cumsum, axis=0, out=cumsum)
	np.cumsum(cumsum, axis=1, out=cumsum)
	for _ in range(Q):
		(p, q) = list(map(int, input().split()))
		p -= 1
		print(cumsum[q, q] - cumsum[q, p] - cumsum[p, q] + cumsum[p, p])

def __starting_point():
	main()
__starting_point()


(N, M, Q) = map(int, input().split())
t = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
	(L, R) = map(int, input().split())
	t[L][R] += 1
for i in range(N + 1):
	for j in range(N):
		t[i][j + 1] += t[i][j]
result = []
for _ in range(Q):
	(p, q) = map(int, input().split())
	result.append(sum((t[i][q] - t[i][i - 1] for i in range(p, q + 1))))
print('\n'.join((str(v) for v in result)))


import sys
import numpy as np
(N, M, Q) = list(map(int, input().split(' ')))
dp = np.zeros(shape=(N + 1, N + 1), dtype=int)
for _ in range(M):
	(L, R) = list(map(int, input().split(' ')))
	dp[L][R] += 1
dp = dp.cumsum(axis=1).cumsum(axis=0)
queries = np.array(list(map(int, sys.stdin.read().split())))
left = queries[0::2] - 1
right = queries[1::2]
print('\n'.join((dp[right, right] + dp[left, left] - dp[left, right] - dp[right, left]).astype(str)))


(n, m, q) = map(int, input().split())
h = [[0] * n for _ in range(n)]
for i in range(m):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	h[n - 1 - l][r] += 1
ans = 0
for i in range(n):
	for j in range(n - 1):
		h[i][j + 1] += h[i][j]
for j in range(n):
	for i in range(n - 1):
		h[i + 1][j] += h[i][j]
for i in range(q):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	print(h[n - 1 - x][y])


(N, M, Q) = list(map(int, input().split()))
T = [tuple(map(int, input().split())) for i in range(M)]
queries = [tuple(map(int, input().split())) for i in range(Q)]
plot = [[0] * (N + 1) for i in range(N + 1)]
accum = [[0] * (N + 1) for i in range(N + 1)]
for (Li, Ri) in T:
	plot[Li][Ri] += 1
for i in range(1, N + 1):
	for j in range(1, N + 1):
		accum[i][j] = accum[i][j - 1] + accum[i - 1][j] - accum[i - 1][j - 1] + plot[i][j]
for (pi, qi) in queries:
	print(accum[qi][qi] - accum[pi - 1][qi])


(N, M, Q) = map(int, input().split())
dp = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
	(L, R) = map(int, input().split())
	dp[L][R] += 1
for i in range(N + 1):
	for j in range(N):
		dp[i][j + 1] += dp[i][j]
for j in range(N + 1):
	for i in range(N):
		dp[i + 1][j] += dp[i][j]
for k in range(Q):
	(p, q) = map(int, input().split())
	print(dp[q][q] - dp[p - 1][q])


(n, m, q) = map(int, input().split())
l = [[0 for i in range(n + 1)] for i in range(n + 1)]
for i in range(m):
	(a, b) = map(int, input().split())
	l[a][b] += 1
for i in range(1, n):
	for j in range(i + 1, n + 1):
		l[i][j] += l[i][j - 1]
for i in range(2, n + 1):
	for j in range(i, 0, -1):
		l[j - 1][i] += l[j][i]
for i in range(q):
	(a, b) = map(int, input().split())
	print(l[a][b])


(N, M, Q) = map(int, input().split())
A = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
	(L, R) = map(int, input().split())
	A[L][R] += 1
for i in range(1, N + 1):
	for j in range(1, N + 1):
		A[i][j] += A[i][j - 1]
for i in range(1, N + 1):
	for j in range(1, N + 1):
		A[i][j] += A[i - 1][j]
for i in range(Q):
	(L, R) = map(int, input().split())
	ans = A[R][R] - A[L - 1][R] - A[R][L - 1] + A[L - 1][L - 1]
	print(ans)


import sys
sys.setrecursionlimit(10 ** 8)

def Z():
	return int(input())

def ZZ():
	return [int(_) for _ in input().split()]

def main():
	(N, M, Q) = ZZ()
	lr = sorted([ZZ() for _ in range(M)])
	query = [ZZ() for _ in range(Q)]
	p = [[0] * (N + 1) for _ in range(N + 1)]
	for (l, r) in lr:
		p[l][r] += 1
	for i in range(1, N + 1)[::-1]:
		for j in range(1, N + 1):
			if j + 1 <= N:
				p[i][j + 1] += p[i][j]
			if 0 <= i - 1:
				p[i - 1][j] += p[i][j]
			if j + 1 <= N and 0 <= i - 1:
				p[i - 1][j + 1] -= p[i][j]
	for (a, b) in query:
		print(p[a][b])
	return

def __starting_point():
	main()
__starting_point()


(N, M, Q) = map(int, input().split())
line = [tuple(map(int, input().split())) for i in range(M)]
query = [tuple(map(int, input().split())) for i in range(Q)]
dp = [[0 for i in range(N + 1)] for i in range(N + 1)]
for l in line:
	dp[l[0]][l[1]] += 1
for i in range(N):
	for j in range(N):
		dp[i + 1][j + 1] += dp[i + 1][j]
for i in range(N):
	for j in range(N):
		dp[i + 1][j + 1] += dp[i][j + 1]
for (p, q) in query:
	print(dp[q][q] - dp[q][p - 1] - dp[p - 1][q] + dp[p - 1][p - 1])


(n, m, q) = map(int, input().split())
d = [[0] * (n + 1) for _ in range(n + 1)]
for mm in range(m):
	(l, r) = map(int, input().split())
	d[l][r] += 1
for i in range(n):
	for j in range(n + 1):
		d[i + 1][j] += d[i][j]
for j in range(n + 1):
	for i in range(n):
		d[j][i + 1] += d[j][i]
for qq in range(q):
	(x, y) = map(int, input().split())
	print(d[y][y] - d[y][x - 1] - d[x - 1][y] + d[x - 1][x - 1])


def main():
	import numpy as np
	from sys import stdin
	input = stdin.readline
	(N, M, Q) = list(map(int, input().split()))
	cumsum = np.zeros((N + 1, N + 1), dtype=np.int64)
	(L, R) = np.array([input().split() for _ in range(M)], dtype=np.int64).T
	np.add.at(cumsum, (L, R), 1)
	np.cumsum(cumsum, axis=0, out=cumsum)
	np.cumsum(cumsum, axis=1, out=cumsum)
	for _ in range(Q):
		(p, q) = list(map(int, input().split()))
		p -= 1
		print(cumsum[q, q] - cumsum[q, p] - cumsum[p, q] + cumsum[p, p])

def __starting_point():
	main()
__starting_point()


(n, m, q) = list(map(int, input().split()))
tmp = [[0] * 510 for _ in range(510)]
for _ in range(m):
	(l, r) = list(map(int, input().split()))
	tmp[l][r] += 1
for i in range(1, 501):
	for j in range(1, 501):
		tmp[i][j] += tmp[i - 1][j]
		tmp[i][j] += tmp[i][j - 1]
		tmp[i][j] -= tmp[i - 1][j - 1]
for _ in range(q):
	ans = 0
	(ll, rr) = list(map(int, input().split()))
	print(tmp[rr][rr] - tmp[rr][ll - 1] - tmp[ll - 1][rr] + tmp[ll - 1][ll - 1])


(n, m, Q) = map(int, input().split())
lr = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for _ in range(m):
	(l, r) = map(int, input().split())
	lr[l][r] += 1
rui = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
	for j in range(1, n + 1):
		rui[i][j] = lr[i][j] + rui[i - 1][j] + rui[i][j - 1] - rui[i - 1][j - 1]
for _ in range(Q):
	(p, q) = map(int, input().split())
	p -= 1
	ans = rui[q][q] - rui[p][q] - rui[q][p] + rui[p][p]
	print(ans)


(N, M, Q) = map(int, input().split())
p = [[0] * 510 for i in range(510)]
for i in range(M):
	(l, r) = map(int, input().split())
	p[l][r] += 1
for i in range(1, N + 1):
	for j in range(1, N + 1):
		p[i][j] += p[i][j - 1]
for i in range(1, N + 1):
	for j in range(1, N + 1):
		p[i][j] += p[i - 1][j]
for i in range(Q):
	(l, r) = map(int, input().split())
	ans = p[r][r] + p[l - 1][l - 1] - p[r][l - 1] - p[l - 1][r]
	print(ans)


import numpy as np
(N, M, Q) = map(int, input().split())
grid = np.zeros((N + 1, N + 1), dtype=np.int64)
query = []
for _ in range(M):
	(L, R) = map(int, input().split())
	grid[L, R] += 1
cum_grid = grid.cumsum(axis=0).cumsum(axis=1)
ans_list = []
for _ in range(Q):
	(p, q) = map(int, input().split())
	ans = cum_grid[q, q] - cum_grid[p - 1, q] - cum_grid[q, p - 1] + cum_grid[p - 1, p - 1]
	ans_list.append(ans)
for ans in ans_list:
	print(ans)


(n, m, q) = map(int, input().split())
import numpy as np
dim2 = np.zeros((n + 1, n + 1), dtype='int8')
for _ in range(m):
	(l, r) = map(int, input().split())
	dim2[l][r] += 1
dim2 = np.cumsum(dim2, axis=0)
dim2 = np.cumsum(dim2, axis=1)
for _ in range(q):
	(p, q) = map(int, input().split())
	ans = dim2[q][q] - dim2[q][p - 1] - dim2[p - 1][q] + dim2[p - 1][p - 1]
	print(ans)


from sys import stdin
import numpy as np
(N, M, Q) = [int(x) for x in stdin.readline().rstrip().split()]
cumsum_2d = np.zeros([N + 1, N + 1])
for i in range(M):
	(L, R) = [int(x) for x in stdin.readline().rstrip().split()]
	cumsum_2d[L, R] += 1
np.cumsum(cumsum_2d, axis=0, out=cumsum_2d)
np.cumsum(cumsum_2d, axis=1, out=cumsum_2d)
for i in range(Q):
	(p, q) = [int(x) for x in stdin.readline().rstrip().split()]
	ans = cumsum_2d[q, q] - cumsum_2d[q, p - 1] - cumsum_2d[p - 1, q] + cumsum_2d[p - 1, p - 1]
	print(int(ans))


(n, m, q) = map(int, input().split())
G = [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
	(l, r) = map(int, input().split())
	G[l][r] += 1
for i in range(1, n + 1):
	for j in range(1, n + 1):
		G[i][j] += G[i - 1][j] + G[i][j - 1] - G[i - 1][j - 1]
p = [list(map(int, input().split())) for _ in range(q)]
for u in p:
	(s, t) = (u[0] - 1, u[1])
	print(G[s][s] + G[t][t] - (G[s][t] + G[t][s]))


import bisect
(N, M, Q) = map(int, input().split())
LR = [[0] * (N + 1) for _ in range(N)]
for i in range(M):
	(l, r) = map(int, input().split())
	LR[l - 1][r] += 1
for i in range(N):
	for j in range(1, N + 1):
		LR[i][j] += LR[i][j - 1]
for _ in range(Q):
	ans = 0
	(p, q) = map(int, input().split())
	for i in range(p - 1, q):
		ans += LR[i][q] - LR[i][p - 1]
	print(ans)


I = lambda : list(map(int, input().split()))
(n, m, q) = I()
k = n + 2
l = [0] * k ** 2
for _ in range(m):
	(s, g) = I()
	l[s * k + g] += 1
for i in range(1, n + 1):
	for j in range(1, n + 1):
		l[i * k + j] += l[i * k + j - 1]
for i in range(1, n + 1):
	for j in range(1, n + 1):
		l[i * k + j] += l[~-i * k + j]
for _ in range(q):
	(s, g) = I()
	print(l[g * k + g] - l[~-s * k + g] - l[g * k + s - 1] + l[~-s * k + s - 1])


import sys
readline = sys.stdin.readline
(N, M, Q) = list(map(int, readline().split()))
train = [[0] * (N + 1) for i in range(N + 1)]
for i in range(M):
	(L, R) = list(map(int, readline().split()))
	train[L][R] += 1
for i in range(N + 1):
	for j in range(1, N + 1):
		train[i][j] += train[i][j - 1]
for j in range(N + 1):
	for i in range(1, N + 1):
		train[i][j] += train[i - 1][j]
for i in range(Q):
	(p, q) = list(map(int, readline().split()))
	print(train[q][q] - train[p - 1][q] - train[q][p - 1] + train[p - 1][p - 1])


(n, m, q) = map(int, input().split())
image = [[0] * n for _ in range(n)]
for _ in range(m):
	(l, r) = map(int, input().split())
	image[l - 1][r - 1] += 1
for l in range(n - 1, -1, -1):
	for r in range(l + 1, n):
		image[l][r] += image[l + 1][r] + image[l][r - 1] - image[l + 1][r - 1]
for _ in range(q):
	(a, b) = map(int, input().split())
	c = image[a - 1][b - 1]
	print(c)


import numpy as np
(N, M, Q) = map(int, input().split())
a = np.array([[0] * (N + 1) for i in range(N + 1)])
for i in range(M):
	(l, r) = map(int, input().split())
	a[l][r] += 1
a = a.cumsum(axis=0).cumsum(axis=1)
for i in range(Q):
	(p, q) = map(int, input().split())
	print(a[q][q] - a[p - 1][q] - a[q][p - 1] + a[p - 1][p - 1])


(n, m, q) = map(int, input().split())
dia = [[0] * (n + 1) for i in range(n + 1)]
for i in range(m):
	(l, r) = map(int, input().split())
	dia[l][r] += 1
lst = [[0] * (n + 1) for i in range(n + 1)]
for i in range(1, n + 1):
	for j in range(i, n + 1):
		lst[i][j] = lst[i][j - 1] + dia[i][j]
for i in range(q):
	(l, r) = map(int, input().split())
	count = 0
	for j in range(l, r + 1):
		count += lst[j][r]
	print(count)


import sys
input = sys.stdin.readline
(n, m, q) = map(int, input().split())
num = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(m):
	(l, r) = map(int, input().split())
	num[l][r] += 1
for i in range(n):
	for j in range(n):
		num[i + 1][j + 1] += num[i + 1][j]
for i in range(q):
	(p, q) = map(int, input().split())
	ans = 0
	for i in range(p, q + 1):
		ans += num[i][q] - num[i][p - 1]
	print(ans)


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


(N, M, Q) = [int(x) for x in input().split()]
ll = [[0] * (N + 1) for i in range(N + 1)]
for i in range(M):
	(l, r) = [int(x) for x in input().split()]
	ll[l][r] += 1
for i in range(1, N + 1):
	for j in range(1, N + 1):
		ll[i][j] += ll[i - 1][j]
for i in range(Q):
	ans = 0
	(p, q) = [int(x) for x in input().split()]
	for i in range(p, q + 1):
		ans += ll[q][i] - ll[p - 1][i]
	print(ans)


(N, M, Q) = map(int, input().split())
S = [[0] * (N + 1) for _ in range(N + 1)]
ans = [0] * Q
for i in range(M):
	(l, r) = map(int, input().split())
	S[l][r] += 1
for i in range(1, N + 1):
	for j in range(1, N + 1):
		S[i][j] += S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1]
for i in range(Q):
	(p, q) = map(int, input().split())
	ans[i] = S[q][q] - S[p - 1][q] - S[q][p - 1] + S[p - 1][p - 1]
print('\n'.join(map(str, ans)))


(N, M, Q) = map(int, input().split())
table = [[0] * N for _ in range(N)]
for i in range(M):
	(l, r) = map(int, input().split())
	table[l - 1][r - 1] += 1
dp = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(N):
	for j in range(N):
		dp[i + 1][j + 1] = dp[i + 1][j] + table[i][j]
for i in range(Q):
	(p, q) = map(int, input().split())
	sum = 0
	for k in range(p, q + 1):
		sum += dp[k][q] - dp[k][p - 1]
	print(sum)


(n, m, Q) = [int(i) for i in input().split()]
grid = [[0] * n for i in range(n)]
grid_acc = [[0] * n for i in range(n)]
for i in range(m):
	(l, r) = [int(i) for i in input().split()]
	grid[l - 1][r - 1] += 1
grid_acc[0][0] = grid[0][0]
for i in range(1, n):
	grid_acc[i][0] = grid_acc[i - 1][0] + grid[i][0]
	grid_acc[0][i] = grid_acc[0][i - 1] + grid[0][i]
for i in range(1, n):
	for j in range(1, n):
		grid_acc[i][j] = grid_acc[i - 1][j] + grid_acc[i][j - 1] - grid_acc[i - 1][j - 1] + grid[i][j]
for i in range(Q):
	(p, q) = [int(i) for i in input().split()]
	if p == 1:
		print(grid_acc[q - 1][q - 1])
	else:
		print(grid_acc[q - 1][q - 1] - grid_acc[p - 2][q - 1] - grid_acc[q - 1][p - 2] + grid_acc[p - 2][p - 2])


a = list(map(int, input().split()))
p = [list(map(int, input().split())) for i in range(a[1])]
q = [list(map(int, input().split())) for i in range(a[2])]
res = [[0] * a[0] for i in range(a[0])]

def lsadd(L, R):
	L -= 1
	R -= 1
	for i in range(0, L + 1):
		res[i][R] += 1
for (l, r) in p:
	lsadd(l, r)
for (l, r) in q:
	print(sum(res[l - 1][:r]))


(N, M, Q) = map(int, input().split())
T = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
for i in range(M):
	(L, R) = map(int, input().split())
	T[L][R] += 1
for l in range(1, N + 1):
	for r in range(1, N + 1):
		T[l][r] += T[l - 1][r] + T[l][r - 1] - T[l - 1][r - 1]
ans = []
for i in range(Q):
	(p, q) = map(int, input().split())
	ans.append(T[p - 1][p - 1] + T[q][q] - T[p - 1][q] - T[q][p - 1])
print('\n'.join(map(str, ans)))


from itertools import accumulate
import numpy as np
(n, m, q) = list(map(int, input().split()))
lr = [list(map(int, input().split())) for _ in range(m)]
pq = [list(map(int, input().split())) for _ in range(q)]
data = [[0] * 500 for i in range(500)]
for (l, r) in lr:
	data[l - 1][r - 1] += 1
data = np.array(data)
data = np.cumsum(data, axis=1)
data = np.cumsum(data, axis=0)
for (p, q) in pq:
	ans = 0
	if p == 1:
		ans = data[q - 1][q - 1]
	else:
		ans = data[q - 1][q - 1] - data[p - 1 - 1][q - 1]
	print(ans)


(N, M, Q) = map(int, input().split())
l = [[0 for i in range(N)] for j in range(N)]
for _ in range(M):
	(L, R) = map(int, input().split())
	l[L - 1][R - 1] += 1
csum = [[0 for i in range(N + 1)] for j in range(N + 1)]
for i in range(1, N + 1):
	for j in range(1, N + 1):
		csum[i][j] = csum[i][j - 1] + csum[i - 1][j] - csum[i - 1][j - 1] + l[i - 1][j - 1]
for _ in range(Q):
	(p, q) = map(int, input().split())
	print(csum[q][q] - csum[q][p - 1] - csum[p - 1][q] + csum[p - 1][p - 1])


(N, M, Q) = map(int, input().split())
C = [[0 for _ in range(N + 1)] for __ in range(N + 1)]
for _ in range(M):
	(l, r) = map(int, input().split())
	C[l][r] += 1
for i in range(N + 1):
	for j in range(1, N + 1):
		C[i][j] += C[i][j - 1]
for _ in range(Q):
	(p, q) = map(int, input().split())
	ans = 0
	for i in range(p, q + 1):
		ans += C[i][q] - C[i][i - 1]
	print(ans)


(N, M, Q) = map(int, input().split())
LR = [[0] * (N + 2 - i) for i in range(N + 2)]
for i in range(M):
	(L, R) = map(int, input().split())
	LR[L][R - L + 1] += 1
for i in range(2, N + 2):
	for j in range(1, N - i + 2):
		LR[j][i] += LR[j][i - 1] + LR[j + 1][i - 1] - LR[j + 1][i - 2]
for i in range(Q):
	(p, q) = map(int, input().split())
	print(LR[p][q - p + 1] - LR[q + 1][0])


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


(n, m, q) = map(int, input().split())
a = [[0 for i in range(n)] for j in range(n)]
for i in range(m):
	(l, r) = map(int, input().split())
	a[l - 1][r - 1] += 1
for i in range(n):
	for j in range(1, n):
		a[i][j] += a[i][j - 1]
for j in range(n):
	for i in range(1, n):
		a[i][j] += a[i - 1][j]
for i in range(q):
	(l, r) = map(int, input().split())
	ans = a[r - 1][r - 1]
	if l > 1:
		ans += a[l - 2][l - 2] - a[r - 1][l - 2] - a[l - 2][r - 1]
	print(ans)


from itertools import accumulate
(N, M, Q, *I) = map(int, open(0).read().split())
(LR, PQ) = (I[:2 * M], I[2 * M:])
M = [[0] * (N + 1) for _ in range(N + 1)]
for (l, r) in zip(*[iter(LR)] * 2):
	M[l][r] += 1
A = [list(accumulate(reversed(a)))[::-1] for a in zip(*[accumulate(m) for m in M])]
for (p, q) in zip(*[iter(PQ)] * 2):
	print(A[q][p])


from collections import defaultdict
(N, M, Q) = list(map(int, input().split()))
l2r = defaultdict(int)
l2acc = [[0] * (N + 1) for _ in range(N)]
r2acc = [[0] * (N + 1) for _ in range(N)]
for _ in range(M):
	(l, r) = list(map(int, input().split()))
	(l, r) = (l - 1, r - 1)
	l2r[l, r] += 1
queries = []
for _ in range(Q):
	(l, r) = list(map(int, input().split()))
	(l, r) = (l - 1, r - 1)
	queries.append((l, r))
for l in range(N):
	acc = 0
	for r in range(l, N):
		acc += l2r[l, r]
		l2acc[l][r] = acc
for r in range(N):
	acc = 0
	for l in range(r, -1, -1):
		acc += l2acc[l][r]
		r2acc[l][r] = acc
for (l, r) in queries:
	print(r2acc[l][r])


def cum2D(a, H, W):
	cum = [[0] * (W + 1) for _ in range(H + 1)]
	for i in range(H):
		for j in range(W):
			cum[i + 1][j + 1] = cum[i][j + 1] + cum[i + 1][j] - cum[i][j] + a[i + 1][j + 1]
	return cum
(n, m, q) = list(map(int, input().split()))
trains = [tuple(map(int, input().split())) for _ in range(m)]
a = [[0] * (n + 1) for j in range(n + 1)]
for k in range(m):
	(start, stop) = trains[k]
	a[start][stop] += 1
cum = cum2D(a, n, n)
for _ in range(q):
	(p, q) = list(map(int, input().split()))
	print(cum[n][q] - cum[p - 1][q])


(n, m, q) = map(int, input().split())
x = [[0 for i in range(n)] for j in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	x[a - 1][b - 1] += 1
for j in range(1, n):
	for k in range(n - j):
		x[k][j + k] += x[k][j + k - 1] + x[k + 1][j + k] - x[k + 1][j + k - 1]
for i in range(q):
	(a, b) = map(int, input().split())
	print(x[a - 1][b - 1])


(N, M, Q) = map(int, input().split())
c = [[0 for i in range(N + 1)] for j in range(N + 1)]
for i in range(M):
	(a, b) = map(int, input().split())
	c[a][b] += 1
for i in range(1, N):
	for j in range(1, N + 1 - i):
		c[j][i + j] += c[j + 1][i + j] + c[j][i + j - 1] - c[j + 1][i + j - 1]
for i in range(Q):
	(a, b) = map(int, input().split())
	print(c[a][b])


def resolve():
	(n, m, q) = map(int, input().split())
	rosen = [[0] * n for _ in range(n)]
	for i in range(m):
		(l, r) = map(int, input().split())
		l -= 1
		r -= 1
		rosen[l][r] += 1
	cum = [[0] * (n + 1) for _ in range(n + 1)]
	for i in range(n):
		if i == 0:
			cum[0][0] = rosen[0][0]
			for j in range(1, n):
				cum[0][j] = cum[0][j - 1] + rosen[0][j]
		else:
			cum[i][0] = cum[i - 1][0] + rosen[i][0]
			for j in range(1, n):
				cum[i][j] = cum[i - 1][j] + cum[i][j - 1] - cum[i - 1][j - 1] + rosen[i][j]
	for i in range(q):
		(p, q) = map(int, input().split())
		p -= 1
		q -= 1
		if p == 0:
			print(cum[q][q])
		else:
			print(cum[q][q] - cum[p - 1][q] - cum[q][p - 1] + cum[p - 1][p - 1])
resolve()


(N, M, Q) = map(int, input().split())
A = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
for _ in range(M):
	(L, R) = map(int, input().split())
	A[L][R] += 1
B = [[0 for _ in range(N + 2)] for _ in range(N + 2)]
for i in range(N, 0, -1):
	for j in range(1, N + 1):
		B[i][j] = A[i][j] + B[i + 1][j] + B[i][j - 1] - B[i + 1][j - 1]
for _ in range(Q):
	(p, q) = map(int, input().split())
	print(B[p][q])


import sys
(N, M, Q) = list(map(int, sys.stdin.readline().strip().split()))
cusum = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
	(L, R) = list(map(int, sys.stdin.readline().strip().split()))
	cusum[L][R] += 1
for i in range(N):
	for j in range(N):
		cusum[i + 1][j + 1] += cusum[i + 1][j] + cusum[i][j + 1] - cusum[i][j]
for _ in range(Q):
	(p, q) = list(map(int, sys.stdin.readline().strip().split()))
	ans = cusum[q][q] - cusum[q][p - 1] - cusum[p - 1][q] + cusum[p - 1][p - 1]
	print(ans)


from itertools import accumulate
(N, M, Q) = map(int, input().split())
a = [[0] * N for i in range(N)]
for i in range(M):
	(l, r) = map(int, input().split())
	a[l - 1][r - 1] += 1
for i in range(N):
	a[i] = list(accumulate(a[i]))
for i in range(N):
	for j in range(N - 1):
		a[j + 1][i] += a[j][i]
for i in range(Q):
	(p, q) = map(int, input().split())
	if p == 1:
		ans = a[q - 1][q - 1]
	else:
		ans = a[q - 1][q - 1] - a[p - 2][q - 1]
	print(ans)


(n, m, q) = map(int, input().split())
a = [[0 for _ in range(n)] for _ in range(n)]
for i in range(m):
	(x, y) = map(int, input().split())
	a[x - 1][y - 1] += 1
for j in range(n):
	for k in range(1, n):
		a[j][k] = a[j][k] + a[j][k - 1]
for l in range(q):
	ans = 0
	(L, R) = map(int, input().split())
	for g in range(L - 1, R):
		ans += a[g][R - 1]
	print(ans)


(N, M, Q) = map(int, input().split())
s = [[0 for j in range(501)] for i in range(501)]
for _ in range(M):
	(L, R) = map(int, input().split())
	s[L][R] += 1
for i in range(1, 501):
	for j in range(1, 501):
		s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]
for _ in range(Q):
	(p, q) = map(int, input().split())
	print(s[q][q] - s[p - 1][q] - s[q][p - 1] + s[p - 1][p - 1])


import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
import numpy as np

def input():
	return sys.stdin.readline().strip()

def INT():
	return int(input())

def MAP():
	return list(map(int, input().split()))

def LIST():
	return list(map(int, input().split()))

def ZIP(n):
	return list(zip(*(MAP() for _ in range(n))))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
(N, M, Q) = MAP()
LR = [LIST() for _ in range(M)]
pq = [LIST() for _ in range(Q)]
x = np.zeros((N + 1, N + 1), dtype=np.int64)
for (L, R) in LR:
	x[L, R] += 1
x = x.cumsum(axis=0).cumsum(axis=1)
for (p, q) in pq:
	print(x[q][q] - x[q][p - 1] - x[p - 1][q] + x[p - 1][p - 1])


(n, m, q) = map(int, input().split())
T = [[0] * n for i in range(n)]
for i in range(m):
	(l, r) = map(int, input().split())
	T[l - 1][r - 1] += 1
for i in range(n):
	for j in range(1, n):
		T[i][j] += T[i][j - 1]
for j in range(n):
	for i in range(n - 2, -1, -1):
		T[i][j] += T[i + 1][j]
for i in range(q):
	(p, q) = map(int, input().split())
	print(T[p - 1][q - 1])


(N, M, Q) = map(int, input().split())
matrix = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
	(l, r) = map(int, input().split())
	matrix[l][r] += 1
accmatrix = [[0] * (N + 1) for _ in range(N + 1)]
for l in range(1, N + 1):
	accmatrix[l] = [x + y for (x, y) in zip(accmatrix[l - 1], matrix[l])]
for l in range(1, N + 1):
	lis = accmatrix[l]
	for r in range(1, N + 1):
		lis[r] += lis[r - 1]
for _ in range(Q):
	(p, q) = map(int, input().split())
	ans = accmatrix[q][q] - accmatrix[p - 1][q] - accmatrix[q][p - 1] + accmatrix[p - 1][p - 1]
	print(ans)


(n, m, q) = map(int, input().split())
lr = []
for _ in range(m):
	lr.append(list(map(int, input().split())))
a = [[0] * n for i in range(n)]
for (l, r) in lr:
	a[l - 1][r - 1] += 1
cnt = [[0] * n for i in range(n)]
for y in range(n):
	v = 0
	for x in range(y, -1, -1):
		v += a[x][y]
		cnt[x][y] = cnt[x][y - 1] + v
for _ in range(q):
	(p, q) = map(int, input().split())
	print(cnt[p - 1][q - 1])


import sys
sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7

def resolve():
	(n, m, q) = list(map(int, input().split()))
	cnt = [[0] * n for _ in range(n)]
	for _ in range(m):
		(l, r) = list(map(int, input().split()))
		cnt[l - 1][r - 1] += 1
	R = [[0] * (n + 1) for _ in range(n + 1)]
	for h in range(n):
		for w in range(n):
			R[h + 1][w + 1] = R[h][w + 1] + R[h + 1][w] - R[h][w] + cnt[h][w]
	for _ in range(q):
		(p, q) = list(map(int, input().split()))
		res = R[q][q] - R[p - 1][q] - R[q][p - 1] + R[p - 1][p - 1]
		print(res)

def __starting_point():
	resolve()
__starting_point()


(n, m, q) = map(int, input().split())
x = [[0] * (n + 1) for i in range(n + 1)]
c = [[0] * (n + 1) for i in range(n + 1)]
for i in range(m):
	(l, r) = map(int, input().split())
	x[l][r] += 1
for i in range(1, n + 1):
	for j in range(1, n + 1):
		c[i][j] = c[i][j - 1] + x[i][j]
for i in range(q):
	(p, q) = map(int, input().split())
	s = 0
	for j in range(p, q + 1):
		s += c[j][q] - c[j][p - 1]
	print(s)


(N, M, Q) = map(int, input().split())
train = [list(map(int, input().split())) for i in range(M)]
qs = [list(map(int, input().split())) for i in range(Q)]
ns = []
for i in range(N + 1):
	ns.append([0] * (N + 1))
for (l, r) in train:
	for i in range(r, N + 1):
		ns[l][i] += 1
for (p, q) in qs:
	ans = 0
	for i in range(p, q + 1):
		ans += ns[i][q]
	print(ans)


from itertools import accumulate
(N, M, Q) = map(int, input().split())
D = [[0] * (N + 1) for i in range(N + 1)]
for _ in range(M):
	(L, R) = map(int, input().split())
	D[L][R] += 1
for i in range(N - 1, 0, -1):
	for j in range(1, N + 1):
		D[i][j] += D[i + 1][j]
for i in range(1, N + 1):
	D[i] = list(accumulate(D[i]))
for _ in range(Q):
	(p, q) = map(int, input().split())
	print(D[p][q])


import itertools
(n, m, q) = map(int, input().split())
LR = [[0] * (n + 1) for i in range(n + 1)]
for i in range(m):
	(l, r) = map(int, input().split())
	LR[l][r] += 1
for i in range(n):
	LR[i] = list(itertools.accumulate(LR[i]))
for i in range(q):
	(l, r) = map(int, input().split())
	ans = 0
	for j in range(l, r + 1):
		ans += LR[j][r] - LR[j][l - 1]
	print(ans)


(n, m, q_) = list(map(int, input().split()))
lr = [list(map(int, input().split())) for _ in range(m)]
pq = [list(map(int, input().split())) for _ in range(q_)]
from collections import defaultdict
dmap = defaultdict(int)
smap = defaultdict(int)
ssmap = defaultdict(int)
for (l, r) in lr:
	if (l, r) in dmap:
		dmap[l, r] += 1
	else:
		dmap[l, r] = 1
for i in range(1, n + 1):
	tmp = 0
	for j in range(i, n + 1):
		if (i, j) in dmap:
			tmp += dmap[i, j]
		smap[i, j] = tmp
for i in range(1, n + 1):
	tmp = 0
	for j in range(1, i + 1):
		tmp += smap[j, i]
		ssmap[j, i] = tmp
for (p, q) in pq:
	ans = ssmap[q, q] - ssmap[p - 1, q]
	print(ans)


from sys import stdin
import numpy as np

def main():
	readline = stdin.readline
	(n, m, q) = map(int, readline().split())
	table = np.array([[0] * n for _ in range(n)], dtype='int64')
	for i in range(m):
		(l, r) = map(lambda x: int(x) - 1, readline().split())
		table[l][r] += 1
	for i in range(n):
		table[i] = table[i].cumsum()
	ans = [0] * q
	for i in range(q):
		(l, r) = map(lambda x: int(x) - 1, readline().split())
		ans[i] = table[l:r + 1, r].sum()
	for i in range(q):
		print(ans[i])

def __starting_point():
	main()
__starting_point()


from bisect import bisect_right
(N, M, Q) = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(M)]
lr.sort(reverse=True)
lst = [[]]
j = N - 1
for i in range(M):
	if lr[i][0] - 1 < j:
		lst[-1].sort()
		while lr[i][0] - 1 < j:
			lst.append(lst[-1][:])
			j -= 1
	lst[-1].append(lr[i][-1] - 1)
lst[-1].sort()
lst.reverse()
for i in range(Q):
	(p, q) = map(int, input().split())
	m = bisect_right(lst[p - 1], q - 1)
	print(m)


(n, m, Q) = map(int, input().split())
a = []
for i in range(n + 1):
	a.append([0] * (n + 1))
s = a[:]
for i in range(m):
	(l, r) = map(int, input().split())
	a[l][r] += 1
for l in range(1, n + 1):
	for r in range(1, n + 1):
		s[l][r] = a[l][r] + s[l - 1][r] + s[l][r - 1] - s[l - 1][r - 1]
for i in range(Q):
	(p, q) = map(int, input().split())
	print(s[q][q] - s[p - 1][q] - s[q][p - 1] + s[p - 1][p - 1])


from itertools import accumulate
(n, m, q) = map(int, input().split())
li = [[0 for i in range(n + 1)] for j in range(n + 1)]
lin = []
for i in range(m):
	(l, r) = map(int, input().split())
	li[l][r] += 1
for i in range(n + 1):
	lin += [list(accumulate(li[i]))]
for i in range(q):
	(l, r) = map(int, input().split())
	point = 0
	for i in range(l, r + 1):
		point += lin[i][r] - lin[i][l - 1]
	print(point)


(n, m, q) = map(int, input().split())
A = [[0] * (n + 1) for i in range(n + 1)]
for i in range(m):
	(a, b) = map(int, input().split())
	A[a][b] = A[a][b] + 1
B = [[0] * (n + 1) for i in range(n + 1)]
for i in range(1, n + 1):
	for j in range(1, n + 1):
		B[i][j] = B[i - 1][j] + B[i][j - 1] - B[i - 1][j - 1] + A[i][j]
for i in range(q):
	(x, y) = map(int, input().split())
	print(B[y][y] - B[y][x - 1] - B[x - 1][y] + B[x - 1][x - 1])


(n, m, q) = list(map(int, input().split()))
lr = [[0 for i in range(501)] for i in range(501)]
for i in range(m):
	(lt, rt) = list(map(int, input().split()))
	lr[lt][rt] += 1
for i in range(1, 501):
	for j in range(1, 501):
		lr[i][j] += lr[i][j - 1]
for i in range(q):
	(lt, rt) = list(map(int, input().split()))
	ans = 0
	for j in range(lt, rt + 1):
		ans += lr[j][rt] - lr[j][j - 1]
	print(ans)


(N, M, Q) = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(M)]
pq = [list(map(int, input().split())) for _ in range(Q)]
L = [[0] * N for _ in range(N)]
for (l, r) in LR:
	L[l - 1][r - 1] += 1
for i in range(1, N):
	for j in range(N - i):
		L[j][j + i] += L[j][j + i - 1] + L[j + 1][i + j] - L[j + 1][j + i - 1]
for (p, q) in pq:
	print(L[p - 1][q - 1])


import sys
sys.setrecursionlimit(10010010)

def abc106_d():
	(n, m, q) = map(int, input().split())
	table = [[0] * (n + 1) for _ in range(n + 1)]
	for _ in range(m):
		(l, r) = map(int, input().split())
		table[l][r] += 1
	query = [tuple(map(int, input().split())) for _ in range(q)]
	dp = [[-1] * (n + 1) for _ in range(n + 1)]

	def calc(l, r):
		nonlocal dp
		if l == 0 or r == 0:
			return 0
		if dp[l][r] != -1:
			return dp[l][r]
		res = calc(l - 1, r) + calc(l, r - 1) - calc(l - 1, r - 1) + table[l][r]
		dp[l][r] = res
		return res
	for (p, q) in query:
		ans = calc(q, q) - calc(q, p - 1) - calc(p - 1, q) + calc(p - 1, p - 1)
		print(ans)

def __starting_point():
	abc106_d()
__starting_point()


from itertools import accumulate
from operator import add, mul
(n, m, q) = map(int, input().split())
a = []
b = []
for i in range(n):
	a.append([0] * n)
	b.append([0] * n)
for i in range(m):
	(l, r) = map(int, input().split())
	a[l - 1][r - 1] += 1
for i in range(n):
	a[i] = list(accumulate(a[i]))
for i in range(n):
	for j in range(n - i - 1):
		a[n - i - j - 2][n - i - 1] += a[n - i - j - 1][n - i - 1]
for i in range(q):
	(P, Q) = map(int, input().split())
	print(a[P - 1][Q - 1])


(N, M, Q) = map(int, input().split())
t = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
	(L, R) = map(int, input().split())
	t[L][R] += 1
for i in range(N + 1):
	for j in range(N):
		t[i][j + 1] += t[i][j]
for i in range(N):
	for j in range(N + 1):
		t[i + 1][j] += t[i][j]
result = []
for _ in range(Q):
	(p, q) = map(int, input().split())
	result.append(t[q][q] + t[p - 1][p - 1] - t[p - 1][q] - t[q][p - 1])
print(*result, sep='\n')


(N, M, Q) = map(int, input().split())
Trs = [tuple(map(int, input().split())) for i in range(M)]
pqs = [tuple(map(int, input().split())) for i in range(Q)]
cs = [[0 for i in range(N + 1)] for j in range(N + 1)]
for tr in Trs:
	cs[tr[0]][tr[1]] += 1
for i in range(N):
	for j in range(N):
		cs[i + 1][j + 1] += cs[i + 1][j]
for i in range(N):
	for j in range(N):
		cs[i + 1][j + 1] += cs[i][j + 1]
for pq in pqs:
	p = pq[0]
	q = pq[1]
	n = cs[q][q] - cs[q][p - 1] - cs[p - 1][q] + cs[p - 1][p - 1]
	print(n)


import sys
input = sys.stdin.readline
(N, M, Q) = map(int, input().split())
com = [[0] * 502 for i in range(502)]
for _ in range(M):
	(L, R) = map(int, input().split())
	com[L][R] += 1
for i in range(502):
	for j in range(1, 502):
		com[i][j] += com[i][j - 1]
for _ in range(Q):
	(p, q) = map(int, input().split())
	ans = 0
	for i in range(p, q + 1):
		ans += com[i][q]
	print(ans)


s = input().split()
(n, m, q) = (int(s[0]), int(s[1]), int(s[2]))
arr = [[0 for i in range(n + 3)] for j in range(n + 3)]
for i in range(m):
	s = input().split()
	(l, r) = (int(s[0]), int(s[1]))
	for j in range(l + 1):
		arr[j][r] += 1
for i in range(q):
	s = input().split()
	(p, q) = (int(s[0]), int(s[1]))
	print(sum(arr[p][1:q + 1]))


import numpy as np
import sys
input = sys.stdin.readline
(N, M, Q) = map(int, input().split())
T = np.zeros((N, N), dtype=np.int32)
for _ in [0] * M:
	(l, r) = map(int, input().split())
	T[l - 1, r - 1] += 1
T = T[::-1].cumsum(axis=0).cumsum(axis=1)[::-1]
for _ in [0] * Q:
	(p, q) = map(int, input().split())
	print(T[p - 1, q - 1])


(N, M, Q) = map(int, input().split())
train = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(M):
	(a, b) = map(int, input().split())
	train[a][b] += 1
for i in range(1, N + 1):
	for j in range(1, N + 1):
		train[i][j] += train[i][j - 1]
for i in range(Q):
	ans = 0
	(l, r) = map(int, input().split())
	for j in range(l, r + 1):
		ans += train[j][r] - train[j][l - 1]
	print(ans)


(n, m, q) = map(int, input().split())
S = [[0 for i in range(n + 1)] for j in range(n + 1)]
for i in range(m):
	(l, r) = map(int, input().split())
	S[l][r] += 1
for i in range(1, n + 1):
	for j in range(1, n):
		S[i][j + 1] += S[i][j]
for i in range(q):
	(a, b) = map(int, input().split())
	ans = 0
	for y in range(a, b + 1):
		ans += S[y][b] - S[y][a - 1]
	print(ans)


(n, m, q) = map(int, input().split())
bi = [[0 for i in range(n + 1)] for j in range(n + 1)]
for i in range(m):
	(l, r) = map(int, input().split())
	bi[l][r] += 1
ans = [[0 for i in range(n + 1)] for j in range(n + 1)]
for i in range(1, n + 1):
	cou = 0
	for j in range(1, n + 1):
		cou += bi[i][j]
		ans[i][j] = ans[i - 1][j] + cou
for i in range(q):
	(p, q) = map(int, input().split())
	print(ans[q][q] - ans[q][p - 1] - ans[p - 1][q] + ans[p - 1][p - 1])


import numpy as np
import sys
input = sys.stdin.readline

def main():
	(n, m, q) = map(int, input().split())
	counts = np.zeros((n + 1, n + 1), dtype=np.int32)
	for _ in range(m):
		(from_, to) = map(int, input().split())
		counts[:from_ + 1, to] += 1
	counts = np.cumsum(counts, axis=1)
	queries = np.array([list(map(int, input().split())) for _ in range(q)])
	ps = queries[:, 0]
	qs = queries[:, 1]
	res = counts[ps, qs]
	print(*res, sep='\n')

def __starting_point():
	main()
__starting_point()


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


(N, M, Q) = map(int, input().split())
X = [[0 for _ in range(N + 1)] for __ in range(N + 1)]
for i in range(M):
	(L, R) = map(int, input().split())
	X[L][R] += 1
for i in range(N + 1):
	for j in range(N):
		X[i][j + 1] += X[i][j]
for i in range(N + 1):
	for j in range(N):
		X[j + 1][i] += X[j][i]
for i in range(Q):
	(p, q) = map(int, input().split())
	print(X[q][q] - X[p - 1][q])


import numpy as np
(N, M, Q) = map(int, input().split())
table = [[0] * N for _ in range(N)]
for _ in range(M):
	(L, R) = map(lambda n: int(n) - 1, input().split())
	table[R][-L - 1] += 1
table = np.array(table, dtype=np.int64).cumsum(axis=0).cumsum(axis=1).tolist()
for _ in range(Q):
	(p, q) = map(lambda n: int(n) - 1, input().split())
	print(table[q][-p - 1])


from itertools import accumulate

def a():
	return map(int, input().split())
(n, m, q) = a()
s = [[0 for i in range(n)] for j in range(n)]
for i in range(m):
	(x, y) = a()
	s[n - x][y - 1] += 1

def f(s):
	for i in range(len(s)):
		s[i] = list(accumulate(s[i]))
f(s)
s = list(zip(*s))
f(s)
for i in range(q):
	(x, y) = a()
	print(s[y - 1][n - x])


(n, m, Q) = map(int, input().split())
M = [[0] * n for _ in range(n)]
for i in range(m):
	(l, r) = map(int, input().split())
	M[r - 1][l - 1] += 1
for q in range(n):
	for p in reversed(range(1, n)):
		M[q][p - 1] += M[q][p]
for p in range(n):
	for q in range(n - 1):
		M[q + 1][p] += M[q][p]
for i in range(Q):
	(p, q) = map(int, input().split())
	print(M[q - 1][p - 1])


class Cumsum2d(object):

	def __init__(self, a):
		self.a = a
		self.h = len(a)
		self.w = len(a[0])
		self._cumsum = [[0 for _ in range(self.w + 1)] for _ in range(self.h + 1)]
		self._preprocess()

	def _preprocess(self):
		for i in range(1, self.h + 1):
			for j in range(1, self.w + 1):
				self._cumsum[i][j] = self.a[i - 1][j - 1] + self._cumsum[i][j - 1] + self._cumsum[i - 1][j] - self._cumsum[i - 1][j - 1]

	def query(self, h1, h2, w1, w2):
		return self._cumsum[h2][w2] - self._cumsum[h1][w2] - self._cumsum[h2][w1] + self._cumsum[h1][w1]

def __starting_point():
	(N, M, Q) = [int(x) for x in input().split(' ')]
	count = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
	for _ in range(M):
		(l, r) = [int(x) for x in input().split(' ')]
		count[l][r] += 1
	cumsum = Cumsum2d(count)
	for _ in range(Q):
		(p, q) = [int(x) for x in input().split(' ')]
		print(cumsum.query(p, q + 1, p, q + 1))
__starting_point()


(n, m, q) = map(int, input().split())
table = []
for i in range(n + 1):
	table.append([0] * (n + 1))
for i in range(m):
	(a, b) = map(int, input().split())
	table[b][a] += 1
for i in range(2, n + 1):
	for j in range(1, n + 2 - i):
		table[i + j - 1][j] += table[i + j - 1][j + 1] + table[i + j - 2][j] - table[i + j - 2][j + 1]
for _ in range(q):
	(start, end) = map(int, input().split())
	print(table[end][start])


(n, m, k) = map(int, input().split())
R = [[0] * n for _ in range(n)]
for _ in range(m):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	R[r][l] += 1
for i in range(1, n):
	for j in range(n):
		R[i][j] += R[i - 1][j]
for i in range(n):
	for j in range(n - 2, -1, -1):
		R[i][j] += R[i][j + 1]
for _ in range(k):
	(p, q) = map(int, input().split())
	print(R[q - 1][p - 1])


(N, M, Q) = list(map(int, input().split()))
Map = [[0] * 500 for i in range(500)]
for i in range(M):
	(l, r) = list(map(int, input().split()))
	(l, r) = (l - 1, r - 1)
	Map[r][l] += 1
S = [[0] * 501 for i in range(501)]
for i in range(500):
	s = 0
	for j in range(500):
		s += Map[i][j]
		S[i + 1][j + 1] = S[i][j + 1] + s
for i in range(Q):
	(p, q) = list(map(int, input().split()))
	print(S[q][500] - S[q][p - 1])


(n, m, Q) = map(int, input().split())
d = [[0] * (n + 1) for i in range(n + 1)]
for i in range(m):
	(l, r) = map(int, input().split())
	d[l][r] += 1
for i in range(1, n + 1):
	for j in range(1, n + 1):
		d[i][j] += d[i][j - 1]
pq = [list(map(int, input().split())) for i in range(Q)]
for u in pq:
	(p, q) = u
	ans = 0
	for i in range(p, q + 1):
		ans += d[i][q]
	print(ans)


import sys
input = sys.stdin.readline
(N, M, Q) = map(int, input().split())
cum = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
	(l, r) = map(int, input().split())
	cum[l][r] += 1
for i in range(1, N + 1):
	for j in range(i + 1, N + 1):
		cum[i][j] += cum[i][j - 1]
for _ in range(Q):
	(p, q) = map(int, input().split())
	tot = 0
	for i in range(p, q + 1):
		tot += cum[i][q]
	print(tot)


(N, M, Q) = map(int, input().split())
s = [[0 for j in range(N + 1)] for i in range(N + 1)]
for i in range(M):
	(l, r) = map(int, input().split())
	s[l][r] += 1
for i in range(1, N + 1):
	for j in range(1, N + 1):
		s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]
for i in range(Q):
	(l, r) = map(int, input().split())
	print(s[r][r] - s[r][l - 1] - s[l - 1][r] + s[l - 1][l - 1])


import numpy as np
(n, m, q) = list(map(int, input().split()))
x = np.zeros((n, n), dtype=int)
for _ in range(m):
	(l, r) = list(map(int, input().split()))
	x[r - 1][l - 1] += 1
x.cumsum(out=x, axis=0)
for i in range(n):
	x[i] = np.cumsum(x[i][::-1])[::-1]
for _ in range(q):
	(l, r) = list(map(int, input().split()))
	print(x[r - 1][l - 1])


from copy import deepcopy
(n, m, q) = list(map(int, input().split()))
lr = [list(map(int, input().split())) for _ in range(m)]
pq = [list(map(int, input().split())) for _ in range(q)]
cnt = [[0] * (n + 1) for _ in range(n + 1)]
for (l, r) in lr:
	cnt[l][r] += 1
acc = deepcopy(cnt)
for i in range(n):
	for j in range(n):
		tmp = acc[i][j + 1] + acc[i + 1][j] - acc[i][j]
		acc[i + 1][j + 1] += tmp
for (p, q) in pq:
	p -= 1
	ans = acc[q][q] - acc[p][q] - acc[q][p] + acc[p][p]
	print(ans)


(N, M, Q) = map(int, input().split())
lst = []
cnt = [0] * N
ans = [0] * Q
for i in range(M):
	(a, b) = map(int, input().split())
	lst.append([b, a, 't'])
for i in range(Q):
	(a, b) = map(int, input().split())
	lst.append([b, a + 500, i])
lst.sort()
for i in lst:
	if i[2] == 't':
		cnt[i[1] - 1] += 1
	else:
		ans[i[2]] = sum(cnt[i[1] - 501:i[0]])
for j in ans:
	print(j)


from itertools import accumulate
(N, M, Q) = map(int, input().split())
table = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(M):
	(l, r) = map(int, input().split())
	table[l][r] += 1
dp = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(N):
	dp[i + 1] = list(accumulate(table[i + 1]))
for i in range(Q):
	(p, q) = map(int, input().split())
	sum = 0
	for k in range(p, q + 1):
		sum += dp[k][q] - dp[k][p - 1]
	print(sum)


(n, m, q) = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(m)]
p = [list(map(int, input().split())) + [i] for i in range(q)]
l.extend(p)
l = sorted(l, key=lambda x: x[1])
ka = [0] * n
ans = []
for i in l:
	if len(i) == 2:
		ka[i[0] - 1] += 1
	else:
		ans.append([i[2], sum(ka[i[0] - 1:i[1]])])
ans = sorted(ans)
for i in range(len(ans)):
	print(ans[i][1])


import sys

def input():
	return sys.stdin.readline()[:-1]

def make_sumtable():
	sumtable = [[0] * (N + 1) for i in range(N + 1)]
	for i in range(M):
		sumtable[L[i]][R[i]] += 1
	for i in range(1, N + 1):
		for j in range(1, N + 1):
			sumtable[i][j] += sumtable[i - 1][j]
			sumtable[i][j] += sumtable[i][j - 1]
			sumtable[i][j] -= sumtable[i - 1][j - 1]
	return sumtable
(N, M, Q) = list(map(int, input().split()))
L = []
R = []
for i in range(M):
	(l, r) = list(map(int, input().split()))
	L.append(l)
	R.append(r)
sumtable = make_sumtable()
for i in range(Q):
	(p, q) = list(map(int, input().split()))
	print(sumtable[q][q] - sumtable[q][p - 1] - sumtable[p - 1][q] + sumtable[p - 1][p - 1])


(N, M, Q) = map(int, input().split())
num = [[0 for i in range(N)] for j in range(N)]
lr = [list(map(int, input().split())) for i in range(M)]
for (l, r) in lr:
	num[l - 1][r - 1] += 1
for j in range(N):
	for i in range(N - 1, 0, -1):
		num[i - 1][j] += num[i][j]
for i in range(N):
	for j in range(N - 1):
		num[i][j + 1] += num[i][j]
for i in range(Q):
	(p, q) = map(int, input().split())
	print(num[p - 1][q - 1])


(N, M, Q) = map(int, input().split())
S = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
	(l, r) = map(int, input().split())
	S[l][r] += 1
C = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
	for j in range(1, N + 1):
		C[i][j] = C[i - 1][j] + C[i][j - 1] + S[i][j] - C[i - 1][j - 1]
for _ in range(Q):
	(l, r) = map(int, input().split())
	print(C[r][r] - C[r][l - 1] - C[l - 1][r] + C[l - 1][l - 1])


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


from itertools import accumulate
(N, M, Q) = map(int, input().split())
ST = [[0 for x in range(N + 2)] for y in range(N + 2)]
for i in range(M):
	(s, t) = map(int, input().split())
	ST[1][t] += 1
	ST[s + 1][t] -= 1
	ST[1][N + 1] += 1
	ST[s + 1][N + 1] -= 1
ST1 = [list(accumulate(l)) for l in zip(*ST)]
ST2 = [list(accumulate(l)) for l in zip(*ST1)]
for i in range(Q):
	(s, t) = map(int, input().split())
	print(ST2[s][t])


def train_map(LR, N):
	train = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
	for (l, r) in LR:
		train[l][r] += 1
	for i in range(N + 1):
		for j in range(1, N + 1):
			train[i][j] += train[i][j - 1]
	for j in range(N + 1):
		for i in reversed(list(range(1, N + 1))):
			train[i - 1][j] += train[i][j]
	return train

def main():
	(N, M, Q) = list(map(int, input().split()))
	LR = [list(map(int, input().split())) for _ in range(M)]
	pq = [list(map(int, input().split())) for _ in range(Q)]
	train = train_map(LR, N)
	for (p, q) in pq:
		print(train[p][q])

def __starting_point():
	main()
__starting_point()


(N, M, Q) = map(int, input().split())
C = [[0 for i in range(N + 1)] for j in range(N + 1)]
for i in range(M):
	(L, R) = map(int, input().split())
	C[L][R] += 1
D = [[0 for i in range(N + 4)] for j in range(N + 4)]
for i in range(N + 1):
	for j in range(N + 1):
		D[i][j + 1] = D[i][j] + C[i][j]
for j in range(Q):
	(p, q) = map(int, input().split())
	s = 0
	for i in range(p, q + 1):
		s += D[i][q + 1] - D[i][i]
	print(s)


import numpy as np

def main():
	(n, m, q) = map(int, input().split())
	lst = np.zeros((n, n), dtype=int)
	for _ in range(m):
		(s, t) = map(int, input().split())
		lst[s - 1][t - 1] += 1
	lst = lst.cumsum(axis=1)[::-1].cumsum(axis=0)[::-1]
	for _ in range(q):
		(s, t) = map(int, input().split())
		print(lst[s - 1][t - 1])
main()


(N, M, Q) = map(int, input().split())
MAP = [[0] * N for i in range(N)]
for i in range(M):
	(L, R) = map(int, input().split())
	MAP[L - 1][R - 1] += 1
for r in range(N):
	for l in range(N - 1, 0, -1):
		MAP[l - 1][r] += MAP[l][r]
for r in range(N - 1):
	for l in range(N):
		MAP[l][r + 1] += MAP[l][r]
for i in range(Q):
	(p, q) = map(int, input().split())
	print(MAP[p - 1][q - 1])


(n, m, q) = map(int, input().split())
train = [[0] * n for i in range(n)]
for i in range(m):
	(l, r) = map(int, input().split())
	train[l - 1][r - 1] += 1
for i in range(n):
	for j in range(n - 1):
		train[i][j + 1] += train[i][j]
for i in range(q):
	(p, q_) = map(int, input().split())
	ans = 0
	for j in range(p - 1, q_):
		ans += train[j][q_ - 1]
	print(ans)