원 안의 점 개수 쿼리

고정된 N개의 점에 대해 M개의 원 질의가 주어질 때, 각 원 안이나 원주 위에 있는 점의 개수를 세어 출력한다.

어려움9기하분할 정복정렬시뮬레이션아직 제출이 없습니다시간 제한8초메모리 제한512 MB

문제

2차원 좌표 평면에 점 NN개가 놓여 있다. 다음 쿼리를 처리하는 프로그램을 작성하시오.

  • x y r: 중심이 (x,y)(x, y)이고 반지름이 rr인 원의 내부에 있는 점의 개수를 출력한다. 원의 둘레 위에 있는 점도 내부에 있는 점으로 센다.

즉, 점 (a,b)(a, b)(ax)2+(by)2r2(a - x)^2 + (b - y)^2 \le r^2을 만족할 때 답에 포함된다.

같은 좌표에 점이 둘 이상 놓여 있을 수 있고, 이때는 겹친 점을 모두 따로 센다. 쿼리는 점을 추가하거나 지우지 않으므로 처리 순서가 답에 영향을 주지 않는다.

입력

첫째 줄에 점의 개수 NN (1N1000001 \le N \le 100\,000)이 주어진다.

둘째 줄부터 NN개의 줄에 각 점의 좌표 xxyy가 공백으로 구분되어 주어진다 (0x,y10000000 \le x, y \le 1\,000\,000).

다음 줄에 쿼리의 개수 MM (1M1000001 \le M \le 100\,000)이 주어진다.

다음 MM개의 줄에 쿼리 정보 xx, yy, rr이 공백으로 구분되어 주어진다 (0x,y10000000 \le x, y \le 1\,000\,000, 1r10000001 \le r \le 1\,000\,000).

입력으로 주어지는 모든 수는 정수다.

출력

쿼리마다 원 안에 있는 점의 개수를 한 줄에 하나씩, 입력에 주어진 순서대로 출력한다.