Rat-O-Matic

회사 Rapid City Dynamics는 개 모양 로봇, 치타 모양 로봇, 사람 모양 로봇으로 알려져 있다. 큰 프로젝트에는 큰돈이 들기 때문에, 회사는 더 단순하면서도 더 인기 있고 팔 수 있는 제품을 만들기로 했다. 새 로봇의 이름은 Rat-O-Matic이다. 여러분은 Rapid City Dynamics의 직원으로서 이 설계에 참여한다.

이 로봇은 평면 위에 놓인 특별한 틀을 건드리며 움직이고 멜로디를 만드는 기계 쥐다. 평면은 모든 방향으로 무한하며 데카르트 좌표계가 있다고 가정해도 된다. 틀은 정확히 $n$개 있다. 각 틀은 정수 $x$, $y$, $r$로 주어진다. 틀은 중심이 $(x, y)$이고 두 축 정렬 정사각형 사이에 있는 영역이다. 첫 번째 정사각형의 반지름은 $r$이고 두 번째 정사각형의 반지름은 $2r$이다. 정사각형의 반지름은 중심에서 변까지의 거리다. 각 틀에는 소리가 하나씩 연결되어 있다. 소리는 "r", "a", "t" 세 가지뿐이다. 어떤 두 틀도 겹치거나 맞닿지 않는다.

키보드에 틀 번호를 입력해 로봇에 명령을 내린다. 틀은 1번부터 번호가 붙어 있다. 처음에 쥐는 모든 틀 바깥에 서 있다. 명령을 받으면 쥐는 지정된 틀을 향해 움직이기 시작한다. 내비게이션 시스템은 다른 틀과 교차하는 횟수가 가장 적은 경로를 고른다. 틀을 건드릴 때마다 그 틀의 소리가 나므로, 쥐는 이동하면서 멜로디를 연주한다. 로봇은 지정된 틀을 건드린 뒤 멈춘다.

사람들은 익숙한 멜로디를 좋아한다. 데이터베이스에는 $m$개의 멜로디가 있고, 각 멜로디는 소리 문자로 된 문자열이다. 생성된 멜로디가 데이터베이스 멜로디에 포함된다는 것은, 생성된 멜로디가 그 멜로디의 부분 문자열(연속된 부분 수열)일 때이고, 그때만 그렇다. 생성된 멜로디의 인기도는 그것을 포함하는 데이터베이스 멜로디의 개수다. 데이터베이스에 같은 멜로디가 여러 개 있으면 각각 따로 센다.

여러분은 배치를 실험하기 위해 $q$번의 실험을 한다. 실험은 세 종류다. 1번 실험은 활성 상태인 틀 $x$를 비활성화한다. 비활성화된 틀은 소리를 내지 않는다. 처음에는 모든 틀이 활성 상태다. 2번 실험은 비활성 상태인 틀 $x$를 활성화한다. 3번 실험은 쥐가 모든 틀 바깥에서 출발해 틀 $x$를 향해 움직이며 만든 멜로디의 인기도를 구한다. 이때 틀 $x$는 활성 상태다.

첫 줄에 틀의 개수 $n$이 주어진다($1 \le n \le 2 \cdot 10^5$). 다음 $n$줄에는 정수 $x_i$, $y_i$, $r_i$와 문자 $c_i$가 공백으로 구분되어 주어진다. 이는 각각 틀 $i$의 중심 좌표, 안쪽 정사각형의 반지름, 소리다. 제약은 $-10^8 \le x_i, y_i \le 10^8$, $1 \le r_i \le 10^8$이고, $c_i$는 r, a, t 중 하나다.

다음 줄에는 데이터베이스의 멜로디 개수 $m$이 주어진다($1 \le m \le 2 \cdot 10^5$). 다음 $m$줄에는 멜로디가 한 줄에 하나씩 주어진다. 각 멜로디는 비어 있지 않으며 r, a, t로만 이루어진다. 모든 멜로디 길이의 합은 $2 \cdot 10^5$을 넘지 않는다.

다음 줄에는 실험의 개수 $q$가 주어진다($1 \le q \le 2 \cdot 10^5$). 다음 $q$줄에는 문자 $t_j$(-, +, ? 중 하나)와 정수 $x_j$가 공백으로 구분되어 주어진다. -는 1번 실험, +는 2번 실험, ?는 3번 실험이다. 정수는 틀 번호다. 3번 실험은 적어도 하나 있다고 보장된다.

3번 실험마다 그 멜로디의 인기도를 한 줄에 정수로 출력한다.