Read problems statements [Hindi] ,[Bengali] , [Mandarin chinese] , [Russian] and [Vietnamese] as well.

There are $N$ circles in a plane. Circle $i$ and circle $j$ form a *good pair* if it is possible to choose a point $P_{1}$ on the perimeter of circle $i$ and a point $P_{2}$ on the perimeter of circle $j$ such that the Euclidean distance between $P_{1}$ and $P_{2}$ is exactly $K$. (Note that $P_{1}$ and $P_{2}$ do not need to have integer coordinates.)

You should answer $Q$ queries. In each query, you are given the required distance $K$. Chef is interested in finding the number of good pairs of distinct circles for each query. Please help him.

Note: Circle $i$ and circle $j$ are distinct when $i \neq j$. There may be any number of circles that coincide (have identical centers and radii).

------  Input ------
The first line of the input contains two space-separated integers $N$ and $Q$ denoting the number of circles and the number of queries respectively.
Each of the following $N$ lines contains three space-separated integers $X$, $Y$ and $R$ describing a circle with radius $R$ and center $(X, Y)$.
Each of the next $Q$ lines contains one integer $K$ describing a query.
 
------  Output ------
For each query, print a single line containing one integer — the number of good pairs of circles.
 
------  Constraints ------
$2 ≤ N ≤ 10^{3}$
$1 ≤ Q ≤ 5\cdot 10^{5}$
$X, Y ≤ |2\cdot 10^{5}|$
$1 ≤ R ≤ 2\cdot 10^{5}$
$0 ≤ K ≤ 10^{6}$
 
------  Subtasks ------
Subtask #1 (30 points):
$2 ≤ N ≤ 10^{2}$
$1 ≤ Q ≤ 5\cdot 10^{2}$

Subtask #2 (70 points): original constraints

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

0 0 5

8 3 2

0

10

20
----- Sample Output 1 ------ 
0

1

0
----- explanation 1 ------ 
The distance between the point $(0.00, -5.00)$ on circle $1$ and the point $(8.00, 1.00)$ on circle $2$ is $10$. There is no pair of points on these two circles with distance $0$ or $20$.

Source: codechef | Difficulty: HARD
Tags: Geometry

Range queries

Mathematics


Solutions:
import math

def dist(x1, x2, y1, y2):
	return math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)

def calculate(c1, c2, l):
	radsum = c1[2] + c2[2]
	distc = dist(c1[0], c2[0], c1[1], c2[1])
	maxrad = max(c1[2], c2[2])
	minrad = min(c1[2], c2[2])
	if distc > radsum:
		mindist = distc - radsum
		maxdist = distc + radsum
	elif distc < maxrad - minrad:
		mindist = maxrad - minrad - distc
		maxdist = 2 * maxrad - mindist
	else:
		mindist = 0
		maxdist = radsum + distc
	return [mindist, maxdist]
(n, q) = [int(i) for i in input().split()]
circles = []
query = []
for j in range(n):
	circles.append([int(i) for i in input().split()])
for i in range(q):
	query.append(int(input()))
l = [0] * 1000001
for i in range(len(circles)):
	for j in range(i + 1, len(circles)):
		x = calculate(circles[i], circles[j], l)
		l[math.ceil(x[0])] += 1
		l[math.floor(x[1]) + 1] -= 1
for i in range(1, len(l)):
	l[i] = l[i] + l[i - 1]
for i in query:
	print(l[i])


import math
cx = []
cy = []
cr = []
freq = [0] * 1000001
(n, q) = map(int, input().split(' '))
for _ in range(n):
	(x, y, r) = map(float, input().split(' '))
	cx.append(x)
	cy.append(y)
	cr.append(r)
qs = []
for _ in range(q):
	qs.append(int(input()))
for i in range(n - 1):
	for j in range(i + 1, n):
		x = cx[i] - cx[j]
		y = cy[i] - cy[j]
		d = math.sqrt(x * x + y * y)
		r1 = cr[i]
		r2 = cr[j]
		if d <= r1 + r2:
			if math.fabs(r1 - r2) <= d:
				kMin = 0
			else:
				kMin = math.ceil(math.fabs(r1 - r2) - d)
		else:
			kMin = math.ceil(d - r1 - r2)
		kMAx = math.floor(d + r1 + r2) + 1
		if kMin <= 1000000:
			freq[int(kMin)] += 1
		if kMAx <= 1000000:
			freq[int(kMAx)] -= 1
for i in range(1, 1000001):
	freq[i] += freq[i - 1]
for i in range(q):
	print(freq[qs[i]])


def add(arr, N, lo, hi, val):
	arr[lo] += val
	if hi != N - 1:
		arr[hi + 1] -= val

def updateArray(arr, N):
	for i in range(1, N):
		arr[i] += arr[i - 1]
	return arr
N = 1000001
car = [0 for x in range(0, 1000001)]
import math
(l, u) = ([], [])
(n, q) = [int(x) for x in input().split()]
c = []
for i in range(n):
	c.append([int(x) for x in input().split()])
for x in range(n):
	for y in range(x + 1, n):
		a = c[x]
		b = c[y]
		r1 = a[2]
		r2 = b[2]
		z = math.sqrt(math.pow(a[0] - b[0], 2) + math.pow(a[1] - b[1], 2))
		if a != b:
			if z < r1 + r2 and z <= abs(r1 - r2):
				add(car, N, max(math.ceil(max(r1, r2) - z - min(r1, r2)), 0), math.floor(r1 + r2 + z), 1)
			else:
				add(car, N, max(0, math.ceil(z - r1 - r2)), math.floor(z + r1 + r2), 1)
car = updateArray(car, N)
for i in range(q):
	k = int(input())
	print(car[k])


import math

def distance(x1, y1, x2, y2):
	return math.sqrt(math.pow(x1 - y1, 2) + math.pow(x2 - y2, 2) * 1.0)
(n, q) = map(int, input().split())
a = []
b = []
for i in range(0, n):
	x = list(map(int, input().split()))
	a.append(x)
for j in range(0, q):
	k = int(input())
	b.append(k)
index = [0] * 1000002
for i in range(0, n - 1):
	for j in range(i + 1, n):
		d = distance(a[i][0], a[j][0], a[i][1], a[j][1])
		if d >= a[i][2] + a[j][2]:
			mi = math.ceil(d - a[i][2] - a[j][2])
			ma = math.floor(d + a[i][2] + a[j][2])
		elif d < a[i][2] + a[j][2] and d >= abs(a[i][2] - a[j][2]):
			mi = 0
			ma = math.floor(d + a[i][2] + a[j][2])
		elif d < a[i][2] + a[j][2]:
			if a[i][2] > a[j][2]:
				mi = math.ceil(a[i][2] - d - a[j][2])
				ma = math.floor(d + a[i][2] + a[j][2])
			else:
				mi = math.ceil(a[j][2] - d - a[i][2])
				ma = math.floor(d + a[i][2] + a[j][2])
		index[mi] += 1
		index[ma + 1] += -1
for i in range(1, 1000002):
	index[i] += index[i - 1]
for k in range(0, q):
	print(index[b[k]])


import math
(n, m) = map(int, input().split())
arr = []
ans = [0 for x in range(10 ** 6)]
for i in range(n):
	arr.append([int(x) for x in input().split()])
for i in range(n):
	for j in range(i + 1, n):
		dist = math.sqrt(pow(arr[i][0] - arr[j][0], 2) + pow(arr[i][1] - arr[j][1], 2))
		rmax = max(arr[i][2], arr[j][2])
		rmin = min(arr[i][2], arr[j][2])
		if rmax - rmin > dist:
			minarr = rmax - rmin - dist
			maxarr = rmax + rmin + dist
		elif rmax + rmin > dist:
			minarr = 0
			maxarr = rmax + rmin + dist
		else:
			minarr = dist - rmax - rmin
			maxarr = dist + rmax + rmin
		ans[math.ceil(minarr)] += 1
		ans[math.floor(maxarr) + 1] -= 1
for i in range(1, 10 ** 6):
	ans[i] += ans[i - 1]
for i in range(m):
	k = int(input())
	print(ans[k])


import math
import collections
import random
import time
import os

def getInput():
	(N, M) = map(int, input().split())
	A = []
	for i in range(N):
		(x, y, r) = map(int, input().split())
		A.append((x, y, r))
	qs = []
	for i in range(M):
		qs.append(int(input()))
	return (N, A, qs)

def distance(circlea, circleb):
	(x1, y1, r1) = circlea
	(x2, y2, r2) = circleb
	d = math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
	mxd = d + r1 + r2
	(mnr, mxr) = (min(r1, r2), max(r1, r2))
	mnd = max(0, d - r1 - r2, mxr - d - mnr)
	return (mnd, mxd)

def preprocess(N, circles):
	starts = collections.defaultdict(int)
	ends = collections.defaultdict(int)
	for i in range(N):
		for j in range(i + 1, N):
			(a, b) = distance(circles[i], circles[j])
			starts[a] += 1
			ends[b] += 1
	return (starts, ends)

def query(queries, starts, ends):
	points = [(p, 0, 0) for p in starts.keys()]
	points += [(p, 2, 0) for p in ends.keys()]
	points += [(p, 1, i) for (i, p) in enumerate(queries)]
	ans = [0 for _ in range(len(queries))]
	counts = 0
	for (p, a, pi) in sorted(points):
		if a == 1:
			ans[pi] = counts
		else:
			counts += starts[p] - ends[p]
	return ans

def solve(N, circles, queries):
	(starts, ends) = preprocess(N, circles)
	ans = query(queries, starts, ends)
	print('\n'.join(map(str, ans)))

def genInput():
	N = 1000
	A = [(random.randint(-1000, 1000), random.randint(-1000, 1000), random.randint(1, 300)) for _ in range(N)]
	qs = [random.randint(0, 1000) for _ in range(5 * 10 ** 5)]
	return (N, A, qs)

def test():
	(N, a, qs) = genInput()
	t0 = time.time()
	solve(N, a, qs)
	print(time.time() - t0)
(N, A, qs) = getInput()
solve(N, A, qs)


import math
(t, k) = map(int, input().split())
c = []
res = [0 for x in range(10 ** 6 + 5)]
l = r = 0
for x in range(t):
	c.append(list(map(int, input().split())))
for i in range(t):
	for j in range(i):
		dx = c[i][0] - c[j][0]
		dy = c[i][1] - c[j][1]
		dc = math.sqrt(dx ** 2 + dy ** 2)
		(r, R) = (min(c[i][2], c[j][2]), max(c[i][2], c[j][2]))
		if R > dc + r:
			l = R - dc - r
		else:
			l = dc - r - R
		ll = math.ceil(max(0, l))
		ul = math.floor(dc + r + R)
		res[ll] += 1
		res[ul + 1] -= 1
for i in range(1, 10 ** 6):
	res[i] += res[i - 1]
for x in range(k):
	print(res[int(input())])


def endtime(tup):
	return tup[1]
(N, Q) = map(int, input().split())
arr = []
for i in range(N):
	(X, Y, R) = map(int, input().split())
	arr.append((X, Y, R))
main = []
for i in range(N):
	for j in range(i + 1, N):
		c1x = arr[i][0]
		c1y = arr[i][1]
		r1 = arr[i][2]
		c2x = arr[j][0]
		c2y = arr[j][1]
		r2 = arr[j][2]
		c1c2 = pow((c1x - c2x) * (c1x - c2x) + (c1y - c2y) * (c1y - c2y), 0.5)
		if c1c2 >= r1 + r2:
			minimum = c1c2 - r1 - r2
			maximum = c1c2 + r1 + r2
			main.append((minimum, maximum))
		elif c1x == c2x and c1y == c2y:
			minimum = abs(r2 - r1)
			maximum = r1 + r2
			main.append((minimum, maximum))
		else:
			maximum = c1c2 + r1 + r2
			if c1c2 >= abs(r2 - r1):
				minimum = 0
			else:
				minimum = abs(r2 - r1) - c1c2
			main.append((minimum, maximum))
main.sort(key=endtime, reverse=True)
from math import ceil
K = pow(10, 6)
arr = [0] * (K + 1)
for i in main:
	s = ceil(i[0])
	e = int(i[1])
	if e > K:
		e = K
	arr[s] += 1
	arr[e + 1] += -1
sum = 0
for i in range(K + 1):
	sum += arr[i]
	arr[i] = sum
for i in range(Q):
	x = int(input())
	print(arr[x])


from math import hypot, ceil, floor

def function(A, B):
	dist = hypot(B[0] - A[0], B[1] - A[1])
	if dist >= A[2] + B[2]:
		a_min = dist - A[2] - B[2]
		a_max = dist + A[2] + B[2]
	elif dist == abs(A[2] - B[2]):
		a_min = 0
		a_max = 2 * max(A[2], B[2])
	elif dist < abs(A[2] - B[2]):
		a_min = max(A[2], B[2]) - min(A[2], B[2]) - dist
		a_max = A[2] + B[2] + dist
	elif abs(A[2] - B[2]) < dist < A[2] + B[2]:
		a_min = 0
		a_max = A[2] + B[2] + dist
	return [ceil(a_min), floor(a_max)]
(N, Q) = map(int, input().split())
data = []
for i in range(N):
	(x, y, r) = map(int, input().split())
	data.append([x, y, r])
final_data = [0] * 10000003
c = 0
for i in range(N - 1):
	for j in range(i + 1, N):
		(a, b) = function(data[i], data[j])
		c = max(b, c)
		final_data[a] += 1
		final_data[b + 1] -= 1
for i in range(1, c + 3):
	final_data[i] += final_data[i - 1]
for q in range(Q):
	print(final_data[int(input())])


import math
(n, q) = map(int, input().split(' '))
cx = []
cy = []
cr = []
for _ in range(n):
	(x, y, r) = map(int, input().split(' '))
	cx.append(x)
	cy.append(y)
	cr.append(r)
qs = []
for _ in range(q):
	qs.append(int(input()))
k = [0] * 1000002
for i in range(n - 1):
	for j in range(i + 1, n):
		dx = cx[i] - cx[j]
		dy = cy[i] - cy[j]
		cc = math.sqrt(dx * dx + dy * dy)
		d_min = d_max = 0.0
		if cc >= cr[i] + cr[j]:
			d_min = cc - cr[i] - cr[j]
			d_max = cc + cr[i] + cr[j]
		elif cc == abs(cr[i] - cr[j]):
			d_min = 0
			d_max = max(2 * cr[i], 2 * cr[j])
		elif cc < abs(cr[i] - cr[j]):
			d_min = max(cr[i], cr[j]) - cc - min(cr[i], cr[j])
			d_max = cr[i] + cc + cr[j]
		else:
			d_min = 0
			d_max = cr[i] + cr[j] + cc
		d_ceil = int(math.ceil(d_min))
		d_floor = int(math.floor(d_max))
		k[d_ceil] += 1
		k[d_floor + 1] -= 1
