Problem:
 Score: 400 points    Problem Statement  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 1 2 3 1
1 1
1 2
2 2
1 2      Sample Output 1 3  As all the trains runs within the section from City 1 to City 2 , the answer to the only query is 3 .       Sample Input 2 10 3 2
1 5
2 8
7 10
1 7
3 10      Sample Output 2 1
1  The first query is on the section from City 1 to 7 . There is only one train that runs strictly within that section: Train 1 .
The second query is on the section from City 3 to 10 . There is only one train that runs strictly within that section: Train 3 .       Sample Input 3 10 10 10
1 6
2 9
4 5
4 7
4 7
5 8
6 6
6 7
7 9
10 10
1 8
1 9
1 10
2 8
2 9
2 10
3 8
3 9
3 10
1 10      Sample Output 3 7
9
10
6
8
9
6
7
8
10

Solution (Python):


"""
参考：https://img.atcoder.jp/abc106/editorial.pdf
　　　https://atcoder.jp/contests/abc106/submissions/3024983
　　　https://imoz.jp/algorithms/imos_method.html
・二次元累積和
・最後にどこを足し引きするかは上記参考の二次元いもすと同じ話だと思う。
"""

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(1, N+1):
    for j in range(2, N+1):
        LR[i][j] += LR[i][j-1]
for i in range(1, N+1):
    for j in range(2, N+1):
        LR[j][i] += LR[j-1][i]

for i in range(Q):
    p, q = map(int, input().split())
    
    ans = LR[p-1][p-1] - LR[p-1][q] - LR[q][p-1] + LR[q][q]
    print(ans)

Solution (Python):


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

N, M, Q = map(int, input().split())
lM, rM = [0] * M, [0] * M
pQ, qQ = [0] * Q, [0] * Q
LR = [[0] * N for i in range(N)]

for i in range(M):
    l, r = map(int, input().split())
    lM[i], rM[i] = l-1, r-1
    LR[l-1][r-1] += 1
for i in range(Q):
    p, q = map(int, input().split())
    pQ[i], qQ[i] = p-1, q-1


cnt = [[0] * N for i in range(N)]
for i in range(N):
    cnt[i][i] = LR[i][i]
    for j in range(1, N):
        cnt[i][j] = cnt[i][j-1] + LR[i][j]

for i in range(Q):
    ans = 0
    for j in range(pQ[i], qQ[i]+1):
        
        
        ans += cnt[j][qQ[i]]
    print(ans)

Solution (Python):
n,m,q = map(int,input().split())

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






for i in range(n) :
    for j in range(n) :
        left = 0
        btm  = 0
        mid  = 0

        if i > 0 :
            left = lr[j][i-1]
        if j > 0 :
            btm  = lr[j-1][i]
        if i > 0 and j > 0 :
            mid  = lr[j-1][i-1]
       
        lr[j][i] = lr[j][i] + left + btm - mid




ans=[] 
for i in range(q) :
    l,r = map(int,input().split())

    l = l - 1
    r = r - 1
    pre = 0
    if l > 0:    
        
        pre = lr[l-1][r] + lr[r][l-1] - lr[l-1][l-1]     

    count = lr[r][r] - pre
    ans.append(count)

for a in ans:
    print(a)

Solution (Python):
import sys
input = sys.stdin.readline

N, M, Q = (int(i) for i in input().split())
dp = [[0] *(N+1) for i in range(N+1)]
for i in range(M):
    L, R = (int(i) for i in input().split())
    dp[L-1][R-1] += 1

for j in range(N):
    for i in range(N-j):
        dp[i][i + j] = dp[i][i + j - 1]  + dp[i + 1][i + j] - dp[i + 1][i + j - 1] + dp[i][i + j]

for i in range(Q):
    L, R = (int(i) for i in input().split())
    print(dp[L-1][R-1])

Solution (Python):
N, M, QN = [int(x) for x in input().split()]

