Problem Description

You are provided with three arrays of the same length n:

• queries[i]: A non-empty string representing the text of the i-th query.
• timestamps[i]: An integer representing the time when queries[i] was issued.
• 0 <= i < n.

Additionally, you receive an array prefixes of length m, where each prefixes[j] is a non-empty string.

For each prefix p in prefixes, your task is to identify all distinct query strings from the queries array that start with p (i.e., query.startsWith(p)). These distinct queries must then be sorted according to the following rules:

1. Descending frequency: The primary sorting key is the number of times that exact query string appears in the queries array.
2. Ascending earliest timestamp: If multiple queries have the same frequency, ties are broken by their earliest timestamp. For a given query string q, find all indices k where queries[k] == q and use min(timestamps[k]) as its earliest timestamp. The query with the smaller earliest timestamp comes first.

The final output should be an array of lists, where result[j] contains the sorted list of matching query strings for prefixes[j].

Assumptions

• 1 <= n, m <= 2 * 10^5. An O(nm) solution will be too slow.
• 1 <= len(queries[i]), len(prefixes[j]) <= 50.
• timestamps[i] fit within a 32-bit signed integer.

Example

Input:

• queries = ["apple", "app", "banana", "app", "application"]
• timestamps = [5, 3, 10, 7, 8]
• prefixes = ["ap", "app", "b"]

Processing for prefix "ap":

• Matching queries: "apple", "app", "app", "application".
• Distinct query strings with frequencies and earliest timestamps:
  • "app": appears 2 times, earliest timestamp = min(3, 7) = 3.
  • "apple": appears 1 time, earliest timestamp = 5.
  • "application": appears 1 time, earliest timestamp = 8.
• Sorted order: "app" (freq 2), then "apple" (freq 1, time 5), then "application" (freq 1, time 8).

Output (conceptually):

• For "ap": ["app", "apple", "application"]
• For "app": ["app", "apple", "application"]
• For "b": ["banana"]