List of Strings

The solution to this problem requires Trie and Binary Indexed Tree/Segment tree. Steps are given below:

1. Take all the input queries and save them. You need to answer the queries offline here.

2. Insert all the strings in a trie, mark the endnodes and track frequency for each node.

3. Run a DFS on the trie and determine dfs time for each node in a way that lexicographically smaller prefix get smaller dfs time.

4. Build a BIT for cumulative sum, add the values of each trie nodes frequency to it.

5. Start executing the type 2 and 3 queries.
   if a type 2 query comes then change the strings endnode by going up of the trie. Change data accordingly in BIT.
   If a type 3 query comes then determine the dfs time of endnodes of the given two strings. Get the sum between this two endnodes’ dfs time and print it.