MAT0 = [[0] * (N + 1) for _ in range(N + 1)]

for i in range(M):
    l, r = [int(x) for x in input().split()]
    MAT0[l][r] += 1

MAT = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
    for j in range(1, N + 1):
        MAT[i][j] = MAT[i][j - 1] + MAT0[i][j]

MM = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
    for j in range(1, N + 1):
        MM[i][j] = MM[i - 1][j] + MAT[i][j]

for i in range(QN):
    p, q = [int(x) for x in input().split()]
    ret = 0
    ret = ret + MM[q][q] - MM[q][p - 1] - MM[p - 1][q] + MM[p - 1][p - 1]
    print(ret)

Solution (Python):
N, M, Q = [int(_) for _ in input().split()]
LR = [[int(_) for _ in input().split()] for _ in range(M)]
PQ = [[int(_) for _ in input().split()] for _ in range(Q)]

cumsum = [[0] * (N+2) for _ in range(N+1)]
for lr in LR:
    cumsum[lr[0]][lr[0]] += 1
    if lr[1] < N:
        cumsum[lr[0]][lr[1]+1] -= 1
for i in range(N+1):
    for j in range(i, N):
        cumsum[i][j+1] += cumsum[i][j]
for pq in PQ:
    print(sum([cumsum[i][i]-cumsum[i][pq[1]+1]
               for i in range(pq[0], pq[1]+1)]))

Solution (Python):
class Train:
    def __init__(self, left, right):
        self.left = left
        self.right = right


class Question:
    def __init__(self, p, q):
        self.p = p
        self.q = q


N, M, Q = map(int, input().split())
trains = []
questions = []
for _ in range(M):
    left, right = map(int, input().split())
    trains.append(Train(left, right))
for _ in range(Q):
    p, q = map(int, input().split())
    questions.append(Question(p, q))

m = {}
cm = {}
for i in range(N+1):
    for j in range(N+1):
        m.setdefault(i, {})
        m[i][j] = 0
        cm.setdefault(i, {})
        cm[i][j] = 0

for train in trains:
    m[train.left][train.right] += 1

for i in range(1, N+1):
    for j in range(1, N+1):
        cm[i][j] = m[i][j] + cm[i][j-1]

for i in range(1, N+1):
    for j in range(1, N+1):
        cm[i][j] += cm[i-1][j]
for question in questions:
    print(cm[question.q][question.q] + cm[question.p-1][question.p-1] -
          cm[question.p-1][question.q]-cm[question.q][question.p-1])

Solution (Python):
N,M,Q = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(M)]
qs = [tuple(map(int,input().split())) for i in range(Q)]

imos = [[0]*(N+1) for i in range(N+1)]
for l,r in src:
    imos[l][r] += 1

for i in range(N+1):
    for j in range(N):
        imos[i][j+1] += imos[i][j]
for i in range(N):
    for j in range(N+1):
        imos[i+1][j] += imos[i][j]

for p,q in qs:
    ans = imos[p-1][p-1] + imos[q][q] - imos[p-1][q] - imos[q][p-1]
    print(ans)

Solution (Python):
N, M, Q = [int(v) for v in input().split()]
p = []
q = []
c = [[0] * (N+1) for i in range(N+1)]

for i in range(M):
    l, r = [int(v) for v in input().split()]
    c[l][r] += 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):
    a, b = [int(v) for v in input().split()]
    p.append(a)
    q.append(b)

for l, r in zip(p, q):
    ans = c[r][r] + c[l-1][l-1] - c[l-1][r] - c[r][l-1]
    print(ans)

Solution (Python):
N, M, Q = [int(v) for v in input().split()]
p = []
q = []
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 = [int(v) for v in 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):
    a, b = [int(v) for v in input().split()]
    p.append(a)
    q.append(b)

for i in range(Q):
    ans = 0
    for j in range(p[i], q[i]+1):
        ans += c[j][q[i]] - c[j][p[i]-1]
    print(ans)

