H. Nădlac
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Iuli has just been employed to be a border policeman at the Nădlac checkpoint (at the border between Romania and Hungary). His job is to verify the papers of all the trucks that pass the border. Each truck is assigned an unique color which can be either red, orange, yellow, green, blue, indigo or violet (the rainbow colors). The color of the truck is an important marker that helps the border police estimate the priority of each transport, more precisely:

$$$red \gt orange \gt yellow \gt green \gt blue \gt indigo \gt violet.$$$

One day, the paper checking system (used by Iuli to check a truck driver's papers) broke down. Because the system is down, no truck is crossing the border until it is repaired. Due to the situation, Iuli's boss is overwhelmed with requests. Iuli knows that his boss doesn't pay him for nothing, so he expects that the boss will assign him some of his tasks.

There are three types of events that can occur while the system is broken:

Type 1) A group of one or more trucks will arrive at the back of the queue.

Type 2) The boss will give Iuli a paper with the colors of a sequence of trucks that is standing in the queue and asks Iuli to check their papers. The problem is that Iuli's boss is, as we said above, overwhelmed by the situation, so he might give Iuli a sequence that might not even exist in the truck queue. If the sequence exists, Iuli will simply check their papers. If the sequence does not exist, Iuli does not know what to do. He can't go ask the boss because he is too busy with managing the crisis. Iuli decides that in case the sequence provided does not exist, he will simply choose the most important sequence of trucks that he can find in the queue, that is less important than the provided sequence.

We say that a sequence $$$X$$$ of trucks is more important than a sequence $$$Y$$$ if one of the following conditions apply:

  • There exists $$$Z$$$ another valid sequence of trucks such that $$$X = Y + Z$$$ (where $$$+$$$ is string concatenation)
  • There exists $$$k$$$ an index such that $$$X_i = Y_i$$$ for every $$$i \lt k$$$ and $$$X_k \gt Y_k$$$. (where $$$X_i$$$ represents the $$$i$$$-th truck from the X sequence of trucks).

Type 3) The boss comes with a question that came from the ministry of transportation of Romania to check on the situation. Because he is again overwhelmed by the situation, he passes the question to Iuli to write a response. Fortunately, the ministry will always ask the same question: the sum of lengths of all distinct sequences. The ministry is not interested in all the trucks in the sequence, so they want the sum of the sequences that contain only colors from a list provided by them.

Iuli is worried of what is to come, so he wants you to help him prepare by resolving a scenario containing events as described above.

You will receive the events that will occur (in the order they are given) in a scenario. For each event of Type 2 you have to find the sequence of trucks that Iuli will choose to verify their papers. For each event of Type 3 you have to find the answer to ministry's question.

At the beginning of each scenario, at the border there are no trucks waiting to pass.

Input

The first line of input will contain one integer $$$Q$$$ ($$$1\leq Q \leq 500$$$) representing the number of events that are occurring in our scenario.

The next $$$Q$$$ lines will each contain an event:

  • $$$1$$$ $$$S$$$, meaning that a sequence of trucks $$$S$$$ ($$$1\leq |S| \leq 10^5$$$) codified by their colors. It is guaranteed that $$$\sum_{}^{} |S| \leq 10^5$$$.
  • $$$2 $$$ $$$T$$$, meaning that the boss wants to check the papers of sequence $$$T$$$ ($$$1\leq |T| \leq 10^5$$$).
  • $$$3 $$$ $$$C$$$, meaning that the ministry wants the answer for the color-sequence $$$C$$$ ($$$1\leq |C| \leq 7$$$).

The truck sequences received in input and required in the output will be codified by their color.

A sequence $$$x_1$$$, $$$x_2$$$, ... $$$x_N$$$ is the codification by color of a sequence of $$$N$$$ trucks where:

  • If $$$x_i = R$$$ means that the $$$i$$$-th truck in the sequence is red.
  • If $$$x_i = O$$$ means that the $$$i$$$-th truck in the sequence is orange.
  • If $$$x_i = Y$$$ means that the $$$i$$$-th truck in the sequence is yellow.
  • If $$$x_i = G$$$ means that the $$$i$$$-th truck in the sequence is green.
  • If $$$x_i = B$$$ means that the $$$i$$$-th truck in the sequence is blue.
  • If $$$x_i = I$$$ means that the $$$i$$$-th truck in the sequence is indigo.
  • If $$$x_i = V$$$ means that the $$$i$$$-th truck in the sequence is violet.

The trucks in a sequence are ordered from the closest truck to the border checkpoint to the furthest away.

For the type 3 event you will receive a sequence of non-empty, non-repeating colors codifying the list of colors provided by the ministry.

Output

The output shall contain the answer to queries of type 2 and 3.

Example
Input
6
1 GBIOOYBIOOYBB
2 R
3 O
1 OOO
2 R
3 O
Output
OOYBB
3
OOO
6
Note

"O" and "OO" are the only sequences with letters "O", thus the resulting total length is 3 for the first query of type 3.

"O", "OO" and "OOO" are the only sequences with letters "O", thus the resulting total length is 6 for the second query of type 6.