Rat-O-Matic

The company Rapid City Dynamics is famous for its dog-like robots, cheetah-like robots and even human-like robots. But big projects need big money, so they decided to build something simpler yet more popular (and sellable!). So now the company is engineering a new robot called Rat-O-Matic, and you, as Rapid City Dynamics employee, are going to take a part!

The robot itself is a mechanical rat which can move around and generate melodies by touching special frames placed on a plane. You can assume the plane is infinite in all directions and there is a Cartesian coordinate system on it. There are exactly $n$ frames. Each frame is described by three integers $x$, $y$ and $r$. It consists of the area enclosed between two axis-aligned squares centered at point $(x, y)$: the first square's radius is $r$ and the second square's radius is $2 r$. The radius of a square is the distance from its center to its side. Moreover, every frame has an associated sound. Currently there are only three possible sounds, let us denote them by "r", "a", and "t". It is guaranteed that no two frames intersect or touch.

It is possible to interact with the robot by entering the frame's number on a special keyboard (frames are numbered starting from 1). Initially, the rat stands outside of all frames. After getting a command, the rat starts to move towards the specified frame. Thanks to the patented navigation system, the robot picks a path which intersects the minimal possible number of other frames. When a frame is touched, it produces an associated sound, so the rat generates a melody while moving. The robot stops after touching the specified frame.

It is well known that people like familiar melodies. There are $m$ melodies in your database. Each melody is described by a string of characters which encode sounds. A melody generated by the rat is said to be contained in a melody from the database if and only if the former is a substring (a continuous subsequence) of the latter. And the popularity of a generated melody is the number of melodies from the database which contain the generated melody. Note that, even if some melodies from the database appear to be the same, they still must be counted separately.

In attempts of creating the most entertaining layout of frames, you made $q$ experiments. Each experiment has one of the following types:

1. Deactivate the frame number $x$. It is guaranteed that the frame is currently active. Deactivated frames do not produce any sound. In the beginning, all frames are active.
2. Activate the frame number $x$. It is guaranteed that the frame is currently deactivated.
3. Calculate the popularity of a melody generated by the robot while moving towards the frame number $x$ starting outside of all frames. It is guaranteed that this frame is active at the moment.

Help yourself to simulate all experiments using just your computer!

The first line contains an integer $n$, the number of frames ($1 \le n \le 2 \cdot 10^5$). The next $n$ lines describe the frames, $i$-th of them contains integers $x\_i$, $y\_i$, $r\_i$ and a character $c\_i$ separated by spaces ($-10^8 \le x\_i, y\_i \le 10^8$, $1 \le r\_i \le 10^8$, and $c\_i$ is either r, a or t). These are coordinates of the center of a frame, the radius of the inner square and the associated sound, respectively.

The next line contains an integer $m$, the number of melodies in the database ($1 \le m \le 2 \cdot 10^5$). The next $m$ lines contain the strings representing the melodies. Each string is non-empty and consists of characters r, a and t. The total length of all strings does not exceed $2 \cdot 10^5$.

The next line contains an integer $q$, the number of experiments ($1 \le q \le 2 \cdot 10^5$). The next $q$ lines describe experiments, $j$-th of them contains a character $t\_j$ (-, + or ?) and an integer $x\_j$ separated by a space. The character encodes the type of the experiment (- is 1, + is 2 and ? is 3), and the integer is the number of the frame.

It is guaranteed that there is at least one experiment of the third type.

For every experiment of the third type, print a single line containing an integer which is the popularity of the generated melody.