Solution (Python):
N,M,Q=map(int,input().split())
Train=[[int(i) for i in input().split()] for i in range(M)]
Map=[[0]*(N+1) for i in range(N+1)]
for i in Train:
  x,y=i[0],i[1]
  Map[y][x]+=1
for a in range(1,N+1):
  for b in range(1,N+1):
    if b<=N-1:
      Map[a][b+1]=Map[a][b]+Map[a][b+1]
    if a>=2:
      Map[a][b]=Map[a-1][b]+Map[a][b]
for i in range(Q):
  p,q=map(int,input().split())
  print(Map[q][q]-Map[q][p-1]-Map[p-1][q]+Map[p-1][p-1])

Solution (Python):
n, m, q = map(int, input().split())
imos = [[0 for i in range(n)] for j in range(n)]

for i in range(m):
    l, r = map(int, input().split())
    imos[l-1][r-1] += 1

for i in range(n):
    for j in range(n-1):
        imos[i][j+1] += imos[i][j]

for j in range(n):
    for i in range(n-1):
        imos[i+1][j] += imos[i][j]

for i in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    if l == 0:
        print(imos[r][r])
    else:
        print(imos[r][r] - imos[l - 1][r] - imos[r][l - 1] + imos[l - 1][l - 1])

Solution (Python):
N,M,Q = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(M)]
qs = [tuple(map(int,input().split())) for i in range(Q)]

imos = [[0]*(N+1) for i in range(N+1)]
for l,r in src:
    imos[l][r] += 1
for i in range(N+1):
    for j in range(N):
        imos[i][j+1] += imos[i][j]
for i in range(N):
    for j in range(N+1):
        imos[i+1][j] += imos[i][j]

ans = []
for p,q in qs:
    ans.append(imos[q][q] - imos[q][p-1] - imos[p-1][q] + imos[p-1][p-1])
print(*ans, sep='\n')

Solution (Python):
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def cum_2d(field:list):
    row = len(field)
    col = len(field[0])
    
    
    for r in range(row):
        for c in range(col-1):
            field[r][c+1] += field[r][c]
    
    
    for c in range(col):
        for r in range(row-1):
            field[r+1][c] += field[r][c]
            
    return field


n,m,q = li()
grid = [[0 for _ in range(n+1)] for _ in range(n+1)]

for _ in range(m):
    l,r = li()
    grid[l][r] += 1
    
grid = cum_2d(grid)


for _ in range(q):
    p,q = li()
    print(grid[q][q] - grid[q][p-1] - grid[p-1][q] + grid[p-1][p-1])

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

Solution (Python):
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def cum_2d(field:list):
    row = len(field)
    col = len(field[0])
    
    
    for r in range(row):
        for c in range(col-1):
            field[r][c+1] += field[r][c]
    
    
    for c in range(col):
        for r in range(row-1):
            field[r+1][c] += field[r][c]
            
    return field

n,m,q = li()
grid = [[0 for _ in range(n+1)] for _ in range(n+1)]

for _ in range(m):
    l,r = li()
    grid[l][r] += 1
    
grid = cum_2d(grid)

for _ in range(q):
    p,q = li()
    print(grid[q][q] + grid[p-1][p-1] - grid[q][p-1] - grid[p-1][q])

Solution (Python):

from sys import stdin
import numpy as np

ds_in = lambda: list(map(int, stdin.readline().split()))  


N, M, Q = ds_in()

section = np.zeros((N, N), dtype=int)
for _ in range(M):
    p, q = ds_in()
    section[N-p, q-1] += 1

cumlist = np.cumsum(np.cumsum(section, axis=0), axis=1)

query = []
for _ in range(Q):
    query.append(ds_in())

for q in query:
    print(cumlist[N-q[0], q[1]-1])

Solution (Python):
import sys 
fin = sys.stdin.readline

