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:

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

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.