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

In String Land there are N (1 ≤ N ≤ 105) cities, numbered from 1 to N sequentially. In each city there lives a man who have a name and also have an attractiveness value. The name of the ith person is namei and the attractiveness value is ai. 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 ith city iff L ≤ i ≤ R for a specific traveler. For different traveler the allowable range of cities to travel can be different.

Every time when a traveler travels the ith city (L ≤ i ≤ R), he/she becomes joyful. The joyfulness of a specific traveler with name tnamei, visiting the jth city is:

LCP(tnamei , namej) × aj

Where tnamei is the name of the ith traveler. namej and aj are respectively the name and the attractiveness value of the person who lives in the jth city. LCP(tnamei, namej) is the length of The Longest Common Prefix of tnamei and namej. We are only interested in the maximum joyfulness of a traveler can achieve while traveling the cities from L to R.

Input

The first line of the input contains a positive integer N (1 ≤ N ≤ 105) where N is the number of cities in String Land. The next line contains N positive integers a1, a2, a3 ... aN, where ai (1 ≤ ai ≤ 106) is the attractiveness value of the person who lives in the ith city. The next N lines will contain N strings name1, name2, name3 ... nameN, where namei is the name of the person who lives in the ith city. The next line contains a positive integer Q (1 ≤ Q ≤ 105) where Q is the number of traveler who will visit the String Land. Each of the next Q lines will contain a string tname and two integers L and R where tnamei is the name of the ith traveler and [Li, Ri] is the range of the index of the allowable city for the ith traveler where the traveler can visit . The name and tname contains only the lowercase English letters, [a-z]. ∑i=1N |namei| ≤ 5 × 105 ∑i=1Q |tnamei| ≤ 5 × 105 Note: |s| means the length of the string s.

Output

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

Sample

Input

Output

3
25 4 33
abcba
abbaa
abacaba
2
abb 2 3
abcd 1 3

66
75

For traveler #1, LCP("abbaa", "abb") = 3 which is "abb", so the joyfulness = 3 × 4 = 12. LCP("abacaba", "abb") = 2, which is "ab", so the joyfulness = 2 × 33 = 66. Since 66 is the maximum joyfulness, hence the result is 66.