시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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)$.

예제 입력 1

3
2 2
3 1
4 1
2
3 2 1
4 2 1

예제 출력 1

2
1

예제 입력 2

5
3 2
3 6
4 6
2 4
4 6
2
4 4 2
3 4 3

예제 출력 2

3
5