Description

Imagine you’ve arrived at the annual NTHU Career & Recruitment Fair, where along a long corridor there are N drink booths arranged in a line from the entrance to the exit. To reflect differences in foot traffic and location value:

• Booths at the two ends (near the entrance and exit) see the most people and therefore charge higher prices.

• Mid-corridor booths have more dispersed traffic and tend to be cheaper.

• Every drink type appears at least three times, and no two booths selling the same drink ever charge the same price.

You want to quantify each drink’s popularity score based on the sequence of its prices as you walk by.

If a drink appears at booths in positions 1 ≤ i₁ < i₂ < ⋯ < i_m ≤ N with corresponding prices p₁ ​, p₂ ​, … , p_m then its popularity score is defined as max(p_u ​- p_v ​+ p_w)​ , for all u < v < w .

Intuitively, you pick three visits in chronological order—an early booth at price p_u, a middle booth at p_v, and a later booth at p_w—and compute p_u ​- p_v ​+ p_w​. Because end booths are pricier (more foot traffic) and middle booths are cheaper (less traffic), this formula captures “high-end interest” at both ends minus the mid-corridor bargain.

Note: This scoring formula does not imply that mid-corridor booths are always cheaper than end booths; it is simply one way to capture the overall trend in a drink’s popularity.

Input

The first line contains a single integer N, the total number of drink booths arranged in a line at the NTHU Career & Recruitment Fair.

The second line contains N space-separated strings s₁,s₂,…,s_N , where sis_isi​ is the name of the drink sold at booth i.

The third line contains N space-separated integers a₁,a₂,…,a_N , where aia_iai​ is the price charged by booth i.

The fourth line contains an integer Q, the number of queries you will make, and then q more lines each containing a single string T_j​ ; each T_j​​ is guaranteed to match at least one of the s_i​.

Constraints

• 1 ≤ N,Q ≤ 2 × 10⁵

• 1 ≤ | S_i |,| T_j |  ≤ 10

• 1 ≤ a_i ≤ 10⁸

^​Subtasks

• Testcases 1 ~ 3: S_i ,T_j   = "a"

• Testcases 4 ~ 6: N,Q ≤ 1000

• Testcases 7 ~ 10: No additional restrictions

^​Hints

1. Use a map<string, vector<int>> to collect, for each drink S, the list of its prices in the exact order they appear. That way each query can immediately grab the price‐sequence for its drink.
2. You want the largest p_u​ before v and the largest p_w​ after v.
   • Initialize a set suffix containing all prices for this drink.
   • Keep an empty set prefix.
   • As you scan each price p_v in order, remove p_v from suffix, if prefix and suffix are both nonempty, compute max(best,^∗prefix.rbegin()+^∗suffix.rbegin() − p_v), and then Insert p_v into prefix.
3. If the same drink is queried more than once, store its computed score in a map<string,int> ans so you only do the above scan once per drink.
4. Each drink’s price-vector is scanned once, and each insertion/erase into a balanced set costs O(log⁡ m). Overall you get O(nlog⁡n + q), which is fast enough up to 2×10⁵.

Output

For each of the Q queried drink names T_j, output on its own line the popularity score of that drink: the maximum value of p_u ​- p_v ​+ p_w over all triples of distinct occurrences u < v < w in the sequence of prices for drink T_j.

Sample Input  Download

Sample Output  Download

Discuss