for i in range(1, len(k)):
	k[i] += k[i - 1]
for i in range(q):
	print(k[qs[i]])


import math

class Circle:

	def __init__(self, x, y, r):
		self.x = x
		self.y = y
		self.r = r
c = []
freq = [0] * 1000001
(n, q) = map(int, input().split(' '))
for _ in range(n):
	(x, y, r) = map(float, input().split(' '))
	c.append(Circle(x, y, r))
qs = []
for _ in range(q):
	qs.append(int(input()))
for i in range(n - 1):
	for j in range(i + 1, n):
		x = c[i].x - c[j].x
		y = c[i].y - c[j].y
		d = math.sqrt(x * x + y * y)
		r1 = c[i].r
		r2 = c[j].r
		if d <= r1 + r2:
			if math.fabs(r1 - r2) <= d:
				kMin = 0
			else:
				kMin = math.ceil(math.fabs(r1 - r2) - d)
		else:
			kMin = math.ceil(d - r1 - r2)
		kMAx = math.floor(d + r1 + r2) + 1
		if kMin <= 1000000:
			freq[int(kMin)] += 1
		if kMAx <= 1000000:
			freq[int(kMAx)] -= 1
for i in range(1, 1000001):
	freq[i] += freq[i - 1]
for i in range(q):
	print(freq[qs[i]])


import math
from bisect import bisect_left
(n, Q) = map(int, input().split())
circle = []
for i in range(n):
	(x, y, r) = map(int, input().split())
	circle.append([x, y, r])

def distance(c1, c2):
	(x1, y1, r1) = (c1[0], c1[1], c1[2])
	(x2, y2, r2) = (c2[0], c2[1], c2[2])
	d = math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2))
	if d > r1 + r2:
		return (d - r1 - r2, d + r1 + r2)
	elif d == r1 + r2:
		return (0, r1 + r1 + r2 + r2)
	elif abs(r1 - r2) < d < r1 + r2:
		return (0, r1 + d + r2)
	elif d == abs(r1 - r2):
		return (0, 2 * max(r1, r2))
	else:
		return (max(r1, r2) - d - min(r1, r2), r1 + d + r2)
rng = [0] * 10 ** 6
for c1 in range(n):
	for c2 in range(c1, n):
		if c1 != c2:
			(minm, maxm) = distance(circle[c1], circle[c2])
			maxm = int(maxm)
			if int(minm) - minm == 0:
				minm = int(minm)
			else:
				minm = int(minm) + 1
			rng[minm] += 1
			rng[maxm + 1] -= 1

def add_one_by_one(L):
	new_L = list(L)
	for i in range(1, len(new_L)):
		new_L[i] += new_L[i - 1]
	return new_L
rng = add_one_by_one(rng)
for q in range(Q):
	k = int(input())
	print(rng[k])


import math
(n, q) = map(int, input().split())
cen = []
r = []
k = []
vmin = []
vmax = []
index = [0] * 1000000
for i in range(n):
	(x, y, rad) = map(int, input().split())
	cen.append([x, y])
	r.append(rad)
for i in range(q):
	k.append(int(input()))
for i in range(0, n - 1):
	for j in range(i + 1, n):
		cc = math.sqrt(pow(cen[i][0] - cen[j][0], 2) + pow(cen[i][1] - cen[j][1], 2))
		if cc >= r[i] + r[j]:
			vmin = cc - r[i] - r[j]
			vmax = cc + r[i] + r[j]
		elif cc == abs(r[i] - r[j]):
			vmin = 0
			vmax = max(2 * r[i], 2 * r[j])
		elif cc < abs(r[i] - r[j]):
			vmin = max(r[i], r[j]) - cc - min(r[i], r[j])
			vmax = min(r[i], r[j]) + cc + max(r[i], r[j])
		else:
			vmin = 0
			vmax = r[i] + r[j] + cc
		index[math.ceil(vmin)] += 1
		index[math.floor(vmax) + 1] -= 1
for i in range(1, 1000000):
	index[i] += index[i - 1]
for i in range(q):
	print(index[k[i]])


import math

def swap(t1, t2):
	return (t2, t1)

def cal_Range(a, b):
	r1 = a[2]
	r2 = b[2]
	d = math.sqrt(pow(a[0] - b[0], 2) + pow(a[1] - b[1], 2))
	rang = []
	if d > r1 and d > r2:
		pass
	elif r1 > d and r1 > r2:
		(d, r1) = swap(d, r1)
	elif r2 > r1 and r2 > d:
		(d, r2) = swap(d, r2)
	rang.append(math.ceil(max(d - (r1 + r2), 0)))
	rang.append(math.floor(d + r1 + r2))
	return rang
(n, q) = map(int, input().split(' '))
circles = []
for _ in range(n):
	dim = list(map(int, input().split(' ')))
	circles.append(dim)
distances = []
no_rep = 0
max_dis = 0
for i in range(n):
	temp = []
	for j in range(n):
		if i != j and no_rep < j:
			temp.append(cal_Range(circles[i], circles[j]))
			max_dis = max(temp[j][0], temp[j][1], max_dis)
		else:
			temp.append([-1, -1])
	no_rep = no_rep + 1
	distances.append(temp)
ranges_list = [0] * (max_dis + 2)
for i in range(n):
	for j in range(n):
		if distances[i][j][0] != -1:
			ranges_list[distances[i][j][0]] += 1
			ranges_list[distances[i][j][1] + 1] -= 1
counter = 0
c_Arr = []
for i in range(len(ranges_list)):
	counter += ranges_list[i]
	c_Arr.append(counter)
for _ in range(q):
	length = int(input())
	try:
		ans = c_Arr[length]
		print(ans)
	except:
		print(0)


import math
from collections import Counter

def getRange(x1, y1, r1, x2, y2, r2):
	distCenters = math.sqrt(math.pow(x1 - x2, 2) + math.pow(y1 - y2, 2))
	if distCenters >= r1 + r2:
		return (math.ceil(distCenters - r1 - r2), int(distCenters + r1 + r2))
	elif abs(r1 - r2) <= distCenters:
		return (0, int(distCenters + r1 + r2))
	else:
		return (math.ceil(abs(r1 - r2) - distCenters), int(distCenters + r1 + r2))
(n, q) = map(int, input().strip().split())
circles = [0] * n
for i in range(n):
	circles[i] = tuple(map(int, input().strip().split()))
adders = list()
subs = list()
cunt = Counter()
for i in range(n):
	for j in range(i + 1, n):
		t = getRange(circles[i][0], circles[i][1], circles[i][2], circles[j][0], circles[j][1], circles[j][2])
		adders.append(t[0])
		subs.append(t[1])
adi = 1
subi = 0
adders = sorted(adders)
subs = sorted(subs)
last = adders[0]
cunt[last] = 1
val = 1
while adi < len(adders):
	if adders[adi] > subs[subi]:
		for i in range(last + 1, subs[subi] + 1):
			cunt[i] = val
		val -= 1
		last = subs[subi]
		subi += 1
	else:
		for i in range(last + 1, adders[adi]):
			cunt[i] = val
		val += 1
		cunt[adders[adi]] = val
		last = adders[adi]
		adi += 1
while subi < len(subs):
	for i in range(last + 1, subs[subi] + 1):
		cunt[i] = val
	val -= 1
	last = subs[subi]
	subi += 1
for j in range(q):
	k = int(input())
	print(cunt[k])


import math
l = [int(s) for s in input().split()]
g = []
for i in range(l[0]):
	a = [int(s) for s in input().split()]
	g.append(a)
h = []
maxi = -1000
for i in range(len(g)):
	for j in range(i + 1, len(g)):
		DistBtwCenters = math.sqrt((g[i][0] - g[j][0]) ** 2 + (g[i][1] - g[j][1]) ** 2)
		gd = DistBtwCenters + g[i][2] + g[j][2]
		sd = -1000
		if g[i][2] >= DistBtwCenters + g[j][2]:
			sd = g[i][2] - (DistBtwCenters + g[j][2])
		elif g[j][2] >= DistBtwCenters + g[i][2]:
			sd = g[j][2] - (DistBtwCenters + g[i][2])
		elif DistBtwCenters > g[i][2] + g[j][2]:
			sd = DistBtwCenters - (g[i][2] + g[j][2])
		elif DistBtwCenters <= g[i][2] + g[j][2]:
			sd = 0
		(sd_m, gd_m) = (math.ceil(sd), math.floor(gd))
		if gd_m > maxi:
			maxi = gd_m
		h.append(sd_m)
		h.append(gd_m)
d = [0] * (maxi + 2)
for j in range(len(h)):
	if j % 2 == 0:
		d[h[j]] += 1
	else:
		d[h[j] + 1] += -1
for i in range(1, len(d)):
	d[i] = d[i - 1] + d[i]
for k in range(l[1]):
	n = int(input())
	if 0 <= n < len(d):
		print(d[n])
	else:
		print(0)


from math import sqrt, floor, ceil
from bisect import bisect_right
(N, Q) = map(int, input().split())
circles = []
boundaries = {0: 0}
for _ in range(N):
	(X1, Y1, R1) = map(int, input().split())
	for (X2, Y2, R2) in circles:
		dist = sqrt((X1 - X2) ** 2 + (Y1 - Y2) ** 2)
		floor_dist = floor(dist)
		start = max(0, abs(R1 - R2) - floor_dist, ceil(dist) - R1 - R2)
		end = floor_dist + R1 + R2 + 1
		if start not in boundaries:
			boundaries[start] = 0
		boundaries[start] += 1
		if end not in boundaries:
			boundaries[end] = 0
		boundaries[end] -= 1
	circles.append((X1, Y1, R1))
keys = sorted(boundaries)
good_pairs = []
for key in keys:
	if not key:
		good_pairs.append(boundaries[0])
	else:
		good_pairs.append(good_pairs[-1] + boundaries[key])
for _ in range(Q):
	K = int(input())
	print(good_pairs[bisect_right(keys, K) - 1])


import math
(n, q) = map(int, input().split())
x = []
y = []
r = []
h = []
for i in range(0, n):
	x.append(0)
	y.append(0)
	r.append(0)
for i in range(0, 1000003):
	h.append(0)
for i in range(n):
	(x[i], y[i], r[i]) = map(int, input().split())
for j in range(0, n - 1):
	for l in range(j + 1, n):
		a = math.sqrt(pow(x[j] - x[l], 2) + pow(y[j] - y[l], 2))
		b = a + r[j] + r[l]
		c = r[j] + r[l]
		if a > c:
			d = a - c
		elif a + min(r[j], r[l]) < max(r[j], r[l]):
			d = max(r[j], r[l]) - a - min(r[j], r[l])
		else:
			d = 0
		u = math.floor(b)
		v = math.ceil(d)
		h[v] += 1
		h[u + 1] -= 1
for i in range(1, 1000003):
	h[i] = h[i] + h[i - 1]
while q != 0:
	k = int(input())
	print(h[k])
	q -= 1


import math
(n, q) = map(int, input().split(' '))
lia = []
for i in range(n):
	temp = list(map(int, input().split(' ')))
	lia.append(temp)