N, M, Q = [int(elem) for elem in fin().split()]
trains = [[int(elem) - 1 for elem in fin().split()] for _ in range(M)]
queries = [[int(elem) - 1 for elem in fin().split()] for _ in range(Q)]

map_2D = [[0] * N for _ in range(N)]
for l, r in trains:
    map_2D[l][r] += 1

cuml_1D = [[0] * N for _ in range(N)]

for j in range(N):
    cuml_sum = 0
    for i in reversed(range(j + 1)):
        cuml_sum += map_2D[i][j]
        cuml_1D[i][j] = cuml_sum

cuml_2D = [[0] * N for _ in range(N)]

for i in range(N):
    cuml_sum = 0
    for j in range(N):
        cuml_sum += cuml_1D[i][j]
        cuml_2D[i][j] = cuml_sum

for p, q in queries:
    print(cuml_2D[p][q])

Solution (Python):
import sys 
fin = sys.stdin.readline

N, M, Q = [int(elem) for elem in fin().split()]
trains = [[int(elem) - 1 for elem in fin().split()] for _ in range(M)]
queries = [[int(elem) - 1 for elem in fin().split()] for _ in range(Q)]

map_2D = [[0] * N for _ in range(N)]
for l, r in trains:
    map_2D[l][r] += 1

cuml_1D = [[0] * N for _ in range(N)]

for j in range(N):
    cuml_sum = 0
    for i in reversed(range(j + 1)):
        cuml_sum += map_2D[i][j]
        cuml_1D[i][j] = cuml_sum

cuml_2D = [[0] * N for _ in range(N)]

for i in range(N):
    cuml_sum = 0
    for j in range(N):
        cuml_sum += cuml_1D[i][j]
        cuml_2D[i][j] = cuml_sum

for p, q in queries:
    print(cuml_2D[p][q])

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

imos = [[0 for i in range(n)] for j in range(n)]

for i in range(m):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    imos[l][r] += 1

for i in range(n):
    for j in range(n-1):
        imos[i][j+1] += imos[i][j]

for j in range(n):
    for i in range(n-1):
        imos[i+1][j] += imos[i][j]

for i in range(Q):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    if p == 0:
        print(imos[q][q])
    else:
        print(imos[q][q] - imos[p-1][q])

Solution (Python):
from itertools import accumulate

N,M,Q=map(int,input().split())

Station=[[0 for x in range(N+2)] for y in range(N+2)]

for i in range(M):
  s,t=map(int,input().split())
  Station[1][t]+=1
  Station[s+1][t]-=1
  Station[1][N+1]+=1
  Station[s+1][N+1]-=1

ST1 = [list(accumulate(l)) for l in zip(*Station)]
ST2 = [list(accumulate(l)) for l in zip(*ST1)]
  
for i in range(Q):
  l,r=map(int,input().split())
  print(ST2[l][r])

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

Solution (Python):
n,m,q=map(int,input().split())

mylist=[[0]*(n+1) for _ in range(n+1)]

for i in range(m):
    l,r=map(int,input().split())
    mylist[l][r]+=1

for i in range(1,n+1):
    for j in range(1,n+1):
        mylist[i][j]+=mylist[i][j-1]

memo=[[-1]*(n+1) for _ in range(n+1)]

for i in range(q):
    P,Q=map(int,input().split())
    if(memo[P][Q]!=-1):
        print(memo[P][Q])
        continue
    tmp=0
    for j in range(Q,P-1,-1):
        tmp+=mylist[j][Q]
        memo[j][Q]=tmp
    print(tmp)

Solution (Python):
N, M, Q = map(int, input().split())
X = []
for i in range(M):
    l, r = map(int, input().split())
    l, r = l - 1, r - 1
    X.append((l, r))


