# Practice on Toph

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

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

This time I’m going to introduce you to a new land, called String Land.

In String Land there are **N (1 ≤ N ≤ 10 ^{5})** cities, numbered from

Every year, people from different countries travel to String Land. Every traveler has a name. When a person travel to the String Land, he/she is only allowed to visit a segment of cities which lies in the range [L, R] i.e. he/she can visit the i

For different traveler the allowable range of cities to travel can be different.

Every time when a traveler travels the i^{th} city (L ≤ i ≤ R), he/she becomes joyful. The joyfulness of a specific traveler with name *tname*_{i}, visiting the j_{th} city is:

LCP(tname

_{i}, name_{j}) × a_{j}

Where *tname*_{i} is the name of the i^{th} traveler.**name**_{j} and **a**_{j} are respectively the name and the attractiveness value of the person who lives in the j^{th} city.**LCP**(*tname*_{i}, **name**_{j}) is the **length** of **The Longest Common Prefix** of *tname*_{i} and **name**_{j}.

We are only interested in the maximum joyfulness of a traveler can achieve while traveling the cities from L to R.

The first line of the input contains a positive integer **N (1 ≤ N ≤ 10 ^{5})** where

The next line contains N positive integers

The next N lines will contain N strings

The next line contains a positive integer

Each of the next Q lines will contain a string

The

∑

∑

For each traveler, report the maximum joyfulness for him/her while visiting the cities from ** L** to

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

3 25 4 33 abcba abbaa abacaba 2 abb 2 3 abcd 1 3 | 66 75 |

For traveler #1, |

62% Solution Ratio

RamprosadGEarliest,

Hasinur_Fastest, 0.2s

theunownLightest, 60 MB

theunownShortest, 1252B

Login to submit