Считаем звезды
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Молодой ученый-астроном из МИСИС Виталий Олегович занимается исследованием звезд в космическом пространстве. Для своих исследований он создал модель, в которой проверяет различные гипотезы. Для очередного исследования ему понадобилась помощь программистов. Дело в том, что ему необходимо эффективно определять количество звезд внутри сферических областей пространства. Помогите молодому ученому с его задачей!

Входные данные

В первой строке через пробел заданы два целых числа $$$n$$$ и $$$q$$$ — количество звезд в модели Виталия Олеговича и количество запросов, $$$1 \le n, q \le 10^5$$$.

В следующих $$$n$$$ строках заданы координаты звезд. В каждой строке через пробел даны три целых числа $$$x, \ y, \ z$$$ — координаты очередной звезды в трехмерном пространстве, $$$1 \le x, y, z \le 10^6$$$.

Известно, что координаты всех $$$n$$$ звезд Виталий Олегович сгенерировал для своей модели так, что они являются независимыми случайными величинами с целочисленным равномерным распределением в диапазоне от $$$1$$$ до $$$10^6$$$. То есть каждая звезда с одинаковой вероятностью может получить любые целочисленные координаты $$$x, y, z$$$ с ограничениями $$$1 \le x, y, z \le 10^6$$$. При этом, разные звезды могли получить одинаковые координаты.

В следующих $$$q$$$ строках заданы запросы, ответы на которые Виталий Олегович хочет получить. В каждой строке через пробел даны четыре целых числа $$$x, \ y, \ z, \ r$$$ — координаты центра и радиус сферы, для которой нужно посчитать количество звезд лежащих строго внутри этой сферы, $$$1 \le x, y, z \le 10^6$$$, $$$1 \le r \le \bold{10^5}$$$.

Выходные данные

На каждый из $$$q$$$ запросов выведите в отдельной строке единственное целое число — количество звезд, которые лежат строго внутри очередной сферы.

Пример

Входные данные

    1 3142 18468 6335142 18468 6335 1100 18468 6335 42100 18468 6335 43

Выходные данные

    1
    0
    1