class Ruisekiwa2D:
    def __init__(self, h, w):
        self.H = h
        self.W = w
        self.G = [[0] * w for _ in range(h)]

    def load(self, points):
        
        for x, y in points:
            self.G[x][y] += 1

    def load_imos(self, points):
        
        for i1, j1, i2, j2 in points:
            self.G[i1][j1] += 1  
            if j2 + 1 < self.W:  
                self.G[i1][j2+1] -= 1
            if i2 + 1 < self.H:
                self.G[i2+1][j1] -= 1  
            if j2 + 1 < self.W and i2 + 1 < self.H:  
                self.G[i2+1][j2+1] += 1

    def calc(self):
        for y in range(self.W):
            for x in range(1, self.H):
                self.G[x][y] += self.G[x-1][y]

        for y in range(1, self.W):
            for x in range(self.H):
                self.G[x][y] += self.G[x][y-1]

    def get(self, i1, j1, i2, j2):
        if i1 > i2 or j1 > j2 or i1 < 0 or j1 < 0 or i2 < 0 or j2 < 0:
            return 0
        elif i1 > 0 and j1 > 0:
            return self.G[i2][j2] - self.G[i1-1][j2] - self.G[i2][j1-1] + self.G[i1-1][j1-1]
        elif i1 <= 0 < j1:
            return self.G[i2][j2] - self.G[i2][j1-1]
        elif j1 <= 0 < i1:
            return self.G[i2][j2] - self.G[i1 - 1][j2]
        else:
            return self.G[i2][j2]


R2D = Ruisekiwa2D(N, N)
R2D.load(X)
R2D.calc()

for q in range(Q):
    p, q = map(int, input().split())
    p, q = p - 1, q - 1
    print(R2D.get(p, p, q, q))