def powo(x, y):
	if y == 0:
		return 1
	elif y % 2 == 0:
		return powo(x, y // 2) * powo(x, y // 2)
	else:
		return x * powo(x, y // 2) * powo(x, y // 2)
fina = [0] * 1000005
for i in range(n):
	for j in range(i + 1, n):
		r1 = lia[i][2]
		r2 = lia[j][2]
		x1 = lia[i][0]
		x2 = lia[j][0]
		y1 = lia[i][1]
		y2 = lia[j][1]
		dis = math.sqrt(powo(x1 - x2, 2) + powo(y1 - y2, 2))
		if dis > r1 + r2:
			fina[math.ceil(dis) - r1 - r2] += 1
			fina[math.floor(dis) + r1 + r2 + 1] -= 1
		elif dis < abs(r1 - r2):
			fina[math.ceil(abs(r1 - r2) - dis)] += 1
			fina[math.floor(dis) + r1 + r2 + 1] -= 1
		elif dis == abs(r1 - r2):
			fina[0] += 1
			fina[2 * max(r1, r2) + 1] -= 1
		elif dis == r1 + r2:
			fina[0] += 1
			fina[2 * (r1 + r2) + 1] -= 1
		else:
			fina[0] += 1
			fina[r1 + r2 + math.floor(dis) + 1] -= 1
for i in range(1, 1000005):
	fina[i] += fina[i - 1]
for i in range(q):
	k = int(input())
	print(fina[k])


from math import sqrt

def solve(intervals):
	result = []
	for i in range(len(intervals)):
		result.append(intervals[i][0])
		result.append(intervals[i][1])
	result = sorted(list(set(result)))
	end_count = {}
	start_count = {}
	for i in range(len(intervals)):
		try:
			end_count[intervals[i][1]] += 1
		except:
			end_count[intervals[i][1]] = 1
	for i in range(len(intervals)):
		try:
			start_count[intervals[i][0]] += 1
		except:
			start_count[intervals[i][0]] = 1
	ans = [0] * 1000007
	val = 0
	i = 0
	k = 0
	while k < len(result):
		while i < result[k]:
			ans[i] = val
			i += 1
		flag = False
		while k < len(result) and result[k] <= i:
			if result[k] in start_count:
				val += start_count[result[k]]
			if result[k] in end_count:
				if result[k] == i:
					ans[i] = val
					flag = True
					val -= end_count[result[k]]
					k += 1
					i += 1
					break
				val -= end_count[result[k]]
			k += 1
		if not flag:
			ans[i] = val
			i += 1
	return ans

def circle(c1, c2):
	x1 = c1[0]
	y1 = c1[1]
	r1 = c1[2]
	x2 = c2[0]
	y2 = c2[1]
	r2 = c2[2]
	distSq = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)
	radSumSq = (r1 + r2) * (r1 + r2)
	if distSq >= radSumSq:
		minn = sqrt(distSq) - r1 - r2
		maxx = sqrt(distSq) + r1 + r2
	else:
		minn = abs(r1 - r2) - sqrt(distSq)
		maxx = sqrt(distSq) + r1 + r2
	return (minn, maxx)
(n, q) = map(int, input().split())
circle_data = []
for i in range(n):
	(x, y, r) = map(int, input().split())
	circle_data.append((x, y, r))
data = []
for i in range(n):
	for j in range(i + 1, n):
		data.append(circle(circle_data[i], circle_data[j]))
ans = solve(data)
for _ in range(q):
	k = int(input())
	print(ans[k])


import math
(n, q) = map(int, input().split())
circles = []
for _ in range(n):
	l = input().split()
	(l[0], l[1], l[2]) = (int(l[0]), int(l[1]), int(l[2]))
	circles.append(l)
num = [0] * (10 ** 6 + 2)
for i in range(len(circles) - 1):
	for j in range(i + 1, len(circles)):
		dist = ((circles[i][0] - circles[j][0]) ** 2 + (circles[i][1] - circles[j][1]) ** 2) ** 0.5
		r = circles[i][2] if circles[i][2] <= circles[j][2] else circles[j][2]
		R = circles[i][2] if circles[i][2] > circles[j][2] else circles[j][2]
		if dist - r - R > 0:
			min_dist = dist - r - R
			max_dist = dist + r + R
		elif dist - r - R == 0:
			min_dist = 0
			max_dist = 2 * r + 2 * R
		elif dist + r > R:
			min_dist = 0
			max_dist = dist + r + R
		elif dist + r == R:
			min_dist = 0
			max_dist = dist - r + R
		else:
			min_dist = R - dist - r
			max_dist = R + dist + r
		(min_dist, max_dist) = (math.ceil(min_dist), math.floor(max_dist))
		num[min_dist] += 1
		num[max_dist + 1] += -1
for i in range(1, 10 ** 6 + 1):
	num[i] += num[i - 1]
for _ in range(q):
	k = int(input())
	print(num[k])


import math

def func(n, u):
	c1c2 = math.sqrt(pow(n[0] - u[0], 2) + pow(n[1] - u[1], 2))
	r1 = n[2]
	r2 = u[2]
	if r1 >= c1c2 + r2:
		return (int(c1c2 + r1 + r2), max(math.ceil(r1 - c1c2 - r2), 0))
	elif r2 >= c1c2 + r1:
		return (int(c1c2 + r1 + r2), max(math.ceil(r2 - c1c2 - r1), 0))
	else:
		return (int(c1c2 + r1 + r2), max(math.ceil(c1c2 - (r1 + r2)), 0))
(n, q) = map(int, input().split())
arr = []
M = [0] * 1000001
m = [0] * 1000001
d = {}
for _ in range(n):
	(x, y, r) = map(int, input().split())
	arr.append([x, y, r])
h = 0
for i in range(n - 1):
	for j in range(i + 1, n):
		(a, b) = func(arr[i], arr[j])
		m[b] += 1
		M[a] += 1
		if a > h:
			h = a
		else:
			continue
d[0] = m[0]
for i in range(1, h + 1):
	d[i] = m[i] - M[i - 1] + d[i - 1]
for _ in range(q):
	k = int(input())
	if k > h:
		print(0)
	else:
		print(d[k])


import math

def dist(c1, c2):
	return math.sqrt((c1[0] - c2[0]) ** 2 + (c1[1] - c2[1]) ** 2)
(n, q) = map(int, input().split())
l = []
for i in range(n):
	t = list(map(int, input().split()))
	l.append(t)
res = [0] * (10 ** 6 + 1)
for i in range(n):
	for j in range(i + 1, n):
		d = dist(l[i], l[j])
		(r1, r2) = (l[i][2], l[j][2])
		if d > r1 + r2:
			mi = d - (r1 + r2)
			mx = d + (r1 + r2)
			res[math.ceil(mi)] += 1
			res[math.floor(mx) + 1] -= 1
		elif abs(r1 - r2) <= d and d <= r1 + r2:
			mi = 0
			mx = d + r1 + r2
			res[math.ceil(mi)] += 1
			res[math.floor(mx) + 1] -= 1
		else:
			mi = max(r1, r2) - d - min(r1, r2)
			mx = d + r1 + r2
			res[math.ceil(mi)] += 1
			res[math.floor(mx) + 1] -= 1
for i in range(1, len(res)):
	res[i] += res[i - 1]
for a0 in range(q):
	k = int(input())
	print(res[k])


import sys
from math import *
from itertools import *

def dist(A, B):
	(x1, y1) = (A[0], A[1])
	(x2, y2) = (B[0], B[1])
	y = (y2 - y1) ** 2
	x = (x2 - x1) ** 2
	ans = (x + y) ** 0.5
	return ans

def interact(A, B):
	r1 = A[2]
	r2 = B[2]
	CC = dist(A, B)
	if CC >= r1 + r2:
		return (0, CC)
	elif CC == 0 and r1 == r2:
		return (1, CC)
	elif CC <= abs(r1 - r2):
		return (2, CC)
	else:
		return (1, CC)

def MinMaxDist(A, B):
	(r1, r2) = (max(A[2], B[2]), min(A[2], B[2]))
	(flag, CC) = interact(A, B)
	if flag == 0:
		minDist = CC - r1 - r2
		maxDist = CC + r1 + r2
	elif flag == 1:
		minDist = 0
		maxDist = CC + r1 + r2
	elif flag == 2:
		minDist = r1 - r2 - CC
		maxDist = r1 + r2 + CC
	return (minDist, maxDist)
(N, Q) = list(map(int, input().strip().split()))
circles = []
arr = [0 for i in range(1000000)]
for i in range(N):
	(X, Y, R) = map(int, sys.stdin.readline().split())
	circles.append((X, Y, R))
	for j in range(i):
		(mini, maxi) = MinMaxDist(circles[i], circles[j])
		mini = ceil(mini)
		maxi = floor(maxi)
		arr[mini] += 1
		arr[maxi + 1] -= 1
prefix = list(accumulate(arr))
for i in range(Q - 1):
	K = int(sys.stdin.readline())
	if i != Q - 1:
		sys.stdout.write(str(prefix[K]) + '\n')
K = int(sys.stdin.readline())
sys.stdout.write(str(prefix[K]))


import math
(N, Q) = map(int, input().split())
(C, L, K) = ([], [], [])
_ = [C.append([int(x) for x in input().split()]) for _ in range(N)]
for i in range(N):
	for j in range(i + 1, N):
		if C[i][0] == C[j][0] and C[i][1] == C[j][1]:
			L.append([int(abs(C[i][2] - C[j][2])), int(C[i][2] + C[j][2])])
		else:
			m = pow(pow(C[i][0] - C[j][0], 2) + pow(C[i][1] - C[j][1], 2), 0.5)
			if m > C[i][2] + C[j][2]:
				L.append([math.ceil(m - C[i][2] - C[j][2]), math.floor(m + C[i][2] + C[j][2])])
			elif m + min(C[i][2], C[j][2]) <= max(C[i][2], C[j][2]):
				L.append([math.ceil(max(C[i][2], C[j][2]) - m - min(C[i][2], C[j][2])), math.floor(max(C[i][2], C[j][2]) + m + min(C[i][2], C[j][2]))])
			else:
				L.append([0, math.floor(C[i][2] + C[j][2] + m)])
_ = [K.append([int(x) for x in input().split()]) for i in range(Q)]
M = [0] * 1000002
for l in L:
	M[l[0]] += 1
	M[l[1] + 1] -= 1
for i in range(1, 1000000):
	M[i] += M[i - 1]
for k in K:
	print(M[k[0]])


import math
a = [int(i) for i in input().split()]
b = []
d = []
e = []
g = []
out = [0] * 10 ** 6
t = a[0] * (a[0] - 1)
for i in range(a[0]):
	b.append([int(i) for i in input().split()])
for i in range(a[1]):
	c = int(input())
	d.append(c)
for i in range(len(b)):
	for j in range(i + 1, len(b)):
		h = math.sqrt((b[i][0] - b[j][0]) ** 2 + (b[i][1] - b[j][1]) ** 2)
		if h > abs(b[i][2] - b[j][2]) and h <= b[i][2] + b[j][2] or h >= b[i][2] + b[j][2]:
			k = math.sqrt((b[i][0] - b[j][0]) ** 2 + (b[i][1] - b[j][1]) ** 2) - b[i][2] - b[j][2]
			if k > 0:
				out[math.ceil(k)] = out[math.ceil(k)] + 1
			else:
				out[0] = out[0] + 1
			ck = math.floor(math.sqrt((b[i][0] - b[j][0]) ** 2 + (b[i][1] - b[j][1]) ** 2) + b[i][2] + b[j][2])
			out[ck + 1] = out[ck + 1] - 1
		elif h == abs(b[i][2] - b[j][2]):
			out[0] = out[0] + 1
			ck1 = math.floor(2 * max(b[i][2], b[j][2]))
			out[ck1 + 1] = out[ck1 + 1] - 1
		else:
			max1 = max(b[i][2], b[j][2])
			min1 = min(b[i][2], b[j][2])
			out[math.ceil(max1 - h - min1)] = out[math.ceil(max1 - h - min1)] + 1
			ck3 = math.floor(max1 + h + min1)
			out[ck3 + 1] = out[ck3 + 1] - 1
out1 = [0] * 10 ** 6
out1[0] = out[0]
for i in range(1, len(out)):
	out1[i] = out1[i - 1] + out[i]
for i in d:
	print(out1[i])


import math

def ed(x1, y1, x2, y2):
	return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5
(n, q) = [int(j) for j in input().split()]
l = [[0] for i in range(n)]
for i in range(n):
	l1 = [int(j) for j in input().split()]
	l[i] = l1
l2 = [0 for i in range(10 ** 6 + 1)]
cn = 0
for i in range(n - 1):
	for j in range(i + 1, n):
		k = ed(l[i][0], l[i][1], l[j][0], l[j][1])
		ab = abs(l[i][2] - l[j][2])
		f1 = l[i][2] + l[j][2] + k
		if k < ab:
			l2[math.ceil(ab - k)] += 1
			l2[math.floor(f1) + 1] -= 1
		elif k >= ab and k <= l[i][2] + l[j][2]:
			l2[0] += 1
			l2[math.floor(f1) + 1] -= 1
		else:
			l2[math.ceil(k - (l[i][2] + l[j][2]))] += 1
			l2[math.floor(f1) + 1] -= 1
for i in range(1, 10 ** 6 + 1):
	l2[i] = l2[i] + l2[i - 1]
for k1 in range(q):
	f1 = int(input())
	print(l2[f1])


import math

def dist(x1, y1, x2, y2):
	return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5

def get_range(c1, c2):
	(x1, y1, r1) = c1
	(x2, y2, r2) = c2
	if c1 == c2:
		return (0, 2 * r1)
	k = dist(x1, y1, x2, y2)
	if k >= r1 + r2:
		return (k - r1 - r2, k + r1 + r2)
	elif k <= abs(r2 - r1):
		r_1 = min(r1, r2)
		r_2 = max(r1, r2)
		return (r_2 - k - r_1, r_2 + k + r_1)
	else:
		return (0, r1 + r2 + k)
(N, Q) = [int(i) for i in input().split()]
li = [tuple([int(i) for i in input().split()]) for j in range(N)]
qls = [int(input()) for i in range(Q)]
sli = [0 for i in range(10 ** 6 + 2)]
for i in range(N):
	for j in range(i + 1, N):
		(mn, mx) = get_range(li[i], li[j])
		mn = math.ceil(mn)
		mx = math.floor(mx)
		sli[mn] += 1
		sli[mx + 1] -= 1
for i in range(1, 10 ** 6 + 1):
	sli[i] += sli[i - 1]
for i in qls:
	print(sli[i])


from math import sqrt, ceil, floor
(n, q) = map(int, input().split())
x = []
y = []
r = []
qu = []
s = n
while s > 0:
	s -= 1
	(xx, yy, rr) = map(int, input().split())
	x.append(xx)
	y.append(yy)
	r.append(rr)
s = q
while s > 0:
	s -= 1
	qs = int(input())
	qu.append(qs)
l = []
u = []
k = 0
f = [0] * (10 ** 6 + 10)
for i in range(0, n):
	for j in range(i + 1, n):
		if x[i] == x[j] and y[i] == y[j]:
			l.append(abs(r[i] - r[j]))
			u.append(abs(r[i] + r[j]))
			if r[i] == r[j]:
				u.pop()
				u.append(0)
		else:
			d = sqrt((x[i] - x[j]) ** 2 + (y[i] - y[j]) ** 2)
			if d > r[i] + r[j]:
				l.append(d - (r[i] + r[j]))
				u.append(d + (r[i] + r[j]))
			elif d == r[i] + r[j]:
				l.append(0)
				u.append(2 * r[i] + 2 * r[j])
			elif d < r[i] + r[j] and d > abs(r[i] - r[j]):
				l.append(0)
				u.append(d + r[i] + r[j])
			elif d < abs(r[i] - r[j]):
				r1 = max(r[i], r[j])
				r2 = min(r[i], r[j])
				l.append(r1 - (d + r2))
				u.append(r1 + r2 + d)
			elif d == abs(r[i] - r[j]):
				r1 = max(r[i], r[j])
				r2 = min(r[i], r[j])
				l.append(0)
				u.append(2 * r1)
		f[ceil(l[k])] += 1
		f[floor(u[k]) + 1] -= 1
		k += 1
for i in range(1, floor(max(u)) + 1):
	f[i] = f[i - 1] + f[i]
o = floor(max(u))
for i in range(0, q):
	if qu[i] > o:
		print(0)
	else:
		print(f[qu[i]])


import math
(n, q) = map(int, input().split())
x = []
y = []
r = []
for i in range(n):
	(a, b, c) = map(int, input().split())
	x.append(a)
	y.append(b)
	r.append(c)
s = [0] * 5000000
t = [0] * 5000000
for i in range(n):
	for j in range(i + 1, n):
		a1 = x[i]
		b1 = y[i]
		c1 = r[i]
		a2 = x[j]
		b2 = y[j]
		c2 = r[j]
		d = math.sqrt((a1 - a2) ** 2 + (b1 - b2) ** 2)
		maxx = 0
		minn = 0
		if d >= c1 + c2:
			maxx = c1 + c2 + d
			minn = d - (c1 + c2)
		elif a1 == a2 and b1 == b2:
			maxx = c1 + c2
			minn = abs(c1 - c2)
		elif max(c1, c2) == d + min(c1, c2):
			maxx = 2 * max(c1, c2)
			minn = 0
		elif max(c1, c2) < d + min(c1, c2):
			maxx = d + c1 + c2
			minn = 0
		else:
			maxx = d + c1 + c2
			minn = max(c1, c2) - (d + min(c1, c2))
		s[math.floor(maxx)] += 1
		t[math.ceil(minn)] += 1
for i in range(1, 5000000):
	t[i] += t[i - 1]
	t[i] -= s[i - 1]
for i in range(q):
	k = int(input())
	print(t[k])


import math
ans = [0 for i in range(0, 1000001)]
(n, q) = map(int, input().split())
ar = [[0 for j in range(3)] for i in range(n)]
for i in range(0, n):
	(ar[i][0], ar[i][1], ar[i][2]) = map(int, input().split())
	for j in range(0, i):
		euclideanDistance = math.sqrt((ar[i][0] - ar[j][0]) * (ar[i][0] - ar[j][0]) + (ar[i][1] - ar[j][1]) * (ar[i][1] - ar[j][1]))
		if euclideanDistance < abs(ar[i][2] - ar[j][2]):
			r1 = max(ar[i][2], ar[j][2])
			r2 = min(ar[i][2], ar[j][2])
			v = math.ceil(r1 - euclideanDistance - r2)
			inv = int(r1 + r2 + euclideanDistance + 1)
			if v < 0:
				v = 0
			ans[v] += 1
			ans[inv] -= 1
		else:
			v = math.ceil(-ar[i][2] - ar[j][2] + euclideanDistance)
			inv = int(ar[i][2] + ar[j][2] + euclideanDistance + 1)
			if v < 0:
				v = 0
			ans[v] += 1
			ans[inv] -= 1
for i in range(1, 1000001):
	ans[i] += ans[i - 1]
while q > 0:
	k = int(input())
	print(ans[k])
	q -= 1


import math
(n, q) = map(int, input().split(' '))
x = []
y = []
r = []
for i in range(n):
	(x_, y_, r_) = map(int, input().split(' '))
	x.append(x_)
	y.append(y_)
	r.append(r_)
fin = [0] * 1000004
for i in range(n):
	for j in range(i + 1, n):
		(mi, mx) = (0, 0)
		sa = math.sqrt(math.pow(abs(x[i] - x[j]), 2) + math.pow(abs(y[i] - y[j]), 2))
		if sa > r[i] + r[j]:
			fin[math.ceil(sa) - r[i] - r[j]] += 1
			fin[math.floor(sa) + r[i] + r[j] + 1] -= 1
		elif sa < abs(r[i] - r[j]):
			fin[math.ceil(abs(r[i] - r[j]) - sa)] += 1
			fin[math.floor(sa) + r[i] + r[j] + 1] -= 1
		elif sa == abs(r[i] - r[j]):
			fin[0] += 1
			fin[2 * max(r[i], r[j]) + 1] += 1
		elif sa == r[i] + r[j]:
			fin[0] += 1
			fin[2 * (r[i] + r[j]) + 1] -= 1
		else:
			fin[0] += 1
			fin[r[i] + r[j] + math.floor(sa) + 1] -= 1
for i in range(1, 1000004):
	fin[i] += fin[i - 1]
for i in range(q):
	k = int(input())
	print(fin[k])


import math
import bisect

def dist(info1, info2):
	return ((info1[0] - info2[0]) ** 2 + (info1[1] - info2[1]) ** 2) ** 0.5

def find_lt(a, x):
	i = bisect.bisect_left(a, x)
	if i:
		return i
	return -1

def find_gt(a, x):
	i = bisect.bisect_right(a, x)
	if i != len(a):
		return i
	return -1
(n, q) = map(int, input().split())
info = []
for _ in range(n):
	(x, y, r) = map(int, input().split())
	info.append([x, y, r])
maxs = []
mins = []
for i in range(1, n):
	(x1, y1, r1) = (info[i][0], info[i][1], info[i][2])
	for j in range(0, i):
		(x2, y2, r2) = (info[j][0], info[j][1], info[j][2])
		dis = dist(info[i], info[j])
		maxdis = 0
		mindis = 0
		if r1 + r2 <= dis:
			mindis = dis - r1 - r2
			maxdis = dis + r1 + r2
		elif dis > abs(r1 - r2) and dis < r1 + r2:
			maxdis = dis + r2 + r1
			mindis = 0
		elif dis == abs(r1 - r2):
			maxdis = dis + r1 + r2
			mindis = 0
		elif abs(r1 - r2) > dis:
			maxdis = dis + r1 + r2
			mindis = abs(r1 - r2) - dis
		maxdis = math.floor(maxdis)
		mindis = math.ceil(mindis)
		if x1 != x2 or y1 != y2 or r1 != r2:
			maxs.append(maxdis)
			mins.append(mindis)
mins.sort()
maxs.sort()
for _ in range(q):
	total = len(mins)
	k = int(input())
	y = find_gt(mins, k)
	if y != -1:
		total = y
	if total != 0:
		z = find_lt(maxs, k)
		if z != -1:
			total -= find_lt(maxs, k)
	print(total)


from math import ceil
(n, q) = map(int, input().split())
l = []
d = []
ans = [0] * 1000002
[l.append(tuple(map(int, input().split()))) for N in range(n)]
for i in range(n - 1):
	for j in range(i + 1, n):
		m = 0
		d1 = ((l[i][0] - l[j][0]) ** 2 + (l[i][1] - l[j][1]) ** 2) ** 0.5
		if l[j][2] > d1 + l[i][2] or l[i][2] > d1 + l[j][2]:
			m = max(l[i][2], l[j][2]) - d1 - min(l[i][2], l[j][2])
		elif d1 >= l[i][2] + l[j][2]:
			m = d1 - l[i][2] - l[j][2]
		M = d1 + l[i][2] + l[j][2]
		ans[ceil(m)] += 1
		ans[int(M) + 1] -= 1
for i in range(1, 1000001):
	ans[i] += ans[i - 1]
[print(ans[int(input())]) for Q in range(q)]


from math import ceil, sqrt
(n, q) = map(int, input().split())
circles = []
for i in range(n):
	(x, y, r) = map(int, input().split())
	circles.append((x, y, r))
counts = [0] * 2000000
for i in range(n - 1):
	for j in range(i + 1, n):
		(x1, y1, r1) = circles[i]
		(x2, y2, r2) = circles[j]
		(r1, r2) = (max(r1, r2), min(r1, r2))
		mind = 0
		cd = sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
		if r1 + r2 <= cd:
			mind = int(ceil(cd - r1 - r2))
		elif r1 >= cd + r2:
			mind = int(ceil(r1 - cd - r2))
		counts[mind] += 1
		maxd = int(cd + r1 + r2)
		if maxd + 1 < 2000000:
			counts[maxd + 1] -= 1
ans = []
for i in range(1, len(counts)):
	counts[i] += counts[i - 1]
for query in range(q):
	k = int(input())
	ans.append(counts[k])
print(*ans, sep='\n')


import math
(n, q) = map(int, input().split())
Cir = []
Dis = []
for i in range(n):
	(a, b, c) = map(int, input().split())
	Cir.append([a, b, c])
for i in range(n - 1):
	for j in range(i + 1, n):
		AA = Cir[i]
		BB = Cir[j]
		dist = (AA[0] - BB[0]) ** 2 + (AA[1] - BB[1]) ** 2
		dist = math.sqrt(dist)
		if dist == AA[2] + BB[2]:
			Dis.append([0, dist + AA[2] + BB[2]])
		elif max(AA[2], BB[2]) > dist + min(AA[2], BB[2]):
			Dis.append([max(AA[2], BB[2]) - dist - min(AA[2], BB[2]), dist + AA[2] + BB[2]])
		elif dist < AA[2] + BB[2]:
			Dis.append([0, dist + AA[2] + BB[2]])
		else:
			Dis.append([dist - AA[2] - BB[2], dist + AA[2] + BB[2]])
Dis2 = [0] * 1000007
for i in range(len(Dis)):
	a = math.ceil(Dis[i][0])
	b = math.floor(Dis[i][1])
	Dis2[min(a, 1000001)] += 1
	Dis2[min(b + 1, 1000001)] -= 1
for i in range(1, len(Dis2)):
	Dis2[i] += Dis2[i - 1]
	if Dis2[i] < 0:
		Dis2[i] = 0
for i in range(q):
	d = int(input())
	print(Dis2[d])


from math import sqrt, floor, ceil
(n, q) = [int(x) for x in input().strip().split(' ')]
l = []
for i in range(n):
	l.append([int(x) for x in input().strip().split(' ')])
start = []
end = []
u = []
for i in range(n):
	for j in range(i + 1, n):
		c1c2 = sqrt((l[j][0] - l[i][0]) ** 2 + (l[j][1] - l[i][1]) ** 2)
		if abs(l[j][2] - l[i][2]) < c1c2 < l[j][2] + l[i][2]:
			start.append(0)
			end.append(int(floor(c1c2 + l[i][2] + l[j][2])))
		elif c1c2 >= l[j][2] + l[i][2]:
			start.append(int(ceil(c1c2 - (l[j][2] + l[i][2]))))
			end.append(int(floor(c1c2 + (l[j][2] + l[i][2]))))
		elif c1c2 <= abs(l[i][2] - l[j][2]):
			start.append(int(ceil(abs(l[i][2] - l[j][2]) - c1c2)))
			end.append(int(floor(c1c2 + l[i][2] + l[j][2])))
ln = len(start)
x = 1000001 * [0]
for i in range(ln):
	x[start[i]] += 1
	x[end[i] + 1] -= 1
s = 0
for i in range(0, 1000001):
	s += x[i]
	x[i] = s
for i in range(q):
	k = int(input().strip())
	print(x[k])


from math import *

def distance(x1, y1, x2, y2):
	return sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2))
