New Year Couple

The new year 2017 is here. To celebrate the 31st night, Mr Rio has thrown a big party at his house. All the young boys and girls of the city have been invited to the party. To make the party more interesting, Rio will select any two person from the party at any moment and declare them as "New Year Couple"! Many attractive gifts are waiting for those couples.

In order to choose the couples, Rio has come up with an interesting plan. He will select three integers U, V and K randomly. A pair of person A and B will be eligible to become a "New Year Couple" only if they satisfy two following conditions:

1. Both of A and B are present at the party at time K.

2. Sub-string ( A, U, V ) = Sub-string( B, U, V ). Here, Sub-string( P, U, V ) is a continuous sub segment of string P which starts at index U and ends at index V.

At time K, Rio will declare any of the pair as "New Year Couple" randomly chosen from the eligible ones. Your task is to help Rio to find the number of pairs eligible to be selected as a "New Year Couple" at that time.

Input

The first line contains an integer N, the number of person who attended the party.
Each of the next N lines contains a string P and two integers S and E.
Here, P is the name of the person who attended the party, S is the time when that person entered and E is the time after which that person left.

The next line contains an integer Q. The number of query when Rio wants to declare the New Year Couple.
Each of the next Q lines contains three integers U, V and K. Details of U, V and K are already explained above.

Constraints:

1 ≤ |P| ≤ 50
1 ≤ U,V ≤ 50
1 ≤ N ≤ 30000
1 ≤ Q ≤ 105
0 ≤ K,S,E ≤ 106
1 ≤ summation of all |P| ≤ 2*105

Output

For each of the query, you have to find the number of pairs that are eligible to be selected as a "New Year Couple" at time K.

Samples

8
mrtarek 10 20
optarkk 15 30
mmtarqq 12 25
aatarcc 8 18
heloptr 22 50
memopto 10 40
kokoptz 15 45
lmkoopa 5 90
5
3 5 20
3 5 11
3 5 16
5 6 25
5 6 16

3
1
6
3
1

5
oookhzal 11 20
apkoptay 10 45
appokyat 30 32
popaozal 10 15
totkozal 15 25
4
6 8 15
7 7 10
3 5 25
1 2 30

3
1
0
1

Explanation:

If a person leaves the party after time E, he is considered present in the party at time E.