Query on Strings

0

0 votes
Trie, Segment Trees, Medium-Hard
Problem

You are given a list of n strings, you have to perform q queries on all of these strings. Queries are of two types -

1LRX : How many strings are there in the range [L,R] such that their prefix is the string X
2iX: Update the value of ith 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
1n4x104
1q5x104
1L,Rn
1|X|20

Sample Input
4 5
a
aaaaa
aaaaaaaaaa
aaaaa
2 2 aaaaaaaaaa
1 1 4 aaaaaa
1 1 4 aaa
2 2 aaaaaaaaaa
2 4 aaaaaaaaaa
Sample Output
2
3
Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?