(N, Q) = (int(i) for i in input().split())
diff_arr = [0] * 1000005

def increment(i, j):
	i = max(i, 0)
	j = min(j, 1000000)
	diff_arr[i] += 1
	diff_arr[j + 1] -= 1
tab_X = []
tab_Y = []
tab_R = []
for _ in range(N):
	(x, y, r) = (int(i) for i in input().split())
	tab_X.append(x)
	tab_Y.append(y)
	tab_R.append(r)
for i in range(N):
	for j in range(i + 1, N):
		deuxRayons = tab_R[i] + tab_R[j]
		dst = distance(tab_X[i], tab_Y[i], tab_X[j], tab_Y[j])
		mx = int(floor(dst + deuxRayons))
		minR = min(tab_R[i], tab_R[j])
		maxR = max(tab_R[i], tab_R[j])
		mn = dst - deuxRayons
		if maxR > dst + minR:
			mn = maxR - dst - minR
		mn = int(ceil(mn))
		increment(mn, mx)
ans = [0] * 1000005
ans[0] = diff_arr[0]
for i in range(1, 1000001):
	ans[i] = ans[i - 1] + diff_arr[i]
for q in range(Q):
	K = int(input())
	print(ans[K])


from math import *
(n, q) = list(map(int, input().split()))
l = []
a = [0] * (10 ** 6 + 3)
for i in range(n):
	(x, y, r) = list(map(int, input().split()))
	for i in l:
		d = ((x - i[0]) ** 2 + (y - i[1]) ** 2) ** 0.5
		if r - d - i[2] > 0:
			mind = r - d - i[2]
		elif i[2] - r - d > 0:
			mind = i[2] - r - d
		else:
			mind = d - r - i[2]
			if mind < 0:
				mind = 0
		mind = ceil(mind)
		maxd = d + r + i[2]
		maxd = int(maxd)
		if maxd > 10 ** 6:
			maxd = 10 ** 6
		if mind > 10 ** 6:
			mind = -1
		a[mind] += 1
		a[maxd + 1] -= 1
	l.append((x, y, r))
b = [0] * (10 ** 6 + 1)
for i in range(10 ** 6 + 1):
	if i == 0:
		b[i] = a[i]
	else:
		b[i] = b[i - 1] + a[i]
for i in range(q):
	i = int(input())
	print(b[i])


from math import ceil
(n, q) = [int(i) for i in input().split()]
a = []
d = [[0] * 2 for i in range(10 ** 6)]
for i in range(n):
	b = [float(j) for j in input().split()]
	a.append(b)
for i in range(n - 1):
	for j in range(i + 1, n):
		(x1, y1, r1, x2, y2, r2) = (a[i][0], a[i][1], a[i][2], a[j][0], a[j][1], a[j][2])
		di = ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5
		md = max(0, di - r1 - r2)
		if di < abs(r1 - r2):
			md = abs(r1 - r2) - di
		d[ceil(md)][0] += 1
		d[int(di + r1 + r2) + 1][1] -= 1
m = [0] * 10 ** 6
c = 0
for i in range(10 ** 6):
	c += d[i][0] + d[i][1]
	m[i] = c
for i in range(q):
	print(m[int(input())])


import math
import bisect
(n, q) = [int(x) for x in input().split()]
x = []
y = []
r = []
m = []
M = []
dic = []
(xx, yy, zz) = [int(x) for x in input().split()]
x.append(xx)
y.append(yy)
r.append(zz)
for i in range(1, n):
	(xx, yy, zz) = [int(x) for x in input().split()]
	x.append(xx)
	y.append(yy)
	r.append(zz)
	for j in range(i - 1, -1, -1):
		u = math.sqrt((x[j] - x[i]) ** 2 + (y[j] - y[i]) ** 2)
		min1 = u - r[i] - r[j]
		if min1 < 0:
			min1 = 0
		if u + min(r[i], r[j]) < max(r[i], r[j]):
			min1 = max(r[i], r[j]) - u - min(r[i], r[j])
		max1 = u + r[i] + r[j]
		M.append(max1)
		m.append(min1)
m.sort()
M.sort()
for i in range(q):
	k = int(input())
	dic.append(k)
	print(bisect.bisect_right(m, k) - bisect.bisect_left(M, k))


import math
import bisect

def binarySearch(arr, l, r, x):
	if r < l:
		return -1
	mid = int(l + (r - l) / 2)
	if arr[mid] == x:
		return mid
	if arr[mid] > x:
		return binarySearch(arr, l, mid - 1, x)
	return binarySearch(arr, mid + 1, r, x)

