cho.sh

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

여러 번의 명령이 주어질 때, 각 중심점에서 원을 최소로 지나는 거리가 제한 이하인 집들의 행복도를 중복 없이 XOR한 값을 구한다.

어려움9그래프BFS기하비트 연산아직 제출이 없습니다시간 제한4초메모리 제한1024 MB

문제

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

2차원 평면인 이 도시에는 중심이 (X_i,Y_i)(X\_i, Y\_i)고 반지름이 R_iR\_i인 NN개의 원이 존재한다. NN개의 원은 서로 같은 점을 공유하지 않음이 보장된다.

또한 강민시에는 총 MM채의 민제네 집이 있다. ii번째 집의 위치는 (A_i,B_i)(A\_i, B\_i)며, 이 집을 부수었을 때 교준이가 얻는 행복도는 C_iC\_i다. 집의 위치나 행복도는 서로 같을 수 있으나, 모든 MM채의 집은 NN개의 원 위에 존재하지 않음이 보장된다.

집을 부수었을 때 교준이가 얻는 행복도의 정의는 조금 특이하다. 어떤 집도 부숴지지 않았다면, 교준이는 00의 행복도를 얻는다. 만일 행복도가 33인 집과 행복도가 66인 집이 부수어졌다면, 교준이는 3⊕6=53 \oplus 6 = 5의 행복도를 얻는다. 즉, 행복도가 c_1,c_2,⋯ ,c_kc\_1, c\_2, \cdots, c\_k인 집 kk채가 부숴졌다면, 교준이는 총 (c_1⊕c_2⊕⋯⊕c_k)( c\_1 \oplus c\_2 \oplus \cdots \oplus c\_k )의 행복도를 얻게 된다. 이때 ⊕\oplus는 배타적 논리합을 나타내는 기호다.

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

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

민제네 집 철거 공사 계획을 세우고 있던 교준이는 다음과 같은 궁금증이 생겼다:

민제에게 "(U_1,V_1)(U\_1, V\_1)로 가서 거리 L_1L\_1 이내에 있는 너네 집을 모두 부숴라."라고 명령한 후,

다시 민제에게 "(U_2,V_2)(U\_2, V\_2)로 가서 거리 L_2L\_2 이내에 있는 너네 집을 모두 부숴라."라고 명령한 후,

⋯\cdots

다시 민제에게 "(U_K,V_K)(U\_K, V\_K)로 가서 거리 L_KL\_K 이내에 있는 너네 집을 모두 부숴라."라고 총 KK차례 명령한다면,

내가 얻는 총 행복도는 얼마일까?

교준이의 영원한 심부름꾼, 민제는 오늘도 교준이의 궁금증을 해결해주어야 한다. 허나 민제는 "1+9+10=19"라고 말할 정도로 수학을 못하는 바보다. 민제를 위하여 교준이의 질문에 답해주는 프로그램을 작성해보자!

입력

첫 번째 줄에는 강민시의 원의 개수를 나타내는 자연수 NN과 민제네 집의 수를 나타내는 자연수 MM, 교준이의 궁금증 횟수를 나타내는 자연수 QQ가 사이에 공백을 두고 주어진다.

두번째 줄부터 NN개의 줄에 걸쳐 NN개의 원에 관한 정보가 주어진다. (i+1)(i+1)번째 줄에는 세 정수 X_iX\_i, Y_iY\_i, R_iR\_i가 사이에 공백을 두고 주어진다(1≤i≤N)(1 \le i \le N).

(N+2)(N+2)번째 줄부터 MM개의 줄에 걸쳐 MM채의 민제네 집에 관한 정보가 주어진다. (N+i+1)(N+i+1)번째 줄에는 세 정수 A_iA\_i, B_iB\_i, C_iC\_i가 사이에 공백을 두고 주어진다(1≤i≤M)(1 \le i \le M).

(N+M+2)(N+M+2)번째 줄부터 아래와 같은 형식으로 QQ개의 교준이의 궁금증에 관한 정보가 주어진다.

하나의 궁금증은 여러 줄에 걸쳐 표현되며, 다음와 같은 형식을 같는다. 첫 번째 줄에는 민제에게 명령하는 총 횟수를 나타내는 자연수 KK가 주어진다. 두번째 줄부터 KK개의 줄에 걸쳐 KK번의 명령에 관한 정보가 주어진다. (i+1)(i+1)번째 줄에는 세 정수 U_iU\_i, V_iV\_i, L_iL\_i가 사이에 공백을 두고 주어진다(1≤i≤K)(1 \le i \le K).

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≤X_i≤109(1≤i≤N)-10^9 \le X\_i \le 10^9 (1 \le i \le N)
  • −109≤Y_i≤109(1≤i≤N)-10^9 \le Y\_i \le 10^9 (1 \le i \le N)
  • 1≤R_i≤109(1≤i≤N)1 \le R\_i \le 10^9 (1 \le i \le N)
  • ii번째 원과 jj번째 원은 서로 같은 점을 공유하지 않는다(1≤i<j≤N)(1 \le i < j \le N).
  • −109≤A_i≤109(1≤i≤M)-10^9 \le A\_i \le 10^9 (1 \le i \le M)
  • −109≤B_i≤109(1≤i≤M)-10^9 \le B\_i \le 10^9 (1 \le i \le M)
  • 0≤C_i<231(1≤i≤M)0 \le C\_i < 2^{31} (1 \le i \le M)
  • ii번째 원 위에 점 (A_j,B_j)(A\_j, B\_j)가 존재하지 않는다(1≤i≤N,1≤j≤M)(1 \le i \le N, 1 \le j \le M).
  • 각 궁금증에 대하여, −109≤U_i≤109(1≤i≤K)-10^9 \le U\_i \le 10^9 (1 \le i \le K)
  • 각 궁금증에 대하여, −109≤V_i≤109(1≤i≤K)-10^9 \le V\_i \le 10^9 (1 \le i \le K)
  • 각 궁금증에 대하여, 0≤L_i≤N (1≤i≤K)0 \le L\_i \le N (1 \le i \le K)
  • 각 궁금증에 대하여, ii번째 원 위에 점 (U_j,V_j)(U\_j, V\_j)가 존재하지 않는다(1≤i≤N,1≤j≤K)(1 \le i \le N, 1 \le j \le K).