Strings are inevitable in life. They give meaning to our expressions. Strings come in life in many ways, like a well-written letter for hearts, a nice song composed to heal the souls. For NGPC contestants like you, strings come in the form of a programming problem to give joy.
You will be given a list of strings and queries. The queries are of two types. They are described below:
Type 1: A prefix and a character will be given. You will have to change the character to of the strings which have a prefix . Note that, we start counting indexes of strings from .
Type 2: A prefix will be given. You have to determine the number of strings that have a prefix that matches with .
A prefix of a string is a substring of that occurs at the beginning of .
The first line of the input file will contain a single positive integer which denotes the number of strings in the list . Each of the next lines will contain a string . After that, there will be a single positive integer . Each of the next lines will contain each of the two types of queries described below:
This is the first type of query. You will have to change the character to of the strings which have a prefix such that .
Here, and contains one of the lowercase English alphabets only.
This is the second type of query. You have to determine the number of strings that have a prefix that matches with .
Here, .
It is guaranteed that all the strings in the input file contains lowercase English alphabets only and there will be at least one query of type 2.
Other constraints:
For each of the type of query, print the number of strings which have a prefix that matches with given prefix .
Input | Output |
---|---|
2 abcdx abcex 3 1 abce d 2 abce 2 abcd | 0 2 |