Description

Given \(N\) integers \(a_1 \dots a_N\) and \(M\) queries.
In each query, you will be given one integer \(x\), please output an integer in \(a\) which is closest to \(x\).
If there are more than one such integer, please output the smaller one.

ps. We suggest you use std::set to do this problem :)

Input

The first line contains two integers \(N, M\).
The second line contains \(N\) integers \(a_1, a_2 \dots a_N\)
Each of the next \(M\) lines contains an integer \(x\).

\(N \quad M\)
\(a_1 \quad a_2 \dots a_N\)
\(x_1\)
\(\vdots\)
\(x_M\)

Constraints

• \(1 \le N, M \le 10^5\)
  
• \(0 \le a_i, x_i \le 10^9\)

Output

Please output the answer of each query.

Sample Input  Download

Sample Output  Download

Tags

Discuss

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. Due to foot-traffic and location, prices vary significantly.

Booths near the two ends (entrance and exit) typically have higher visibility and can charge higher prices.

Mid-corridor booths generally have less concentrated traffic, leading to potentially lower prices.

Each type of drink appears at least three times, and booths selling the same drink may charge identical prices.

You wish to evaluate each drink’s popularity score and determine the number of distinct booth combinations that achieve this score, based on their price distribution as you walk by.

Suppose a drink appears at booths 1 ≤ i₁ < i₂ < ⋯ < i_m ≤ N with corresponding prices p₁ ​, p₂ ​, … , p_m.

Define:

• The popularity score S = max(p_u ​- p_v ​+ p_w)​ , for all u < v < w 

• The number of distinct triples reaching this maximum score C = (the number of (u,v,w) such that p_u ​- p_v ​+ p_w = S), counted modulo 10⁹+7.

Intuitively, you select an early booth at price p_u, a middle booth at price p_v, and a later booth at price p_w; higher outer prices combined with a lower middle price yield a higher popularity score.

Note: This formula does not necessarily imply mid-corridor booths are always cheaper, but it helps capture a general trend in drink 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 s_i​ is the name of the drink sold at booth i.

The third line contains N space-separated integers a₁,a₂,…,a_N , where a_i​ 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⁸

• Every drink appears at least three times.

• Every queried drink T_j matches at least one of the drinks s_i.

Subtasks

• Testcases 1 ~ 2: s_i ,T_j   = "a", no duplicate prices for the same drink.(The number of triples C is always equal to 1)

• Testcases 3 ~ 4: N,Q ≤ 1000, no duplicate prices for the same drink.(The number of triples C is always equal to 1)

• Testcases 5 ~ 6: No duplicate prices for the same drink.(The number of triples C is always equal to 1)

• Testcases 7 ~ 8: The number of triples C ≤ 10.

• Testcases 9 ~ 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 retrieve the price-sequence for its drink.
2. Basic multiset usage
   • ​​A multiset allows multiple elements with equivalent values, whereas a set enforces uniqueness.
   • Internally, both are typically implemented as balanced binary trees, so most operations have O(log n) complexity.
   • find(val) returns an iterator to one matching element (not all of them).

   • ms.erase(val) removes all elements equal to val.

   • To remove only a single occurrence, use auto it = ms.find(val); if (it != ms.end()) ms.erase(it)
3. You want the largest p_u before v and the largest p_w after v.
4. Initialize a multiset suffix containing all prices for this drink and a parallel map cntSuffix that records, for every price x, how many times x currently appears in suffix.
5. Keep an empty multiset prefix and an empty map cntPrefix; they will hold prices (and their multiplicities) that lie to the left of the current position.
6. As you scan each price p_v in order:
   • Remove p_v from suffix, decrement cntSuffix[p[v]].
   • If both prefix and suffix are nonempty, update the best value best = max(best,^∗prefix.rbegin()+^∗suffix.rbegin() − p_v).
   • Accumulate the number of ways by multiplying the occurrences of L and R: ways += cntPrefix[L] × cntSuffix[R] (mod 10⁹+7).
   • Insert p_v into prefix and increment cntPrefix[p[v]].
   • If the same drink is queried more than once, store its computed score in a map<string, vector<int>> ans to avoid repeated computation.
7. Cache the pair (best, ways) in map<string, pair<ll,ll>> ans so that a repeated query for the same drink returns in O(log n) time without recomputation.
8. 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 + qlog⁡n), which is fast enough up to 2×10⁵.

Output

For each query T_j, output a single line containing two integers:

• S(T_j): the maximum popularity score.

• C(T_j): the number of triples that achieve this score, modulo 10⁹+7.

Sample Input  Download

Sample Output  Download

Tags

Discuss