def countOccurrences(arr, n, x):
	ind = binarySearch(arr, 0, n - 1, x)
	if ind == -1:
		return 0
	count = 1
	left = ind - 1
	while left >= 0 and arr[left] == x:
		count += 1
		left -= 1
	right = ind + 1
	while right < n and arr[right] == x:
		count += 1
		right += 1
	return count
(n, q) = [int(x) for x in input().split()]
x = []
y = []
r = []
m = []
M = []
(xx, yy, zz) = [int(x) for x in input().split()]
x.append(xx)
y.append(yy)
r.append(zz)
for i in range(1, n):
	(xx, yy, zz) = [int(x) for x in input().split()]
	x.append(xx)
	y.append(yy)
	r.append(zz)
	for j in range(i - 1, -1, -1):
		u = math.sqrt((x[j] - x[i]) ** 2 + (y[j] - y[i]) ** 2)
		min1 = u - r[i] - r[j]
		if min1 < 0:
			min1 = 0
		if u + min(r[i], r[j]) < max(r[i], r[j]):
			min1 = max(r[i], r[j]) - u - min(r[i], r[j])
		M.append(u + r[i] + r[j])
		m.append(min1)
m.sort()
M.sort()
for i in range(q):
	k = int(input())
	print(bisect.bisect_right(m, k) - bisect.bisect_left(M, k))


from math import sqrt, floor, ceil

def check(a, b):
	(mnr, mxr) = (min(a[2], b[2]), max(a[2], b[2]))
	rsum = a[2] + b[2]
	if a[0] == b[0] and a[1] == b[1]:
		if a[2] == b[2]:
			return [0, 2 * a[2]]
		else:
			return [mxr - mnr, rsum]
	dis = sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)
	mn = dis - rsum
	mx = dis + rsum
	if dis == a[2] + b[2]:
		return [0, 2 * rsum]
	elif dis > rsum:
		return [mn, mx]
	elif dis <= mxr - mnr:
		p = mxr - (mnr + dis)
		return [p, dis + rsum]
	else:
		return [0, dis + rsum]
(n, q) = map(int, input().split())
a = []
b = [0] * (10 ** 6 + 1)
se = [[0, 0] for y in range(10 ** 6 + 2)]
for e in range(n):
	a.append(list(map(int, input().split())))
for i in range(0, n - 1):
	for j in range(i + 1, n):
		x = check(a[i], a[j])
		se[int(ceil(x[0]))][0] += 1
		se[int(floor(x[1]))][1] += 1
p = 0
for i in range(0, 10 ** 6 + 1):
	p += se[i][0]
	b[i] = p
	p -= se[i][1]
for e in range(q):
	k = int(input())
	print(b[k])


import math

def adding_val(listval, N, l, h, val):
	listval[l] += val
	if h != N - 1:
		listval[h + 1] -= val

def updatelistval(listval, N):
	for i in range(1, N):
		listval[i] += listval[i - 1]
(n, q) = [int(x) for x in input().split()]
c = []
for i in range(n):
	c.append([int(x) for x in input().split()])
ks = 1000000
kvals = [0 for i in range(ks)]
for x in range(n):
	for y in range(x + 1, n):
		a = c[x]
		b = c[y]
		r1 = a[2]
		r2 = b[2]
		z = math.sqrt(math.pow(a[0] - b[0], 2) + math.pow(a[1] - b[1], 2))
		if a != b:
			if z < r1 + r2 and z <= abs(r1 - r2):
				adding_val(kvals, ks, max(0, math.ceil(max(r1, r2) - z - min(r1, r2))), math.floor(r1 + r2 + z), 1)
			else:
				adding_val(kvals, ks, max(0, math.ceil(z - r1 - r2)), math.floor(z + r1 + r2), 1)
del n
del c
updatelistval(kvals, ks)
for i in range(q):
	query = int(input())
	print(kvals[query])


import math
left__limit = [0] * 5000007
right_limit = [0] * 5000007

def rng(mn, mx):
	left__limit[math.ceil(mn)] += 1
	right_limit[int(mx)] += 1

def dist(circle1, circle2):
	(x1, y1, r1) = circle1
	(x2, y2, r2) = circle2
	centre_distance = math.hypot(x2 - x1, y2 - y1)
	if x1 == x2 and y1 == y2:
		minimum_possible_range = abs(r1 - r2)
		maximum_possible_range = r1 + r2
	elif centre_distance >= r1 + r2:
		minimum_possible_range = centre_distance - r1 - r2
		maximum_possible_range = centre_distance + r1 + r2
	elif centre_distance + min(r1, r2) < max(r1, r2):
		minimum_possible_range = max(r1, r2) - centre_distance - min(r1, r2)
		maximum_possible_range = r1 + r2 + centre_distance
	elif centre_distance + min(r1, r2) == max(r1, r2):
		minimum_possible_range = 0
		maximum_possible_range = 2 * max(r1, r2)
	else:
		minimum_possible_range = 0
		maximum_possible_range = centre_distance + r1 + r2
	rng(minimum_possible_range, maximum_possible_range)
(no_circles, no_queries) = map(int, input().split())
circles = []
for _ in range(no_circles):
	(x, y, radius) = map(int, input().split())
	circles.append((x, y, radius))
distance_ranges = []
pairs_of_circles = []
for i in range(no_circles):
	for j in range(i, no_circles):
		if i == j:
			continue
		dist(circles[i], circles[j])
for i in range(1, 5000007):
	left__limit[i] += left__limit[i - 1] - right_limit[i - 1]
for _ in range(no_queries):
	q = int(input())
	count = left__limit[q]
	print(count)


import math
(n, q) = map(int, input().split())
x = [None] * n
y = [None] * n
r = [None] * n
thr = [0] * 1000002
for i in range(n):
	(x[i], y[i], r[i]) = map(int, input().split())
for i in range(n):
	for j in range(i + 1, n):
		d = math.sqrt((x[j] - x[i]) ** 2 + (y[j] - y[i]) ** 2)
		if d >= r[i] + r[j]:
			min1 = d - r[i] - r[j]
			min1 = int(math.ceil(min1))
			max1 = int(d + r[i] + r[j])
		elif d > abs(r[i] - r[j]) and d < r[i] + r[j]:
			min1 = 0
			max1 = int(d) + r[i] + r[j]
		elif d < abs(r[i] - r[j]):
			min1 = abs(r[i] - r[j]) - d
			min1 = int(math.ceil(min1))
			max1 = int(d + r[i] + r[j])
		thr[min1] += 1
		thr[max1 + 1] -= 1
for i in range(1, 1000002):
	thr[i] = thr[i - 1] + thr[i]
for i in range(q):
	q1 = int(input())
	print(thr[q1])


from math import *
(n, q) = map(int, input().split())
x = []
y = []
r = []
for i in range(n):
	(a, b, c) = map(float, input().split())
	x.append(a)
	y.append(b)
	r.append(c)
res = []
for i in range(1000010):
	res.append(0)
for i in range(n):
	for j in range(i + 1, n):
		c2c = sqrt((x[i] - x[j]) ** 2 + (y[i] - y[j]) ** 2)
		larger_r = max(r[i], r[j])
		smaller_r = min(r[i], r[j])
		if c2c > r[i] + r[j]:
			low = c2c - r[i] - r[j]
		elif c2c <= r[i] + r[j] and c2c >= larger_r - smaller_r:
			low = 0
		elif c2c < larger_r - smaller_r:
			low = larger_r - c2c - smaller_r
		high = c2c + r[i] + r[j]
		low = ceil(low)
		high = floor(high)
		res[low] = res[low] + 1
		res[high + 1] = res[high + 1] - 1
for i in range(1, 1000010):
	res[i] = res[i - 1] + res[i]
for i in range(q):
	k = int(input())
	print(res[k])


from math import ceil, floor

class circle:

	def __init__(self, x, y, r):
		self.x = x
		self.y = y
		self.r = r

def calculate_distance(a, b):
	d = ((b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y)) ** 0.5
	if d >= a.r + b.r:
		min_distance = ceil(d - a.r - b.r)
		max_distance = floor(d + a.r + b.r)
		return (min_distance, max_distance)
	else:
		min_distance = max(a.r, b.r) - (d + min(a.r, b.r))
		if min_distance < 0:
			min_distance = 0
		min_distance = ceil(min_distance)
		max_distance = floor(d + a.r + b.r)
		return (min_distance, max_distance)
(n, q) = [int(x) for x in input().split()]
circle_pairs = []
(lower, upper) = ([0] * 1000005, [0] * 1000005)
ans = [0] * 1000005
max_distance = 0
for _ in range(n):
	t = [int(x) for x in input().split()]
	circle_pairs.append(circle(t[0], t[1], t[2]))
for i in range(n):
	for j in range(i + 1, n):
		distances = calculate_distance(circle_pairs[i], circle_pairs[j])
		lower[distances[0]] += 1
		upper[distances[1]] += 1
		max_distance = max(max_distance, distances[1])
ans[0] = lower[0] - upper[0]
for i in range(1, max_distance + 1):
	ans[i] = ans[i - 1] + lower[i] - upper[i - 1]
for _ in range(q):
	query = int(input())
	print(ans[query])


import math
import bisect
(n, q) = map(int, input().split())
x = []
y = []
r = []
a = []
b = []
for i in range(0, n):
	(n1, n2, n3) = map(float, input().split())
	x.append(n1)
	y.append(n2)
	r.append(n3)

def dist(i, j):
	d = math.pow(x[i] - x[j], 2) + math.pow(y[i] - y[j], 2)
	return math.sqrt(d)
for i in range(0, n - 1):
	for j in range(i + 1, n):
		if x[i] != x[j] or y[i] != y[j] or r[i] != r[j]:
			d = dist(i, j)
			small = min(r[i], r[j])
			big = max(r[i], r[j])
			if d > small + big:
				a.append(math.ceil(d - big - small))
			elif d < big - small:
				a.append(math.ceil(big - d - small))
			else:
				a.append(0)
			b.append(math.floor(d + small + big) + 1)
a = sorted(a)
b = sorted(b)
for i in range(0, q):
	k = int(input())
	more = bisect.bisect(a, k)
	less = bisect.bisect(b, k)
	print(more - less)


import math
(n, q) = [int(y) for y in input().split(' ')]
C = []
R = []
q1 = []
q2 = []
ans = []
for i in range(n):
	(c1, c2, r1) = [int(x) for x in input().split(' ')]
	c = (c1, c2)
	C.append(c)
	R.append(r1)
for i in range(len(C)):
	for j in range(i + 1, len(C)):
		d1 = (C[j][0] - C[i][0]) ** 2
		d2 = (C[j][1] - C[i][1]) ** 2
		d = math.sqrt(d1 + d2)
		if d <= abs(R[j] - R[i]) and d < R[i] + R[j]:
			min_ = max(max(R[i], R[j]) - d - min(R[i], R[j]), 0)
			max_ = R[i] + R[j] + d
		else:
			min_ = max(0, d - R[i] - R[j])
			max_ = d + R[i] + R[j]
		q1.append(math.ceil(min_))
		q2.append(math.floor(max_))
for i in range(max(q2) + 2):
	ans.append(0)
for j in range(len(q1)):
	ans[q1[j]] += 1
	ans[q2[j] + 1] -= 1
for j in range(1, len(ans)):
	ans[j] += ans[j - 1]
for i in range(q):
	temp = int(input())
	if temp in range(len(ans)):
		print(ans[temp])
	else:
		print('0')


import math
(n, q) = map(int, input().split())
mat = {}
for i in range(1, n + 1):
	x = list(map(int, input().split()))
	mat[i] = x
ans = [0] * (10 ** 6 + 5)
for i in range(1, n + 1):
	one = mat[i]
	for j in range(i + 1, n + 1):
		two = mat[j]
		r1 = one[2]
		r2 = two[2]
		dist = math.sqrt((one[0] - two[0]) ** 2 + (one[1] - two[1]) ** 2)
		if dist > r1 + r2:
			ans[max(math.ceil(dist - r1 - r2), 0)] += 1
			ans[min(math.floor(dist + r1 + r2) + 1, 10 ** 6 + 1)] -= 1
		elif dist == r1 + r2:
			ans[0] += 1
			ans[min(int(dist) + r1 + r2 + 1, 10 ** 6 + 1)] -= 1
		elif (r1 - r2) ** 2 <= dist ** 2 and dist ** 2 <= (r1 + r2) ** 2:
			ans[0] += 1
			ans[min(int(dist) + r1 + r2 + 1, 1000000 + 1)] -= 1
		elif r2 < r1:
			ans[max(0, math.ceil(r1 - (dist + r2)))] += 1
			ans[min(math.floor(2 * r1 - (r1 - (dist + r2)) + 1), 1000000 + 1)] -= 1
		else:
			mi = r2 - (dist + r1)
			ans[max(0, math.ceil(mi))] += 1
			ans[min(math.floor(2 * r2 - mi) + 1, 1000000 + 1)] -= 1
for i in range(1, len(ans)):
	ans[i] += ans[i - 1]
	if ans[i] < 0:
		ans[i] = 0
for qi in range(q):
	qq = int(input())
	print(ans[qq])


from math import sqrt, floor, ceil

def update(D, l, r, x):
	D[l] += x
	D[r + 1] -= x

def makeArray(A, D):
	for i in range(0, len(A)):
		if i == 0:
			A[i] = D[i]
		else:
			A[i] = D[i] + A[i - 1]

def dis(a, b):
	return sqrt((b[0] - a[0]) ** 2 + (b[1] - a[1]) ** 2)

def circheck(p1, p2, l):
	s = dis(p1, p2)
	r1 = p1[2]
	r2 = p2[2]
	t1 = min(r1, r2)
	t2 = max(r1, r2)
	(r2, r1) = (t2, t1)
	if s >= r1 + r2:
		rng = [ceil(s - (r1 + r2)), floor(s + (r1 + r2))]
	elif s <= r2 - r1:
		if s == 0:
			if r1 != r2:
				rng = [r2 - r1, r1 + r2]
			else:
				rng = [0, 0]
		else:
			rng = [ceil(r2 - r1 - s), floor(r2 + r1 + s)]
	else:
		rng = [0, floor(r1 + r2 + s)]
	update(l, rng[0], rng[1], 1)
(n, q) = map(int, input().split())
ml = [0] * 1000001
d = [0] * 1000002
sideL = []
for _ in range(0, n):
	(x, y, r) = map(int, input().split())
	el = [x, y, r]
	sideL.append(el)
	for i in range(_ - 1, -1, -1):
		circheck(el, sideL[i], d)
