|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||256 MB||3||2||2||66.667%|
The year is 2211. Very New York is a city on Mars. The streets of the city make up a perfect grid. Each intersection in the city can be specified using a pair $(x,y)$ of integers. The distance between two intersections $(x_1,y_1)$ and $(x_2,y_2)$ equals $|x_1-x_2| + |y_1-y_2|$.
An investor is interested in building a hotel in the city. Since hotel owners love to advertise hotels using phrases of the form "150 restaurants within half a mile", the investor wants to learn the number of restaurants within a specific distance from each of the prospective locations.
The first line contains $R$, the number of restaurants in the city ($0 \le R \le 100\,000$). The next $R$ lines describe the coordinates of one restaurant each. Each of these lines contains two integers $x$ and $y$ ($1 \le x,y \le 1\,000\,000$).
The $(R+2)$-nd line contains one integer $Q$ which is the number of queries ($1 \le Q \le 100\,000$). The next $Q$ lines contain one query each. Each query consists of a triple of integers $x$, $y$, and $d$ ($1 \le x, y, d \le 1\,000\,000$).
The output should consist of $Q$ lines, each containing a single integer. The $i$-th line should contain the answer to the $i$-th query $(x,y,d)$: the number of restaurants at distance at most $d$ from $(x,y)$.
3 2 2 3 1 4 1 2 3 2 1 4 2 1
5 3 2 3 6 4 6 2 4 4 6 2 4 4 2 3 4 3