# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

## New Year Couple

The new year 2017 is here. To celebrate the 31^{st} 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.

**Constraints:**

**1 ≤ |P| ≤ 50****1 ≤ U,V ≤ 50****1 ≤ N ≤ 30000****1 ≤ Q ≤ 10 ^{5}**

**0 ≤ K,S,E ≤ 10**

^{6}**1 ≤ summation of all |P| ≤ 2*10**

^{5}### 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

Input | Output |
---|---|

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 |

Input | Output |
---|---|

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**.

#### flash_7

Tarango works NSUPS. He loves to play FIFA & travel with friends. When not solving problems, he spends most of his time day dreaming. And, he most definitely is not a "manga lover". →