409630: GYM103648 G Dove Dance

Doves like to dance. Doves like to go to dances with other doves. Sometimes dove dances look like this:

Today, the doves have planned a dove dance! Dove dances occur sequentially, that is, as a series of events over time. The doves have planned for a dove dance of length $$$Q$$$ units of time.

It just so happens that you have been hired as the bouncer for the dove dance! As the bouncer, it is your responsibility to keep track of the names of the doves that are present at the dove dance.

Initially, the dance has zero doves present. At each point in time, it is possible that a dove may show up at the dance. When this happens, the dove will tell you its name, a string of lowercase English letters ("a"-"z"). We will call these queries of type 1.

Another possible event which can happen at a given point in time is a complaint. Sometimes, doves tend to get too groovy on the dance floor and another dove will report the name of the offending dove to you, the bouncer. If this is the case, it is your responsibility to report back whether or not the name of the offending dove is a prefix of the names of any doves which are currently at the dove dance. Note that the name reported to you need not be the name of any of the doves at the dance, and also note that, being the kind and wholesome bouncer you are, you will never end up removing any doves from the dance.

However, doves are fickle creatures, and sometimes they enjoy changing their identities at whim. The third and final possibility of an event that can happen at a given point in time is that the doves will collectively decide to change their names by doing a little dove twirl. When a dove twirl occurs, all of the doves who are currently at the dance will reverse their names and take on their new identities. We will call these queries of type 3.

The first line of input will consist of a single integer $$$Q\ (1 \leq Q \leq 10^5)$$$, denoting the number of queries. The next $$$Q$$$ lines of input will consist of a single query. Each query line will be in either the form $$$1\ S$$$, $$$2\ T$$$, or $$$3$$$ where $$$\sum{|S|}, \sum{|T|} \leq 10^5$$$. A query of type 1 denotes that dove with a name of $$$S$$$ appears at the dance. A query of type 2 asks whether $$$T$$$ is a prefix of any of the names of doves at the dance. A query of type 3 denotes a reversal of all names of doves currently at the dance.

For each query of type 2, the output should contain a single line containing either a $$$0$$$ or a $$$1$$$ depending on whether or not the queried dove appeared at the dance or not.

5
1 alice
2 alice
3
2 ali
2 ecil

1
0
1

The sample case follows the following sequence of events:

At the first point in time, a dove named "alice" appears at the dance.

At the second point in time, a dove complains to the bouncer regarding a dove named "alice", and the bouncer reports back "1" since "alice" is a prefix of "alice".

At the third point in time, all doves currently at the dance reverse their names, so the only dove at the dance is now named "ecila".

At the fourth point in time, a dove complains to the bouncer regarding a dove named "ali", and the bouncer reports back "0" since "ali" is not a prefix of "ecila".

At the fifth point in time, a dove complains to the bouncer regarding a dove named "ecil", and the bouncer reports back "1" since "ecil" is a prefix of "ecila".