Today is Kriti's birthday but I forgot to bring a gift for her. She is very angry with me. I have an idea for a gift. She likes coding very much. Why not give her a problem to solve as her gift?
I know a problem but I am not sure whether its solvable or not.
The problem initially has N strings numbered 1 to N. The program has to answer Q queries. Each query is of the form l r S. For each query, the program has to print the number of times the string S appears in the range [l,r].Help me by solving the problem!!
Input
Input will begin with an integer N denoting the number of strings.
N lines follows each having a string.
The next line contains Q denoting the number of queries.
Each of the next Q lines contain a query of the form l r S.
Output
For each query of type l r S, print the answer to that query. Each answer must be in a new line.
Constraints
100 ≤ N ≤ 100000100 ≤ Q ≤ 100000
1 ≤ l ≤ r ≤ N
Size of each string in the input is greater than or equal to 5 and less than or equal to 10.
Each string contains only lower case english characters.
For query 1: Only one "abc" is present (at position 1st) in the range [1,2], so the answer is 1. For query 2: Two "abc" are present (at position 1 and at position 3), so the answer is 2. For query 3: No "hgf" is present in the range [1,2], so the answer is 0.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor