Ontology_Challange-

Design a system that allows for fast searches of questions under topics. There are NN topics, MM questions, and KK queries, given in this order. Each query has a desired topic as well as a desired string prefix. For each query, return the number of questions that fall under the queried topic and begin with the desired string. When considering topics, we want to include all descendants of the queried topic as well as the queried topic itself. In other words, each query searches over the subtree of the topic. The topic ontology is given in the form of a flattened tree of topic names, where each topic may optionally have children. If a topic has children, they are listed after it within parentheses, and those topics may have children of their own, etc. See the sample for the exact input format. The tree is guaranteed to have a single root topic. For ease of parsing, each topic name will be composed of English alphabetical characters, and each question and query text will be composed of English alphabetical characters, spaces, and question marks. Each question and query text will be well behaved: there will be no consecutive spaces or leading/trailing spaces. All queries, however, are case sensitive. Constraints For 100% of the test data, 1≤N,M,K≤1051≤N,M,K≤105 and the input file is smaller than 5MB For 50% of the test data, 1≤N,M,K≤2⋅1041≤N,M,K≤2⋅104 and the input file is smaller than 1MB Input Format Line 1: One integer NN Line 2: NN topics arranged in a flat tree (see sample) Line 3: One integer MM Line 4...M+3: Each line contains a topic name, followed by a colon and a space, and then the question text. Line M+4: One integer KK Line M+5...M+K+4: Each line contains a topic name, followed by a space, and then the query text. Output Format Line 1...K: Line ii should contain the answer for the iith query. Sample Input 6 Animals ( Reptiles Birds ( Eagles Pigeons Crows ) ) 5 Reptiles: Why are many reptiles green? Birds: How do birds fly? Eagles: How endangered are eagles? Pigeons: Where in the world are pigeons most densely populated? Eagles: Where do most eagles live? 4 Eagles How en Birds Where Reptiles Why do Animals Wh Sample Output 1 2 0 3