Solution (Python):
def m():
    n, M, Q = map(int, input().split())
    a = [[0 for _ in range(n+1)] for _ in range(n+1)]
    b = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    for i in range(M):
        l, r = map(int, input().split())
        a[l][r] += 1

    for i in range(1, n+1):
        b[1][i] += a[1][i] + b[1][i-1]
    for i in range(2, n+1):
        b[i][1] += a[i][1] + b[i-1][1]

    for i in range(1, n+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 i in range(Q):
        p, q = map(int, input().split())
        ans = b[q][q] + b[p-1][p-1] - b[q][p-1] - b[p-1][q]
        print(ans)

m()

Solution (Python):

from itertools import accumulate


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

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

for i in range(n-2, -1, -1):
    for j, acc in enumerate(accumulate(LR[i])):
        LR[i][j] = acc  + (0 if j == 0 else LR[i+1][j-1])

res = list()
for i in range(q):
    p,q = map(int, input().split())
    res.append(LR[p-1][q-p])

for r in res:
    print(r)

Solution (Python):
def inpl(): return [int(i) for i in input().split()]

N,M,Q = inpl()
LR = [inpl() for i in range(M)]
pq = [inpl() for i in range(Q)]

H = [[0]*N for i in range(N)]
S = [[0]*N for i in range(N)]

for i in range(M):
    H[LR[i][0]-1][LR[i][1]-1] += 1

S[0][0] = H[0][0]
for i in range(N):
    for j in range(N-1):
        S[i][j+1] = S[i][j] + H[i][j+1]

for i in range(N-1):
    for j in range(N):
        S[i+1][j] = S[i][j] + S[i+1][j]

for i in range(Q):
    if pq[i][1] == 1:
        print(S[0][0])
    elif pq[i][0] == 1:
        print(S[pq[i][1]-1][pq[i][1]-1])
    else:
        ans = S[pq[i][1]-1][pq[i][1]-1] - S[pq[i][1]-1][pq[i][0]-2] - S[pq[i][0]-2][pq[i][1]-1] + S[pq[i][0]-2][pq[i][0]-2]
        print(ans)

Solution (Python):
import itertools
import numpy as np

N,M,Q=list(map(int,input().split()))
trains=[[0 for _ in range(N)] for _ in range(N)]

for _ in range(M):
    L,R=list(map(int,input().split()))
    trains[N-L][R-1]+=1
trains=np.array(trains)
for i in range(N):
    trains[i]=np.array(list(itertools.accumulate(trains[i])))
for i in range(N):
    trains[:,i]=np.array(list(itertools.accumulate(trains[:,i])))

for _ in range(Q):
    p,q=list(map(int,input().split()))
    print(trains[N-p,q-1])

Solution (Python):
N, M, Q = map(int, input().split())


class Ruisekiwa2D:
    def __init__(self, h, w):
        self.H = h
        self.W = w
        self.G = [[0] * w for _ in range(h)]

    def load(self, points):
        
        
        for x, y in points:
            self.G[x][y] += 1

        self.calc()

    def load_imos(self, points):
        
        for i1, j1, i2, j2 in points:
            self.G[i1][j1] += 1  
            if j2 + 1 < self.W:  
                self.G[i1][j2+1] -= 1
            if i2 + 1 < self.H:
                self.G[i2+1][j1] -= 1  
            if j2 + 1 < self.W and i2 + 1 < self.H:  
                self.G[i2+1][j2+1] += 1

        self.calc()

    def calc(self):
        for y in range(self.W):
            for x in range(1, self.H):
                self.G[x][y] += self.G[x-1][y]

        for y in range(1, self.W):
            for x in range(self.H):
                self.G[x][y] += self.G[x][y-1]

    def get(self, i1, j1, i2, j2):
        if i1 > i2 or j1 > j2 or i1 < 0 or j1 < 0 or i2 < 0 or j2 < 0:
            return 0
        elif i1 > 0 and j1 > 0:
            return self.G[i2][j2] - self.G[i1-1][j2] - self.G[i2][j1-1] + self.G[i1-1][j1-1]
        elif i1 <= 0 < j1:
            return self.G[i2][j2] - self.G[i2][j1-1]
        elif j1 <= 0 < i1:
            return self.G[i2][j2] - self.G[i1 - 1][j2]
        else:
            return self.G[i2][j2]


R2D = Ruisekiwa2D(N, N)
I = []
for i in range(M):
    l, r = map(int, input().split())
    l, r = l -1, r- 1
    I.append((l, r))
R2D.load(I)

for i in range(Q):
    p, q = map(lambda x: int(x) - 1, input().split())
    print(R2D.get(p, p, q, q))

Solution (Python):
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])

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def cum_2d(field:list):
    row = len(field)
    col = len(field[0])
    
    
    for r in range(row):
        for c in range(col-1):
            field[r][c+1] += field[r][c]
    
    
    for c in range(col):
        for r in range(row-1):
            field[r+1][c] += field[r][c]
            
    return field
            

n,m,q = li()
train = []
query = []

field = [[0 for _ in range(n+1)] for _ in range(n+1)]

for _ in range(m):
    train.append(tuple(li()))
    
for _ in range(q):
    query.append(tuple(li()))
    
for ts, tt in train:
    field[ts][tt] += 1
    
field = cum_2d(field)
        
for qs,qt in query:
    print(field[qt][qt] - field[qt][qs-1] - field[qs-1][qt] + field[qs-1][qs-1])

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,m,q = li()
train = []
query = []

field = [[0 for _ in range(n+1)] for _ in range(n+1)]

for _ in range(m):
    train.append(tuple(li()))
    
for _ in range(q):
    query.append(tuple(li()))
    
for ts, tt in train:
    field[ts][tt] += 1
    
for r in range(n+1):
    for c in range(n):
        field[r][c+1] += field[r][c]
        
for c in range(n+1):
    for r in range(n):
        field[r+1][c] += field[r][c]
        
for qs,qt in query:
    print(field[qt][qt] - field[qt][qs-1] - field[qs-1][qt] + field[qs-1][qs-1])

