You are given a list of n strings, you have to perform q queries on all of these strings. Queries are of two types -
: How many strings are there in the range such that their prefix is the string X
: Update the value of string to X
Input
First line contains two space separated integers n and q. Next n line contains strings in each row of length at most 20. Next q line contains these queries as per the description above. For every query of type 1 you need to provide the required output.
Constraints
4 5 a aaaaa aaaaaaaaaa aaaaa 2 2 aaaaaaaaaa 1 1 4 aaaaaa 1 1 4 aaa 2 2 aaaaaaaaaa 2 4 aaaaaaaaaa