makeArray(ml, d)
for _ in range(0, q):
	k = int(input())
	print(ml[k])


from math import *

def dist(a, b, c, d):
	return sqrt(pow(a - b, 2) + pow(c - d, 2))
(n, q) = map(int, input().split())
x = []
y = []
r = []
i = 0
mini = []
maxm = []
k = 0
m = 0
while i < n:
	(a, b, c) = map(int, input().split())
	x.append(a)
	y.append(b)
	r.append(c)
	i = i + 1
i = 0
while i < n:
	j = i + 1
	while j < n:
		c = dist(x[i], x[j], y[i], y[j])
		if c + r[j] <= r[i]:
			mini.append(ceil(r[i] - r[j] - c))
			maxm.append(floor(c + r[i] + r[j]))
		elif c + r[i] <= r[j]:
			mini.append(ceil(r[j] - r[i] - c))
			maxm.append(floor(c + r[i] + r[j]))
		elif c <= r[i] + r[j]:
			mini.append(0)
			maxm.append(floor(c + r[i] + r[j]))
		else:
			mini.append(ceil(c - r[i] - r[j]))
			maxm.append(floor(c + r[i] + r[j]))
		if m < maxm[k]:
			m = maxm[k]
		k = k + 1
		j = j + 1
	i = i + 1
N = [0 for i in range(m + 2)]
i = 0
while i < n * (n - 1) / 2:
	N[mini[i]] = N[mini[i]] + 1
	N[maxm[i] + 1] = N[maxm[i] + 1] - 1
	i = i + 1
i = 1
while i < m + 2:
	N[i] = N[i] + N[i - 1]
	i = i + 1
i = 0
while i < q:
	k = int(input())
	if k <= m:
		print(N[k])
	else:
		print(0)
	i = i + 1


import math

class cl:

	def __init__(self, a, b, cc):
		self.x = a
		self.y = b
		self.r = cc
(n, q) = map(int, input().split())
v = []
c = [0 for i in range(1000005)]
for i in range(n):
	(a, b, cc) = map(int, input().split())
	k = cl(a, b, cc)
	v.append(k)
	for j in range(i):
		e = False
		if v[i].r < v[j].r:
			e = True
			t = v[i]
			v[i] = v[j]
			v[j] = t
		d = math.sqrt((v[i].x - v[j].x) ** 2 + (v[i].y - v[j].y) ** 2)
		if v[i].r + v[j].r <= d:
			mn = math.ceil(d - v[i].r - v[j].r)
			mx = math.floor(d + v[i].r + v[j].r)
			if mn < 1000001:
				c[mn] += 1
			if mx < 1000001:
				c[mx + 1] -= 1
		elif v[i].r >= d + v[j].r:
			mn = math.ceil(v[i].r - d - v[j].r)
			mx = math.floor(v[i].r + d + v[j].r)
			if mn < 1000001:
				c[mn] += 1
			if mx < 1000001:
				c[mx + 1] -= 1
		elif v[i].r + v[j].r >= d:
			mx = math.floor(d + v[i].r + v[j].r)
			c[0] += 1
			if mx < 1000001:
				c[mx + 1] -= 1
		if e:
			t = v[i]
			v[i] = v[j]
			v[j] = t
x = 0
for i in range(1000001):
	x += c[i]
	c[i] = x
for i in range(q):
	y = int(input())
	print(c[y])


import math
(n, q) = map(int, input().split())
circles = []
for i in range(n):
	circles.append(tuple(map(int, input().split())))
karr = [int(input()) for i in range(q)]
numk = [0 for i in range(10000001)]
(i, j) = (0, 0)
for i in range(len(circles)):
	for j in range(i):
		xdiff = circles[i][0] - circles[j][0]
		ydiff = circles[i][1] - circles[j][1]
		d = math.sqrt(xdiff * xdiff + ydiff * ydiff)
		dsq = xdiff * xdiff + ydiff * ydiff
		maxd = int(d + circles[i][2] + circles[j][2])
		if dsq > (circles[i][2] + circles[j][2]) ** 2:
			mind = int(math.ceil(d - circles[i][2] - circles[j][2]))
		elif dsq >= (max(circles[i][2], circles[j][2]) - min(circles[i][2], circles[j][2])) ** 2 and dsq <= (circles[i][2] + circles[j][2]) ** 2:
			mind = 0
		else:
			mind = int(math.ceil(max(circles[i][2], circles[j][2]) - min(circles[i][2], circles[j][2]) - d))
		numk[mind] += 1
		numk[maxd + 1] -= 1
csum = 0
for i in range(len(numk)):
	t = numk[i]
	numk[i] += csum
	csum += t
for i in karr:
	print(numk[i])


from collections import namedtuple
circle = namedtuple('circle', ['x', 'y', 'r'])
(N, Q) = map(int, input().strip().split())
circle_list = []
for _ in range(N):
	(x, y, r) = map(int, input().strip().split())
	circle_list.append(circle(x=x, y=y, r=r))
from math import ceil, floor, sqrt

def dist_bw_centres(circle1, circle2):
	return sqrt((circle1.x - circle2.x) ** 2 + (circle1.y - circle2.y) ** 2)

def min_max_dist(circle1, circle2):
	d_centres = dist_bw_centres(circle1, circle2)
	(mn, mx) = (d_centres - circle1.r - circle2.r, d_centres + circle1.r + circle2.r)
	if mn < 0:
		mn = abs(circle2.r - circle1.r) - d_centres if abs(circle2.r - circle1.r) - d_centres > 0 else 0
	return (ceil(mn), floor(mx))
possible = [0] * 1000000
for (index, circle1) in enumerate(circle_list[:-1]):
	for circle2 in circle_list[index + 1:]:
		(mn, mx) = min_max_dist(circle1, circle2)
		possible[mn] += 1
		possible[mx + 1] -= 1
for i in range(1, len(possible)):
	possible[i] += possible[i - 1]
for q in range(Q):
	K = int(input().strip())
	print(possible[K] if possible[K] > 0 else 0)


from math import ceil, floor

def cal_distance(a, b):
	d = ((b[0] - a[0]) * (b[0] - a[0]) + (b[1] - a[1]) * (b[1] - a[1])) ** 0.5
	if d >= a[2] + b[2]:
		return (ceil(d - a[2] - b[2]), floor(d + a[2] + b[2]))
	else:
		l = max(a[2], b[2]) - (d + min(a[2], b[2]))
		if l < 0:
			l = 0
		l = ceil(l)
		r = floor(d + a[2] + b[2])
		return (l, r)
(n, q) = [int(x) for x in input().split()]
circles = []
(l, r) = ([0] * 1000005, [0] * 1000005)
ans = [0] * 1000005
m = 0
for _ in range(n):
	circles.append([int(x) for x in input().split()])
for i in range(n):
	for j in range(i + 1, n):
		ranges = cal_distance(circles[i], circles[j])
		l[ranges[0]] += 1
		r[ranges[1]] += 1
		m = max(m, ranges[1])
ans[0] = l[0] - r[0]
for i in range(1, m + 1):
	ans[i] = ans[i - 1] + l[i] - r[i - 1]
for _ in range(q):
	x = int(input())
	print(ans[x])


import math
(n, q) = [int(x) for x in input().split()]
b = []
for x in range(n):
	a = [int(y) for y in input().split()]
	b.append(a)
i = []
for x in range(n - 1):
	o = b[x]
	r2 = o[2]
	for y in range(x + 1, n):
		p = b[y]
		r1 = p[2]
		z = math.sqrt(math.pow(o[0] - p[0], 2) + math.pow(o[1] - p[1], 2))
		if o != p:
			if z <= abs(r1 - r2):
				l = max(max(r1, r2) - z - min(r1, r2), 0)
				m = r1 + r2 + z
				i.append([l, m])
			else:
				l = max(z - r1 - r2, 0)
				m = z + r1 + r2
				i.append([l, m])
h = [0 for r in range(1000002)]
for w in i:
	t1 = int(math.ceil(w[0]))
	t2 = int(math.floor(w[1]))
	h[t1] = h[t1] + 1
	h[t2 + 1] = h[t2 + 1] - 1
for w1 in range(1, 1000002):
	h[w1] = h[w1] + h[w1 - 1]
for x in range(q):
	k = int(input())
	print(h[k])


from math import ceil, floor
(n, q) = map(int, input().split())
l = []
for i in range(n):
	(x, y, r) = map(int, input().split())
	l.append([x, y, r])
dis = []
for i in range(n - 1):
	for j in range(i + 1, n):
		k = ((l[i][0] - l[j][0]) ** 2 + (l[i][1] - l[j][1]) ** 2) ** 0.5
		k = round(k, 6)
		if k >= l[i][2] + l[j][2]:
			a = abs(ceil(k) - l[i][2] - l[j][2])
			b = abs(floor(k) + l[i][2] + l[j][2])
			if a == 0:
				dis.append([0, b])
			else:
				dis.append([a, b])
		elif k <= abs(l[i][2] - l[j][2]):
			mx = k + (l[i][2] + l[j][2])
			a = max(l[i][2], l[j][2])
			mn = 2 * a - mx
			dis.append([ceil(mn), floor(mx)])
		else:
			mx = floor(k) + l[i][2] + l[j][2]
			dis.append([0, mx])
total_range = len(dis)
m = -10 ** 10
ran = [0] * 10 ** 6
for i in range(total_range):
	m = max(m, dis[i][1])
	ran[dis[i][0]] += 1
	ran[dis[i][1] + 1] -= 1
for i in range(1, m + 1):
	ran[i] += ran[i - 1]
for i in range(q):
	key = int(input())
	if key > m:
		print(0)
	else:
		print(ran[key])


import math
(n, q) = map(int, input().split())
circles = []
for i in range(n):
	(x, y, r) = map(int, input().split())
	if [x, y, r] not in circles:
		circles.append([x, y, r])

def sdld(cir1, cir2):
	(maxr, minr) = (max(cir1[2], cir2[2]), min(cir1[2], cir2[2]))
	dist = ((cir1[0] - cir2[0]) ** 2 + (cir1[1] - cir2[1]) ** 2) ** 0.5
	if dist >= maxr + minr:
		sd = math.ceil(dist - maxr - minr)
		ld = math.floor(dist + maxr + minr)
	elif maxr - minr < dist < maxr + minr:
		sd = 0
		ld = math.floor(dist + maxr + minr)
	else:
		sd = math.ceil(maxr - dist - minr)
		ld = math.floor(dist + maxr + minr)
	return (sd, ld)
short = []
lon = []
for i in range(n - 1):
	for j in range(i + 1, n):
		short.append(sdld(circles[i], circles[j])[0])
		lon.append(sdld(circles[i], circles[j])[1])
store = [0] * 1000000
for i in short:
	store[i] += 1
for i in lon:
	store[i + 1] -= 1
for i in range(1, len(store)):
	store[i] += store[i - 1]
queries = []
for i in range(q):
	queries.append(int(input()))
for i in range(len(queries)):
	print(store[queries[i]])


import math
(n, q) = map(int, input().split())
A = list(list())
L = list()
U = list()
while n > 0:
	A.append(list(map(int, input().split())))
	n -= 1
for i in range(0, len(A) - 1):
	for j in range(i + 1, len(A)):
		(x1, x2, y1, y2, r1, r2) = (A[i][0], A[j][0], A[i][1], A[j][1], A[i][2], A[j][2])
		dx = x1 - x2
		dy = y1 - y2
		v = dx * dx + dy * dy
		ed = math.sqrt(v)
		if x1 == x2 and y1 == y2:
			L.append(abs(r1 - r2))
			U.append(r1 + r2)
		elif r1 >= ed + r2 or r2 >= ed + r1:
			if r1 > r2:
				L.append(math.ceil(r1 - (ed + r2)))
				U.append(math.floor(r1 + r2 + ed))
			else:
				L.append(math.ceil(r2 - (ed + r1)))
				U.append(math.floor(r1 + r2 + ed))
		else:
			L.append(max(0, math.ceil(ed - (r1 + r2))))
			U.append(math.floor(ed + (r1 + r2)))
A = [0] * 1000001
D = [0] * 1000001
for i in range(0, len(L)):
	D[L[i]] += 1
	D[U[i] + 1] -= 1
for i in range(0, len(A)):
	if i == 0:
		A[i] = D[i]
	else:
		A[i] = D[i] + A[i - 1]
while q > 0:
	xx = int(input())
	print(A[xx])
	q -= 1


import math
n = input().split()
lst = list(map(int, n))
(N, Q) = (lst[0], lst[1])
L = []
q = []

def ShortLongDist(x1, y1, r1, x2, y2, r2):
	R = [r1, r2]
	R.sort()
	C1C2 = ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5
	if C1C2 >= r1 + r2:
		sd = C1C2 - r1 - r2
		ld = C1C2 + r1 + r2
	elif C1C2 < abs(r1 - r2):
		sd = R[1] - C1C2 - R[0]
		ld = C1C2 + r1 + r2
	else:
		sd = 0
		ld = C1C2 + r1 + r2
	return (sd, ld)
for i in range(N):
	newlst = tuple(map(int, input().split()))
	L.append(newlst)
for i in range(Q):
	q.append(int(input()))
newlst_tuple = []
short_list = []
long_list = []
for i in range(N - 1):
	for j in range(i + 1, N):
		short_list.append(math.ceil(ShortLongDist(L[i][0], L[i][1], L[i][2], L[j][0], L[j][1], L[j][2])[0]))
		long_list.append(math.floor(ShortLongDist(L[i][0], L[i][1], L[i][2], L[j][0], L[j][1], L[j][2])[1]))
		newlst_tuple.append(ShortLongDist(L[i][0], L[i][1], L[i][2], L[j][0], L[j][1], L[j][2]))
Klist = [0] * 1000000
for i in short_list:
	Klist[i] += 1
for i in long_list:
	Klist[i + 1] += -1
for i in range(1, len(Klist)):
	Klist[i] += Klist[i - 1]
for i in range(len(q)):
	print(Klist[q[i]])


import math
lower_limit = [0] * 5000005
upper_limit = [0] * 5000005
circles = []
(no_of_circles, no_of_queries) = map(int, input().split())
for _ in range(no_of_circles):
	(x, y, radius) = map(int, input().split())
	circles.append((x, y, radius))
