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 ≤ 100000
100 ≤ 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.
SAMPLE INPUT
3
abc
def
abc
3
1 2 abc
1 3 abc
1 2 hgj

SAMPLE OUTPUT
1
2
0

Explanation

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.
def hash_value(s):
	a = [ord(i)-97 for i in s]
	p = 0
	b = 0
	#hv = 10**9 + 7
	for i in xrange(len(a)-1,-1,-1):
		p+=(a[i]*(26**b))
		#p%=hv
		b+=1
	return p
t = input()
all_str = {}
for i in xrange(t):
	xy = hash_value(raw_input())
	if xy in all_str:
		all_str[xy]+=[i]
	else:
		all_str[xy]=[i]
n = input()
for _ in xrange(n):
	inp = raw_input().split()
	l = int(inp[0])-1
	r = int(inp[1])-1
	s = hash_value(inp[2])
	ans = 0
	if(s not in all_str):
		print 0
		continue
	for i in all_str[s]:
		if(l<=i and i<=r):
			ans+=1
	print ans