Sheep Queue Substring Queries

There is a queue of sheep on the grassland. Each sheep has wool of one of 7 colors. The colors are ranked by preference as follows:

$$ red > orange > yellow > green > blue > indigo > violet $$

We will represent each color by a digit according to the above ranking (i.e. red \(=7\), orange \(=6\), yellow \(=5\), green \(=4\), blue \(=3\), indigo \(=2\), violet \(=1\)).

The sheep queue undergoes \(Q\) events. There are three types of events:

1. Type 1: Several sheep join the queue at the end. The input format is: 1 m color1 color2 ... colorm. The sequence is updated by appending these \(m\) colors.
2. Type 2: Given a color sequence \(T\), first convert it into a digit string (by replacing each color with its corresponding digit). Then, consider all nonempty contiguous substrings of this digit string and let \(X\) be the lexicographically maximum substring (using standard lexicographical order, where for example "65" > "6"). Next, considering the current sheep queue (also converted into a digit string in the same manner), find all distinct contiguous substrings whose value is lexicographically not greater than \(X\) (i.e. \(\le X\)). Output the count of such substrings. The input format is: 2 m color1 color2 ... colorm.
3. Type 3: Given a set \(C\) of colors (without order), compute the sum of lengths of all distinct contiguous substrings of the current sheep queue (again, after converting to digits) that are composed only of colors from \(C\). (A substring's length is defined as the number of sheep in it.) The input format is: 3 k color1 color2 ... colork.

The initial sheep queue is empty. Process the events in order and for each event of type 2 and type 3, output the answer on a new line.

inputFormat

The first line contains an integer (Q) representing the number of events. Each of the next (Q) lines represents an event in one of the following formats:

Type 1: 1 m color1 color2 ... colorm Type 2: 2 m color1 color2 ... colorm Type 3: 3 k color1 color2 ... colork

Each color is one of: red, orange, yellow, green, blue, indigo, violet.

outputFormat

For each event of type 2 and type 3, output the answer on a separate line.

sample

5
1 3 red blue green
2 2 orange yellow
3 2 red green
1 2 violet indigo
2 3 yellow green blue

3
2
10