Solution (Python):

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 i in range(n,0,-1):
    for j in range(n):
        d[i][j+1] += d[i][j]
for j in range(n,0,-1):
    for i in range(n,0,-1):
        d[i-1][j] += d[i][j]

pq = []
for _ in range(q):
    p,q = map(int, input().split())
    pq.append([p,q])


for o in pq:
    print(d[o[0]][o[1]])

Solution (Python):




N, M, Q = [int(_) for _ in input().split()]
listN = [[0] * (N+1) for i in range(N+1)]
listNsum = [[0] * (N+1) for i in range(N+1)]

for i in range(M):
	L, R = [int(_) for _ in input().split()]
	listN[L][R] += 1


for iIdx, iList in enumerate(listN):
	for jIdx, jList in enumerate(iList):
		if jIdx == 0:
			listNsum[iIdx][jIdx] = listN[iIdx][jIdx]
		else:
			listNsum[iIdx][jIdx] = listNsum[iIdx][jIdx-1] + listN[iIdx][jIdx]


retList = []
for i in range(Q):
	p, q = [int(_) for _ in input().split()]
	sumv = 0
	for j in range(p, q+1):
		sumv += listNsum[j][q] - listNsum[j][p-1]
	retList.append(sumv)

for i in retList:
	print(i)

Solution (Python):
N, M, Q = map(int, input().split())

T = [[0 for _ in range(N + 1)] for _ in range(N + 1)]

for _ 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] += T[L][R - 1]
        T[L][R] -= T[L - 1][R - 1]

for _ in range(Q):
    P, Q = map(int, input().split())
    ans = 0
    ans += T[Q][Q]
    ans -= T[P - 1][Q]
    ans -= T[Q][P - 1]
    ans += T[P - 1][P - 1]
    print(ans)

Solution (Python):
N, M, Q = [int(_) for _ in input().split()]

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

cumsum = [[0] * (N + 1) for i in range(N + 1)]
for i in range(1, N + 1):
    for j in range(1, N + 1):
        cumsum[i][j] = train_map[i][j] + cumsum[i][j - 1] + cumsum[i - 1][j] - cumsum[i - 1][j - 1]

for _ in range(Q):
    p, q = [int(_) for _ in input().split()]
    print(cumsum[q][q] - cumsum[p-1][q])

Solution (Python):
N, M, Q = [int(_) for _ in input().split()]
T = [[int(_) for _ in input().split()] for i in range(M)]
Q = [[int(_) for _ in input().split()] for i in range(Q)]

train_map = [[0] * (N + 1) for i in range(N + 1)]
for l, r in T:
    train_map[l][r] += 1

cumsum = [[0] * (N + 1) for i in range(N + 1)]
for i in range(1, N + 1):
    for j in range(1, N + 1):
        cumsum[i][j] = train_map[i][j] + cumsum[i][j - 1] + cumsum[i - 1][j] - cumsum[i - 1][j - 1]


for p, q in Q:
    print(cumsum[q][q] - cumsum[p-1][q])

Solution (Python):
N, M, Q = map(int, input().split())
rec = [[0] * N for i in range(N)]
for i in range(M):
    l, r = map(int, input().split())
    rec[l - 1][r - 1] += 1

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

for j in range(N):
    for i in range(N - 2, -1, -1):
        rec[i][j] += rec[i + 1][j]

for i in range(Q):
    p, q = map(int, input().split())
    print(rec[p - 1][q - 1])

Solution (Python):
n, m, q = map(int, input().split())
cities = [[0 for _ in range(n+1)] for _ in range(n+2)]
trains = [list(map(int, input().split())) for _ in range(m)]
quests = [list(map(int, input().split())) for _ in range(q)]

for train in trains:
    x, y = train[0], train[1]
    cities[x][y] += 1

for i in range(n):
    for j in range(1, n-i+1):
        x = j + i
        cities[j][x] += cities[j][x-1] + cities[j+1][x] - cities[j+1][x-1]

