대피

폭풍우가 몰아치는 어두운 밤이다. 우리 요원이 중앙아메리카에서 위험한 임무를 막 마쳤다. 생명이 위험하니 당장 대피시켜야 한다. 헬기가 그를 태울 수 있는 유일한 곳은 정글을 가로지르는 직선 도로이다. 요원은 도로 한가운데, 위치 0에서 출발하며 어느 방향으로든 초당 1미터의 속도로 걸을 수 있다. 날씨는 더 나빠졌다. 뇌우가 다가오고 있고, 낙뢰는 헬기와 요원 모두에게 위험하다. 헬기는 정해진 몇 개의 시각과 장소에서만 착륙할 수 있다. 예보를 통해 각 낙뢰가 언제 어디에 떨어지고, 어느 범위를 태울지 알고 있다. 이 정보를 바탕으로 낙뢰를 피하면서 제시간에 도달할 수 있는 착륙 지점을 구하라.

착륙 지점과 낙뢰의 시각 $t$가 같고 둘 사이의 거리가 $r$보다 가까우면 대피는 불가능하다는 점에 유의하라.

입력의 첫 줄에는 테스트 케이스의 개수 $z$가 주어진다. 각 테스트 케이스는 다음과 같다.

각 테스트 케이스의 첫 줄에는 낙뢰의 개수 $n$ ($0 \leq n \leq 200\,000$)이 주어진다. 이어지는 $n$개의 줄에는 낙뢰 하나를 나타내는 정수 $t, x, r$ ($0 \leq t \leq 10^9$, $-10^9 \leq x \leq 10^9$, $1 \leq r \leq 10^9$)이 주어진다. 각각 낙뢰의 시각 $t$, 위치 $x$, 폭발 반경 $r$이다. 요원은 시각 $t$에 낙뢰로부터 최소 $r$미터 이상 떨어져 있어야 하며, 그렇지 않으면 감전된다.

다음 줄에는 가능한 착륙 지점의 개수 $s$ ($1 \leq s \leq 200\,000$)가 주어진다. 이어지는 $s$개의 줄에는 두 정수 $t, x$ ($0 \leq t \leq 10^9$, $-10^9 \leq x \leq 10^9$)가 주어지며, 헬기가 시각 $t$에 위치 $x$에 착륙할 수 있음을 뜻한다. 요원도 그 시각에 그 자리에 있을 수 있는지 판단하라.

모든 테스트 케이스의 낙뢰와 착륙 지점을 합한 개수는 $1\,300\,000$을 넘지 않는다.

각 테스트 케이스마다, 모든 착륙 지점에 대해 주어진 시각에 요원이 낙뢰를 맞지 않고 그곳에 있을 수 있는지 판단하라. 테스트 케이스마다 한 줄에 답을 출력한다. 주어진 순서대로 각 착륙 지점에 대해, 그곳에서 대피할 수 있으면 @, 아니면 *를 한 글자씩 출력하라.