Problem Description

On a grassland, a group of sheep stand in a line. The wool of these sheep comes in $7$ colors. From most liked to least liked, the order is:

Then, the following three types of events will happen:

1: Some sheep join the end of the line one by one.

2: Given a color sequence $T$, among all distinct substrings of the current sheep sequence, convert each substring into a sequence of numbers according to the preference order (for example, red is $7$ and violet is $1$), and count those whose lexicographic order is less than or equal to the lexicographically largest substring of $T$.

3: Given a set of colors $C$, find the sum of lengths of all distinct substrings of the current sheep sequence that are composed only of colors in $C$.

Input Format

The first line contains an integer $Q (1≤Q≤500)$, representing the number of events.

In the next $Q$ lines, each line first contains a number indicating the event type, and then:

1: Input a sheep sequence $S(1≤|S|≤10^5)$. It is guaranteed that $∑|S|≤10^5$.

2: Input a color sequence $T(1≤|T|≤10^5)$.

3: Input a color set $C(1≤|C|≤7)$.

Each color is represented by the uppercase form of the first letter of the word.

Output Format

For each event of type 2 and type 3, output the answer.

6
1 GBIOOYBIOOYBB
2 R
3 O
1 OOO
2 R
3 O

OOYBB
3
OOO
6

Hint

Translated by ChatGPT 5