for i in range(no_of_circles):
	for j in range(i, no_of_circles):
		if i == j:
			continue
		(x1, y1, radius1) = circles[i]
		(x2, y2, radius2) = circles[j]
		distance_bw_centers = math.hypot(x2 - x1, y2 - y1)
		if x1 == x2 and y1 == y2:
			minimum_possible = abs(radius1 - radius2)
			maximum_possible = radius1 + radius2
		elif distance_bw_centers >= radius1 + radius2:
			minimum_possible = distance_bw_centers - radius1 - radius2
			maximum_possible = distance_bw_centers + radius1 + radius2
		elif distance_bw_centers + min(radius1, radius2) < max(radius1, radius2):
			minimum_possible = max(radius1, radius2) - distance_bw_centers - min(radius1, radius2)
			maximum_possible = radius1 + radius2 + distance_bw_centers
		elif distance_bw_centers + min(radius1, radius2) == max(radius1, radius2):
			minimum_possible = 0
			maximum_possible = 2 * max(radius1, radius2)
		else:
			minimum_possible = 0
			maximum_possible = distance_bw_centers + radius1 + radius2
		lower_limit[math.ceil(minimum_possible)] += 1
		upper_limit[int(maximum_possible)] += 1
for i in range(1, 5000005):
	lower_limit[i] += lower_limit[i - 1] - upper_limit[i - 1]
for query in range(no_of_queries):
	print(lower_limit[int(input())])


import math
from collections import Counter
import itertools

def getsum(BITTree, i):
	s = 0
	i = i + 1
	while i > 0:
		s += BITTree[i]
		i -= i & -i
	return s

def updatebit(BITTree, n, i, v):
	i += 1
	while i <= n:
		BITTree[i] += v
		i += i & -i

def construct(arr, n):
	BITTree = [0] * (n + 1)
	for i in range(n):
		updatebit(BITTree, n, i, arr[i])
	return BITTree
n = input().split()
n = list(map(int, n))
N = n[0]
Q = n[1]
circ = []
que = []
md = []
minm = []
maxm = []
ctr = [0] * 1000000
for i in range(0, N):
	a = input().split()
	a = list(map(int, a))
	circ.append(a)
for i in range(0, Q):
	n1 = int(input())
	que.append(n1)
for i in range(0, N):
	for j in range(i + 1, N):
		cendis = math.sqrt((circ[i][0] - circ[j][0]) ** 2 + (circ[i][1] - circ[j][1]) ** 2)
		radsum = circ[i][2] + circ[j][2]
		mn = cendis - radsum
		if cendis == 0:
			mn = abs(circ[i][2] - circ[j][2])
		if mn < 0:
			if circ[i][2] > circ[j][2] + cendis:
				mn = circ[i][2] - cendis - circ[j][2]
			elif circ[j][2] > circ[i][2] + cendis:
				mn = circ[j][2] - cendis - circ[i][2]
			else:
				mn = 0
		mx = cendis + radsum
		mn = math.ceil(mn)
		mx = math.floor(mx)
		ctr[mn] = ctr[mn] + 1
		ctr[mx + 1] = ctr[mx + 1] - 1
BITTree = construct(ctr, len(ctr))
for i in range(0, Q):
	res = getsum(BITTree, que[i])
	print(res)


(N, Q) = list(map(int, input().split()))
g = []
karray = [0 for z in range(10 ** 6 + 1)]
for i in range(N):
	(X, Y, R) = list(map(int, input().split()))
	g.append((X, Y, R))
for i in range(0, len(g) - 1):
	for j in range(i + 1, len(g)):
		(x1, y1, r1) = g[i]
		(x2, y2, r2) = g[j]
		c = ((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1)) ** 0.5
		if c >= r1 + r2:
			mini = c - r1 - r2
			maxi = c + r1 + r2
		elif c < r1 + r2 and c > abs(r1 - r2):
			mini = 0
			maxi = c + r1 + r2
		elif c == abs(r1 - r2):
			mini = 0
			maxi = c + r1 + r2
		elif c < abs(r1 - r2):
			mini = abs(r1 - r2) - c
			maxi = c + r1 + r2
		try:
			if mini == int(mini):
				karray[int(mini)] += 1
			else:
				karray[int(mini) + 1] += 1
		except:
			pass
		try:
			karray[int(maxi + 1)] -= 1
		except:
			pass
sum_arr = [karray[0]]
for w in range(1, len(karray)):
	sum_arr.append(sum_arr[-1] + karray[w])
for query in range(Q):
	que = int(input())
	print(sum_arr[que])


from math import ceil, floor
(n, q) = map(int, input().split())
l1 = []
l2 = []
r = []
a = [0] * 1000002
for i in range(n):
	(x, y, r1) = map(int, input().split())
	l1.append(x)
	l2.append(y)
	r.append(r1)
for i in range(n):
	for j in range(i + 1, n):
		z = ((l1[i] - l1[j]) ** 2 + (l2[i] - l2[j]) ** 2) ** 0.5
		if max(r[i], r[j]) > z + min(r[i], r[j]):
			mini = max(r[i], r[j]) - (z + min(r[i], r[j]))
			maxi = 2 * max(r[i], r[j]) - mini
		else:
			mini = z - (r[i] + r[j])
			if mini < 0:
				mini = 0
			maxi = z + (r[i] + r[j])
		a[ceil(mini)] += 1
		a[floor(maxi) + 1] -= 1
for i in range(1, 1000002):
	a[i] = a[i] + a[i - 1]
for m in range(q):
	k = int(input())
	print(a[k])


import numpy as np
import math
(n, q) = [int(i) for i in input().strip().split(' ')]
cir = []
dp = np.zeros(10 ** 6 + 3)
for i in range(n):
	(x, y, r) = [int(i) for i in input().strip().split(' ')]
	cir.append([x, y, r])
for c1 in range(n):
	for c2 in range(c1, n):
		if c1 != c2:
			d = ((cir[c1][0] - cir[c2][0]) ** 2 + (cir[c1][1] - cir[c2][1]) ** 2) ** 0.5
			r1 = cir[c1][2]
			r2 = cir[c2][2]
			if d >= r1 + r2:
				min_dis = d - r1 - r2
				max_dis = d + r1 + r2
			elif d < r1 + r2 and d > math.fabs(r1 - r2):
				min_dis = 0
				max_dis = d + r1 + r2
			elif r1 > r2:
				min_dis = r1 - d - r2
				max_dis = r1 + r2 + d
			else:
				min_dis = r2 - d - r1
				max_dis = r2 + r1 + d
			lb = int(math.ceil(min_dis))
			ub = int(math.floor(max_dis))
			dp[lb] = dp[lb] + 1
			dp[ub + 1] = dp[ub + 1] - 1
for i in range(1, 10 ** 6 + 2):
	dp[i] = dp[i - 1] + dp[i]
for i in range(q):
	k = int(input())
	print(int(dp[k]))


import math

def distcenter(x1, y1, x2, y2):
	return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5

def minimumDist(x1, y1, r1, x2, y2, r2):
	centerDist = distcenter(x1, y1, x2, y2)
	if centerDist <= r1 + r2 and max(r1, r2) - min(r1, r2) < centerDist:
		return 0
	else:
		return 2 * max(centerDist, r1, r2) - (centerDist + r1 + r2)

def maximumDist(x1, y1, r1, x2, y2, r2):
	centerDist = distcenter(x1, y1, x2, y2)
	return centerDist + r1 + r2

def mainfunction(array1, array2):
	mindist = minimumDist(array1[0], array1[1], array1[2], array2[0], array2[1], array2[2])
	maxdist = maximumDist(array1[0], array1[1], array1[2], array2[0], array2[1], array2[2])
	lowerrange.append(math.ceil(mindist))
	higherrange.append(math.floor(maxdist))

def pairmaker(array):
	qw = len(circles)
	for i in range(qw - 1):
		for j in range(i + 1, qw):
			mainfunction(circles[i], circles[j])
possibleranges = []
(n, q) = map(int, input().split())
circles = []
for _ in range(n):
	(x, y, r) = map(int, input().split())
	circles.append([x, y, r])
lowerrange = []
higherrange = []
pairmaker(circles)
biglist = [0] * 1000000
for i in lowerrange:
	biglist[i] += 1
for i in higherrange:
	biglist[i + 1] += -1
for i in range(1, 1000000):
	biglist[i] += biglist[i - 1]
for _ in range(q):
	query = int(input().strip())
	print(biglist[query])


import math
dl = [0] * 5000001
dr = [0] * 5000001

def add_new_range(mn, mx):
	dl[math.ceil(mn)] += 1
	dr[int(mx)] += 1

def solve():
	for i in range(1, 5000001):
		dl[i] += dl[i - 1] - dr[i - 1]

def find_dist(c1, c2):
	(x1, y1, r1) = c1
	(x2, y2, r2) = c2
	ds = math.hypot(x2 - x1, y2 - y1)
	if x1 == x2 and y1 == y2:
		mn = abs(r1 - r2)
		mx = r1 + r2
	elif ds >= r1 + r2:
		mn = ds - r1 - r2
		mx = ds + r1 + r2
	elif ds + min(r1, r2) < max(r1, r2):
		mn = max(r1, r2) - ds - min(r1, r2)
		mx = r1 + r2 + ds
	elif ds + min(r1, r2) == max(r1, r2):
		mn = 0
		mx = 2 * max(r1, r2)
	else:
		mn = 0
		mx = ds + r1 + r2
	add_new_range(mn, mx)
(no_circles, no_queries) = map(int, input().split())
circles = []
for _ in range(no_circles):
	(x, y, radius) = map(int, input().split())
	circles.append((x, y, radius))
pairs_of_circles = []
distance_ranges = []
for i in range(no_circles):
	for j in range(i, no_circles):
		if i == j:
			continue
		find_dist(circles[i], circles[j])
solve()
for query in range(no_queries):
	q = int(input())
	count = dl[q]
	print(count)


from math import sqrt
x = []
y = []
r = []
(N, Q) = map(int, input().split())
for i in range(N):
	(a, b, c) = map(int, input().split())
	x.append(a)
	y.append(b)
	r.append(c)
nos = 0
lowerdis = []
upperdis = []
for i in range(N):
	for j in range(i + 1, N):
		minimum = 0
		distance = sqrt((x[i] - x[j]) ** 2 + (y[i] - y[j]) ** 2)
		maximum = 0
		if distance > r[i] + r[j]:
			minimum = distance - r[i] - r[j]
			maximum = distance + r[i] + r[j]
		elif distance < abs(r[i] - r[j]):
			minimum = abs(r[i] - r[j]) - distance
			maximum = r[i] + r[j] + distance
		else:
			minimum = 0
			maximum = distance + r[i] + r[j]
		upperdis.append(maximum)
		nos += 1
		lowerdis.append(minimum)
lowerdis.sort()
i = 0
upperdis.sort()
j = 0
count = 0
ansarray = [0] * 1000001
for index in range(1000001):
	if i < nos:
		while index >= lowerdis[i]:
			i = i + 1
			count = count + 1
			if i == nos:
				break
	while index > upperdis[j]:
		count = count - 1
		j = j + 1
		if j == nos:
			break
	ansarray[index] = count
	if j >= nos:
		break
for i in range(Q):
	print(ansarray[int(input())])


import math

def dist(onex, oney, twox, twoy):
	return math.sqrt((onex - twox) ** 2 + (oney - twoy) ** 2)
(n, q) = [int(i) for i in input().split()]
(x, y, r, ans) = ([], [], [], 0)
for _ in range(n):
	l = [float(i) for i in input().split()]
	x.append(l[0])
	y.append(l[1])
	r.append(l[2])
dp = [0 for i in range(1111110)]
for i in range(0, n):
	for j in range(i + 1, n):
		c1c2 = dist(x[i], y[i], x[j], y[j])
		f = [c1c2, r[i], r[j]]
		f.sort()
		minm = (f[2] - f[1] - f[0]) * (f[2] - f[1] - f[0] > 0)
		maxm = c1c2 + r[i] + r[j]
		dp[math.ceil(minm)] += 1
		dp[math.floor(maxm) + 1] -= 1
for i in range(1, 1000001):
	dp[i] = dp[i] + dp[i - 1]
for _ in range(q):
	k = int(input())
	print(dp[k])


from math import floor
from math import ceil
from math import sqrt
(n, q) = list(map(int, input().split()))
x = []
y = []
r = []
dist = []
for i in range(n):
	(a, b, c) = list(map(int, input().split()))
	x.append(a)
	y.append(b)
	r.append(c)
for i in range(10000001):
	dist.append(0)
for i in range(n - 1):
	for j in range(i + 1, n):
		temp = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])
		if temp >= pow(r[i] + r[j], 2):
			if ceil(sqrt(temp) - (r[i] + r[j])) < 1000001:
				dist[ceil(sqrt(temp) - (r[i] + r[j]))] += 1
			if floor(sqrt(temp) + (r[i] + r[j])) + 1 < 1000001:
				dist[floor(sqrt(temp) + (r[i] + r[j])) + 1] -= 1
		elif temp >= pow(r[i] - r[j], 2):
			dist[0] += 1
			if floor(sqrt(temp) + (r[i] + r[j])) + 1 < 1000001:
				dist[floor(sqrt(temp) + (r[i] + r[j])) + 1] -= 1
		else:
			(max, min) = (r[j], r[j])
			if r[i] >= r[j]:
				max = r[i]
			else:
				min = r[i]
			if ceil(max - sqrt(temp) - min) < 1000001:
				dist[ceil(max - sqrt(temp) - min)] += 1
			if floor(r[i] + r[j] + sqrt(temp)) + 1 < 1000001:
				dist[floor(r[i] + r[j] + sqrt(temp) + 1)] -= 1
for i in range(1, 1000001):
	dist[i] += dist[i - 1]
for i in range(q):
	k2 = int(input())
	print(dist[k2])


from math import sqrt, ceil, floor
(n, q) = map(int, input().split())
circle = []
ans = [0 for i in range(0, 10 ** 6 + 2)]
for _ in range(n):
	circle.append(tuple(map(int, input().split())))
