시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 (언어별 추가 시간 없음) 1024 MB 3 2 2 66.667%

문제

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

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

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

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

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

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

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

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

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

$\cdots$

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

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

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

입력

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

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

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

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

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

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

출력

첫번째 줄부터 $Q$개의 줄에 걸쳐 교준이가 얻는 행복도를 차례대로 출력한다.

제한

모든 입력 데이터는 아래의 조건을 모두 만족한다.

  • $N \le 250,000$
  • $M \le 250,000$
  • $Q \le 250,000$
  • $Q$개의 궁금증의 $K$들의 합은 $250,000$을 넘지 않는다.
  • $-10^9 \le X_i \le 10^9 (1 \le i \le N)$
  • $-10^9 \le Y_i \le 10^9 (1 \le i \le N)$
  • $1 \le R_i \le 10^9 (1 \le i \le N)$
  • $i$번째 원과 $j$번째 원은 서로 같은 점을 공유하지 않는다$(1 \le i < j \le N)$.
  • $-10^9 \le A_i \le 10^9 (1 \le i \le M)$
  • $-10^9 \le B_i \le 10^9 (1 \le i \le M)$
  • $0 \le C_i < 2^{31} (1 \le i \le M)$
  • $i$번째 원 위에 점 $(A_j, B_j)$가 존재하지 않는다$(1 \le i \le N, 1 \le j \le M)$.
  • 각 궁금증에 대하여, $-10^9 \le U_i \le 10^9 (1 \le i \le K)$
  • 각 궁금증에 대하여, $-10^9 \le V_i \le 10^9 (1 \le i \le K)$
  • 각 궁금증에 대하여, $0 \le L_i \le N (1 \le i \le K)$
  • 각 궁금증에 대하여, $i$번째 원 위에 점 $(U_j, V_j)$가 존재하지 않는다$(1 \le i \le N, 1 \le j \le K)$.

예제 입력 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

예제 출력 1

18
31

점 $P_i$는 $i$번째 민제네 집의 위치를 나타낸다.

예제 입력 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

예제 출력 2

4
5
0
4
5
9
10


 

출처

  • 문제를 만든 사람: yclock