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 .
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.
For each of the type of query, print the number of strings which have a prefix that matches with given prefix .
2 abcdx abcex 3 1 abce d 2 abce 2 abcd