Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given $N$ points (numbered $1$ through $N$) in a Cartesian coordinate system. For each valid $i$, the coordinates of the $i$-th point are $(x_{i}, y_{i})$.

You should answer $Q$ queries (numbered $1$ through $Q$). For each valid $i$, in the $i$-th query:
You are given two points $L = (l_{i}, 0)$ and $R = (r_{i}, 0)$.
Consider an isosceles right triangle such that its hypothenuse is the line segment between the points $L$ and $R$ (two of its vertices) and the vertex opposite to it lies above the $x$-axis.
The answer to this query is the number of points among the given $N$ points which lie inside or on the perimeter of this triangle.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $Q$.
$N$ lines follow. For each valid $i$, the $i$-th of these lines contains two space-separated integers $x_{i}$ and $y_{i}$.
$Q$ more lines follow. For each valid $i$, the $i$-th of these lines contains two space-separated integers $l_{i}$ and $r_{i}$.

------  Ouput ------
For each test case, print a single line containing $Q$ space separated integers. For each valid $i$, the $i$-th of these integers should be the answer to the $i$-th query.

------  Constraints ------
$1 ≤ T ≤ 100$
$1 ≤ N, Q ≤ 10^{6}$
$0 ≤ x_{i}, y_{i} ≤ 10^{6}$ for each valid $i$
$0 ≤ l_{i} < r_{i} ≤ 10^{6}$ for each valid $i$
the sum of $N$ over all test cases does not exceed $10^{6}$
the sum of $Q$ over all test cases does not exceed $10^{6}$

------  Subtasks ------
Subtask #1 (50 points):
$N ≤ 10^{5}$
$r_{1}-l_{1} = r_{2}-l_{2} = \ldots = r_{N}-l_{N}$
the sum of $N$ over all test cases does not exceed $10^{5}$
the sum of $Q$ over all test cases does not exceed $10^{5}$

Subtask #2 (50 points): original constraints

----- Sample Input 1 ------ 
1

6 3

1 2

14 7

6 3

8 7

11 10

14 2

0 10

2 22

11 17
----- Sample Output 1 ------ 
1 3 1
----- explanation 1 ------ 
Example case 1:

Source: codechef | Difficulty: VERY_HARD
Tags: Geometry

Range queries

Segment trees revisited

Mathematics

Data structures


Solutions:
from sys import stdin
from sys import stdout

class BITree:
	nodes = []
	n = 0

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

	def add(self, idx, val):
		idx += 1
		while idx < self.n:
			self.nodes[idx] += val
			idx += idx & -idx

	def sum(self, idx):
		r = 0
		idx += 1
		while idx > 0:
			r += self.nodes[idx]
			idx -= idx & -idx
		return r
T = int(input())
for t in range(0, T):
	tree = BITree(2000000)
	(n, q) = map(lambda x: int(x), input().split(' '))
	points = []
	for i in range(0, n):
		xy = input().split(' ')
		x = int(xy[0])
		y = int(xy[1])
		points.append((y - x, x + y))
	points.sort(key=lambda p: p[0])
	queries = []
	for i in range(0, q):
		lr = input().split(' ')
		l = int(lr[0])
		r = int(lr[1])
		queries.append((-l, r, i))
	queries.sort(key=lambda p: p[0])
	solution = [0] * q
	idx = 0
	for i in range(0, q):
		li = queries[i][0]
		ri = queries[i][1]
		query_idx = queries[i][2]
		while idx < n and points[idx][0] <= li:
			tree.add(points[idx][1], 1)
			idx += 1
		solution[query_idx] = str(tree.sum(ri))
	print(' '.join(solution))