for quest in quests:
    p, q = quest[0], quest[1]
    print(cities[p][q])

Solution (Python):
N, M, Q = map(int, input().split())

im = [[0] * (N + 2) for _ in range(N + 2)]
for _ in range(M):
    l, r = map(int, input().split())
    im[1  ][r  ] += 1
    im[l+1][r  ] -= 1
    im[1  ][N+1] -= 1
    im[l+1][N+1] += 1

for i in range(1, N+1):
    for j in range(1, N+1):
        im[i][j+1] += im[i][j]
for j in range(1, N+1):
    for i in range(1, N+1):
        im[i+1][j] += im[i][j]
for _ in range(Q):
    p, q = map(int, input().split())
    print(im[p][q])

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

Solution (Python):
from bisect import bisect_left

def main():
	n, m, q = list(map(int, input().split()))
	trains = [list(map(int, input().split())) for _ in range(m)]
	queries = [list(map(int, input().split())) for _ in range(q)]
	
	xmt = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
	cmt = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
	
	for train in trains:
		xmt[train[0]][train[1]] += 1

	for i in range(1, n + 1):
		for j in range(1, n + 1):
			cmt[i][j] = cmt[i][j - 1] + (cmt[i - 1][j] - cmt[i - 1][j - 1]) + xmt[i][j] 
	
	for query in queries:
		i, j = query
		ans = cmt[j][j] - cmt[i - 1][j] - cmt[j][i - 1] + cmt[i - 1][i - 1]
		print(ans)

if __name__ == '__main__':
	main()

Solution (Python):
n, m, q = map(int, input().split())

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

for	i in range(n-2, -1, -1):
    for	j in range(i+1):
        ans[i - j][j] += ans[i - j + 1][j] + ans[i - j][j + 1] - ans[i - j + 1][j + 1]

tmp = []
for i in range(q):
    p, q = map(int, input().split())
    tmp.append((p, q))

for p, q in tmp:
    print(ans[n-q][p-1])

Solution (Python):
def ary(r, c, val=False): return [[val for _ in range(c)] for _ in range(r)]
def nl(): return list(map(int, input().split()))

n, m, q = nl()
M = ary(n + 1, n + 1, 0)
for _ in range(m):
    l, r = nl()
    M[l][r] += 1

for L in range(1, n + 1):
    for R in range(1, n + 1):
        M[L][R] += M[L - 1][R]
        M[L][R] += M[L][R - 1]
        M[L][R] -= M[L - 1][R - 1]

for _ in range(q):
    p, q = map(int, input().split())
    ans = M[q][q] - M[p - 1][q] - M[q][p - 1] + M[p - 1][p - 1]
    print(ans)

Solution (Python):
from itertools import accumulate as acc
f = lambda: map(int,input().split())
n,m,q = f()
d = [[0 for _ in range(n)]for _ in range(n)]
for _ in range(m):
    l,r = f()
    d[l-1][r-1] += 1
P,Q = [],[]
for _ in range(q):
    a, b = f()
    P.append(a)
    Q.append(b)

for i in range(n):
    d[i] = list(acc(d[i]))
for i in range(n-2,-1,-1):
    for j in range(n):
        d[i][j] += d[i+1][j]
for i in range(q):
    print(d[P[i]-1][Q[i]-1])

Solution (Python):
f = lambda: map(int,input().split())
n,m,q = f()
d = [[0 for _ in range(n)]for _ in range(n)]
for _ in range(m):
    l,r = f()
    d[l-1][r-1] += 1
P,Q = [],[]
for _ in range(q):
    a, b = f()
    P.append(a)
    Q.append(b)

for i in range(n):
    for j in range(1,n):
        d[i][j] += d[i][j-1]
for i in range(n-2,-1,-1):
    for j in range(n):
        d[i][j] += d[i+1][j]
for i in range(q):
    print(d[P[i]-1][Q[i]-1])