19341번 - Very New York 다국어

문제

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)$.

제한

힌트