for i in range(0, n - 1):
	for j in range(i + 1, n):
		m1 = 0
		m2 = 0
		if circle[i][0] == circle[j][0] and circle[i][1] == circle[j][1]:
			if circle[i][2] == circle[j][2]:
				m1 = 0
				m2 = 2 * circle[i][2]
			elif circle[i][2] > circle[j][2]:
				m1 = circle[i][2] - circle[j][2]
				m2 = circle[i][2] + circle[j][2]
			else:
				m1 = -circle[i][2] + circle[j][2]
				m2 = circle[i][2] + circle[j][2]
		else:
			dist = (circle[i][0] - circle[j][0]) ** 2 + (circle[i][1] - circle[j][1]) ** 2
			if dist == (circle[i][2] - circle[j][2]) ** 2:
				m1 = 0
				if circle[i][2] > circle[j][2]:
					m2 = 2 * circle[i][2]
				else:
					m2 = 2 * circle[j][2]
			elif (circle[j][2] - circle[i][2]) ** 2 > dist:
				if circle[j][2] > circle[i][2]:
					m1 = circle[j][2] - int(floor(sqrt(dist))) - circle[i][2]
					m2 = circle[j][2] + int(floor(sqrt(dist))) + circle[i][2]
				else:
					m1 = circle[i][2] - int(floor(sqrt(dist))) - circle[j][2]
					m2 = circle[i][2] + int(floor(sqrt(dist))) + circle[j][2]
			elif (circle[i][2] + circle[j][2]) ** 2 == dist:
				m1 = 0
				m2 = 2 * circle[i][2] + 2 * circle[j][2]
			elif (circle[i][2] + circle[j][2]) ** 2 > dist:
				m1 = 0
				m2 = int(floor(sqrt(dist))) + circle[i][2] + circle[j][2]
			elif (circle[i][2] + circle[j][2]) ** 2 < dist:
				m1 = int(ceil(sqrt(dist))) - circle[i][2] - circle[j][2]
				m2 = int(floor(sqrt(dist))) + circle[i][2] + circle[j][2]
		if m2 > 10 ** 6:
			m2 = 10 ** 6
		if m1 < 0:
			m1 = 0
		ans[m1] += 1
		ans[m2 + 1] -= 1
for i in range(1, 10 ** 6 + 1):
	ans[i] += ans[i - 1]
for _ in range(q):
	k = int(input())
	print(ans[k])


import math
(n, q) = map(int, input().split())
x = []
y = []
r = []
r_min = []
r_max = []
for j in range(n):
	(x1, y1, z1) = map(int, input().split())
	x.append(x1)
	y.append(y1)
	r.append(z1)
n = len(x)
for j in range(n - 1):
	for k in range(j + 1, n):
		d = ((x[j] - x[k]) ** 2 + (y[j] - y[k]) ** 2) ** 0.5
		if r[j] >= d + r[k]:
			r_min.append(r[j] - d - r[k])
			r_max.append(r[j] + d + r[k])
		elif r[k] >= d + r[j]:
			r_min.append(r[k] - d - r[j])
			r_max.append(r[k] + d + r[j])
		else:
			r1 = d + r[j] + r[k]
			r2 = d - r[j] - r[k]
			r_min.append(r2)
			r_max.append(r1)
co = [0] * (10 ** 6 + 2)
for u in range(len(r_min)):
	co[max(0, math.ceil(r_min[u]))] += 1
	co[max(0, math.floor(r_max[u]) + 1)] -= 1
count = [0] * (10 ** 6 + 2)
for u in range(len(co)):
	if u > 0:
		count[u] = co[u] + count[u - 1]
	else:
		count[u] = co[u]
for _ in range(q):
	k = int(input())
	print(count[k])


import math
(N, Q) = map(int, input().strip().split(' '))
lst = []
Min = 0
Max = 0
mm = 0
arr = [0] * 1000000

def dist(a, b):
	return math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)
for i in range(N):
	z = list(map(int, input().strip().split(' ')))
	lst.append(z)
for j in range(N - 1):
	for k in range(j + 1, N):
		d = dist(lst[j], lst[k])
		if d + lst[k][2] + lst[j][2] > mm:
			mm = int(d + lst[k][2] + lst[j][2])
		arr[int(d + lst[k][2] + lst[j][2]) + 1] = arr[int(d + lst[k][2] + lst[j][2]) + 1] - 1
		if lst[j][2] >= lst[k][2]:
			Max = lst[j][2]
			Min = lst[k][2]
		else:
			Min = lst[j][2]
			Max = lst[k][2]
		if d == 0:
			if Max - Min - int(Max - Min) == 0:
				arr[int(Max - Min)] = arr[int(Max - Min)] + 1
			else:
				arr[int(Max - Min) + 1] = arr[int(Max - Min) + 1] + 1
			continue
		elif d == Max - Min:
			arr[0] = arr[0] + 1
			continue
		elif d + Min < Max:
			m = Max - d - Min
			if m - int(m) == 0:
				arr[int(m)] = arr[int(m)] + 1
			else:
				arr[int(m) + 1] = arr[int(m) + 1] + 1
			continue
		elif d < lst[j][2] + lst[k][2] and d != Max - Min:
			arr[0] = arr[0] + 1
			continue
		elif d == lst[j][2] + lst[k][2]:
			arr[0] = arr[0] + 1
			continue
		elif d > lst[j][2] + lst[k][2]:
			if d - lst[j][2] - lst[k][2] - int(d - lst[j][2] - lst[k][2]) == 0:
				arr[int(d - lst[j][2] - lst[k][2])] = arr[int(d - lst[j][2] - lst[k][2])] + 1
			else:
				arr[int(d - lst[j][2] - lst[k][2]) + 1] = arr[int(d - lst[j][2] - lst[k][2]) + 1] + 1
			continue
for i in range(1, mm + 1):
	arr[i] = arr[i - 1] + arr[i]
for i in range(Q):
	D = int(input())
	if D <= mm:
		print(arr[D])
	else:
		print(0)


from math import sqrt
from math import ceil
from math import floor

def get_sum(BIT, i):
	s = 0
	i = i + 1
	while i > 0:
		s += BIT[i]
		i -= i & -i
	return s

def up_date(BIT, n, i, v):
	i += 1
	while i <= n:
		BIT[i] += v
		i += i & -i
(n, q) = [int(xdd) for xdd in input().split()]
l = []
for i in range(n):
	(x, y, r) = [int(xd) for xd in input().split()]
	l.append([x, y, r])
k_list = []
for j in range(q):
	k = int(input())
	k_list.append(k)
a = 0
mil = []
while a < n:
	b = a + 1
	while b < n:
		dis = sqrt((l[a][0] - l[b][0]) ** 2 + (l[a][1] - l[b][1]) ** 2)
		mini = dis - (l[a][2] + l[b][2])
		if dis == 0:
			mini = abs(l[a][2] - l[b][2])
		if mini < 0:
			if l[a][2] > l[b][2] + dis:
				mini = l[a][2] - dis - l[b][2]
			elif l[b][2] > l[a][2] + dis:
				mini = l[b][2] - dis - l[a][2]
			else:
				mini = 0
		maxi = dis + (l[a][2] + l[b][2])
		mil.append((mini, maxi))
		b += 1
	a += 1
y = len(mil)
w = 0
key = 0
zz = 1000001
arr = [0] * zz
while w < y:
	g = ceil(mil[w][0])
	h = floor(mil[w][1])
	val = 1
	up_date(arr, zz, g, val)
	up_date(arr, zz, h + 1, -1 * val)
	w += 1
for k in k_list:
	print(get_sum(arr, k))


import heapq
from math import sqrt

def main():
	(N, Q) = map(int, input().split())
	circles = list()
	for _ in range(N):
		(x, y, r) = map(int, input().split())
		circles.append((x, y, r))
	dist_ranges = list()
	for i in range(N - 1):
		(x1, y1, r1) = circles[i]
		for j in range(i + 1, N):
			(x2, y2, r2) = circles[j]
			dist_center = sqrt((y2 - y1) ** 2 + (x2 - x1) ** 2)
			max_r = max(r1, r2)
			min_r = min(r1, r2)
			if dist_center <= max_r:
				tmp = max_r - min_r - dist_center
				low_range = max(0, tmp)
				high_range = max(abs(tmp), 2 * max_r - tmp)
			else:
				tmp = dist_center - r1 - r2
				low_range = max(0, tmp)
				high_range = max(abs(tmp), dist_center + r1 + r2)
			dist_ranges.append((low_range, high_range))
	dist_ranges.sort()
	K = [int(input()) for _ in range(Q)]
	min_K = min(K)
	max_K = max(K)
	memo = [0 for _ in range(min_K, max_K + 1)]
	heap = list()
	j = 0
	pop = heapq.heappop
	push = heapq.heappush
	for i in range(len(memo)):
		i += min_K
		while j < len(dist_ranges) and i >= dist_ranges[j][0]:
			push(heap, dist_ranges[j][1])
			j += 1
		while len(heap) > 0 and heap[0] < i:
			pop(heap)
		memo[i - min_K] = len(heap)
	for k in K:
		print(memo[k - min_K])
main()


import math
from itertools import accumulate
(n, q) = map(int, input().split())
Matrix = [[0 for o in range(3)] for h in range(n)]

def cumulativeSum(input):
	return list(accumulate(input))
min = 0
max = 0
for e in range(n):
	(x, y, r) = map(int, input().split())
	Matrix[e][0] = x
	Matrix[e][1] = y
	Matrix[e][2] = r
x = [0] * 1000000
ar = [0] * 1000000
for i in range(n):
	for j in range(i + 1, n):
		d = math.sqrt((Matrix[i][0] - Matrix[j][0]) ** 2 + (Matrix[i][1] - Matrix[j][1]) ** 2)
		r1 = Matrix[i][2]
		r2 = Matrix[j][2]
		if d >= r1 + r2:
			min = math.ceil(d - r1 - r2)
			max = math.floor(d + r1 + r2)
		else:
			if r1 > r2:
				if r1 > d + r2:
					min = math.ceil(r1 - d - r2)
					max = math.floor(r1 + d + r2)
				else:
					min = 0
					max = math.floor(r1 + r2 + d)
			if r2 >= r1:
				if r2 > d + r1:
					min = math.ceil(r2 - d - r1)
					max = math.floor(r1 + d + r2)
				else:
					min = 0
					max = math.floor(r1 + r2 + d)
		x[min] += 1
		x[max + 1] -= 1
ar = cumulativeSum(x)
for c in range(q):
	k = int(input())
	print(ar[k])


import math

def add(arr, N, lo, hi, val):
	arr[lo] += val
	if hi != N - 1:
		arr[hi + 1] -= val

def updateArray(arr, N):
	for i in range(1, N):
		arr[i] += arr[i - 1]
cache = []
(n, q) = [int(x) for x in input().split()]
c = []
for i in range(n):
	c.append([int(x) for x in input().split()])
ks = 1000000
kvals = [0 for i in range(ks)]
for x in range(n):
	for y in range(x + 1, n):
		a = c[x]
		b = c[y]
		r1 = a[2]
		r2 = b[2]
		z = math.sqrt(math.pow(a[0] - b[0], 2) + math.pow(a[1] - b[1], 2))
		if a != b:
			if z < r1 + r2 and z <= abs(r1 - r2):
				add(kvals, ks, max(0, math.ceil(max(r1, r2) - z - min(r1, r2))), math.floor(r1 + r2 + z), 1)
			else:
				add(kvals, ks, max(0, math.ceil(z - r1 - r2)), math.floor(z + r1 + r2), 1)
del n
del c
updateArray(kvals, ks)
for i in range(q):
	query = int(input())
	print(kvals[query])


import math
(n, q) = map(int, input().split(' '))
(x, y, r, a) = ([], [], [], [])
for i in range(n):
	(x1, y1, r1) = map(int, input().split(' '))
	x.append(x1)
	y.append(y1)
	r.append(r1)
for i in range(1000005):
	a.append(0)
for i in range(n - 1):
	for j in range(i + 1, n):
		d1 = ((x[i] - x[j]) ** 2 + (y[i] - y[j]) ** 2) ** 0.5
		m1 = d1 + r[i] + r[j]
		if d1 + min(r[i], r[j]) < max(r[i], r[j]):
			m2 = max(r[i], r[j]) - d1 - min(r[i], r[j])
		else:
			m2 = d1 - r[i] - r[j]
		m1 = int(m1)
		m2 = int(math.ceil(m2))
		m2 = max(m2, 0)
		a[m2] += 1
		a[m1 + 1] -= 1
for i in range(1, 1000005):
	a[i] += a[i - 1]
for i in range(q):
	ks = input()
	k = int(ks)
	print(a[k])


import math
n = [int(x) for x in input().split()]
g = []
arr = []
for i in range(n[0]):
	c = [int(x) for x in input().split()]
	g.append(c)
for h in range(10 ** 6 + 1):
	arr.append(0)
for j in range(len(g)):
	for k in range(j + 1, len(g)):
		z = ((g[j][0] - g[k][0]) ** 2 + (g[j][1] - g[k][1]) ** 2) ** 0.5
		if z < g[j][2] + g[k][2] and z <= abs(g[j][2] - g[k][2]):
			max_dis = z + min(g[j][2], g[k][2]) + max(g[j][2], g[k][2])
			min_dis = max(max(g[j][2], g[k][2]) - (z + min(g[j][2], g[k][2])), 0)
		else:
			max_dis = z + g[j][2] + g[k][2]
			min_dis = max(z - (g[j][2] + g[k][2]), 0)
		hi = math.floor(max_dis)
		lo = math.ceil(min_dis)
		arr[hi + 1] = arr[hi + 1] - 1
		arr[lo] = arr[lo] + 1
for i in range(1, len(arr)):
	arr[i] += arr[i - 1]
for i in range(n[1]):
	x = int(input())
	print(arr[x])


import math
import sys
import bisect
input_str = sys.stdin.read()
data = [int(x) for x in input_str.split()]
n = data[0]
q = data[1]
CX = data[2:-q:3]
CY = data[3:-q:3]
CR = data[4:-q:3]
qu = data[-q:]
leftEnds = []
rightEnds = []
for i in range(n):
	for j in range(i + 1, n):
		d = math.sqrt((CX[i] - CX[j]) * (CX[i] - CX[j]) + (CY[i] - CY[j]) * (CY[i] - CY[j]))
		maxDistance = d + CR[i] + CR[j]
		if d > CR[i] + CR[j]:
			minDistance = d - CR[i] - CR[j]
		elif CR[i] > d + CR[j]:
			minDistance = CR[i] - d - CR[j]
		elif CR[j] > d + CR[i]:
			minDistance = CR[j] - d - CR[i]
		else:
			minDistance = 0
		leftEnds.append(minDistance)
		rightEnds.append(maxDistance)
leftEnds.sort()
rightEnds.sort()
for i in range(q):
	k = qu[i]
	print(bisect.bisect_right(leftEnds, k) - bisect.bisect_left(rightEnds, k))