만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

교준이의 심부름꾼, 민제의 고충 ("Circle" Ver.)

시간 제한4초메모리 제한1024 MB

요약
서로 겹치지 않는 원들과 집들이 주어질 때, 각 질의마다 점에서 원을 건너는 횟수가 L 이하인 집들의 C 값 XOR을 구합니다.
난이도

어려움10점 중 9점

유형
트리, 분할 정복, 기하, 비트 연산
정답자
아직 제출이 없습니다

문제

민제는 교준이가 통치하는 도시, 강민시(市)에서 살고 있다.

2차원 평면인 이 도시에는 중심이 (Xi,Yi)(X_i, Y_i)이고 반지름이 RiR_i인 원이 NN개 있다. 어떤 두 원도 같은 점을 공유하지 않는다.

또한 강민시에는 민제네 집이 MM채 있다. ii번째 집의 위치는 (Ai,Bi)(A_i, B_i)이며, 이 집을 부수면 교준이는 행복도 CiC_i를 얻는다. 집의 위치나 행복도는 서로 같을 수 있으나, 어떤 집도 원 위에 있지 않다.

행복도의 정의는 조금 특이하다. 어떤 집도 부숴지지 않았다면 교준이의 행복도는 00이다. 행복도가 33인 집과 66인 집이 부숴졌다면 교준이는 3⊕6=53 \oplus 6 = 5의 행복도를 얻는다. 즉, 행복도가 c1,c2,⋯ ,ckc_1, c_2, \cdots, c_k인 집 kk채가 부숴졌다면 교준이가 얻는 총 행복도는 c1⊕c2⊕⋯⊕ckc_1 \oplus c_2 \oplus \cdots \oplus c_k다. 이때 ⊕\oplus는 배타적 논리합(XOR)을 나타낸다.

민제네 집은 미관상 좋지 못하다. 강민시장 교준이는 강민시를 현대도시로 발전시키려면 민제네 집을 모두 부숴야 한다고 생각한다. 또한 교준이는 매우 악랄하기 때문에 민제에게 직접 집을 철거하라고 명령할 것이다.

교준이가 민제에게 "(x,y)(x, y)로 가서 거리 LL 이내에 있는 너네 집을 모두 부숴라."라고 명령하면, 민제는 (x,y)(x, y) 위치로 이동한 다음, 이 점으로부터 거리가 LL 이하인 모든 민제네 집을 직접 부순다. 이때 두 점 사이의 거리는 한 점에서 다른 점으로 이동하기 위해 지나야 하는 원의 최소 개수를 뜻한다. 점 (x,y)(x, y)가 원 위에 있지 않음은 항상 보장된다.

교준이는 다음과 같은 궁금증이 생겼다. 민제에게 "(U1,V1)(U_1, V_1)로 가서 거리 L1L_1 이내에 있는 너네 집을 모두 부숴라."라고 명령하고, 다시 "(U2,V2)(U_2, V_2)로 가서 거리 L2L_2 이내에 있는 너네 집을 모두 부숴라."라고 명령하고, 이런 식으로 총 KK차례 명령한다면 교준이가 얻는 총 행복도는 얼마일까?

민제는 수학을 못하므로, 교준이의 질문에 답해주는 프로그램이 필요하다.

QQ개의 궁금증은 서로 독립임에 유의하라. 또한 하나의 궁금증에서 민제는 같은 집을 두 번 이상 부수지 않는다.

입력

첫 번째 줄에는 원의 개수 NN, 민제네 집의 수 MM, 궁금증의 횟수 QQ가 공백으로 구분되어 주어진다.

두 번째 줄부터 NN개의 줄에 걸쳐 각 원의 정보 XiX_i, YiY_i, RiR_i가 공백으로 구분되어 주어진다.

(N+2)(N+2)번째 줄부터 MM개의 줄에 걸쳐 각 집의 정보 AiA_i, BiB_i, CiC_i가 공백으로 구분되어 주어진다.

(N+M+2)(N+M+2)번째 줄부터 QQ개의 궁금증이 주어진다. 하나의 궁금증은 여러 줄에 걸쳐 표현된다. 첫 줄에는 민제에게 내리는 명령의 횟수 KK가 주어지고, 이어지는 KK개의 줄에 각 명령의 UiU_i, ViV_i, LiL_i가 공백으로 구분되어 주어진다.

QQ개의 궁금증은 서로 독립이다. 또한 하나의 궁금증에서 민제는 같은 집을 두 번 이상 부수지 않는다.

출력

첫 번째 줄부터 QQ개의 줄에 걸쳐 각 궁금증에 대해 교준이가 얻는 행복도를 차례대로 출력한다.

제한

  • N≤250,000N \le 250,000
  • M≤250,000M \le 250,000
  • Q≤250,000Q \le 250,000
  • QQ개의 궁금증의 KK들의 합은 250,000250,000을 넘지 않는다.
  • −109≤Xi≤109-10^9 \le X_i \le 10^9 (1≤i≤N1 \le i \le N)
  • −109≤Yi≤109-10^9 \le Y_i \le 10^9 (1≤i≤N1 \le i \le N)
  • 1≤Ri≤1091 \le R_i \le 10^9 (1≤i≤N1 \le i \le N)
  • ii번째 원과 jj번째 원은 서로 같은 점을 공유하지 않는다 (1≤i<j≤N1 \le i < j \le N).
  • −109≤Ai≤109-10^9 \le A_i \le 10^9 (1≤i≤M1 \le i \le M)
  • −109≤Bi≤109-10^9 \le B_i \le 10^9 (1≤i≤M1 \le i \le M)
  • 0≤Ci<2310 \le C_i < 2^{31} (1≤i≤M1 \le i \le M)
  • ii번째 원 위에 점 (Aj,Bj)(A_j, B_j)가 존재하지 않는다 (1≤i≤N1 \le i \le N, 1≤j≤M1 \le j \le M).
  • 각 궁금증에 대하여, −109≤Ui≤109-10^9 \le U_i \le 10^9 (1≤i≤K1 \le i \le K)
  • 각 궁금증에 대하여, −109≤Vi≤109-10^9 \le V_i \le 10^9 (1≤i≤K1 \le i \le K)
  • 각 궁금증에 대하여, 0≤Li≤N0 \le L_i \le N (1≤i≤K1 \le i \le K)
  • 각 궁금증에 대하여, ii번째 원 위에 점 (Uj,Vj)(U_j, V_j)가 존재하지 않는다 (1≤i≤N1 \le i \le N, 1≤j≤K1 \le j \le K).

예제2

  1. 예제 1

    입력
    5 5 2
2 2 1
6 9 1
6 8 3
6 7 5
8 4 1
2 2 1
3 10 2
4 1 4
6 9 8
8 11 16
1
8 4 1
3
6 9 3
2 2 0
2 2 1
    예상 출력
    18
31

  2. 예제 2

    입력
    15 10 7
2 6 1
4 8 1
5 3 1
5 10 1
6 4 3
7 5 1
8 9 2
10 6 1
6 6 6
12 10 1
13 5 1
14 2 2
15 9 1
17 7 1
16 8 3
1 9 9
3 5 8
4 6 10
4 8 3
6 8 1
6 11 4
7 5 6
13 1 5
15 7 15
15 11 11
1
9 7 0
1
12 4 1
1
17 7 0
1
17 9 1
2
1 2 0
15 5 1
2
9 7 1
17 9 0
3
6 4 0
8 3 0
5 3 1
    예상 출력
    4
5
0
4
5
9
10