A catalog lists n words indexed 0..n-1 in the given order (duplicate words may appear; the higher index wins). For each of q queries, each giving a prefix and a suffix, report the largest index i such that word i has the given prefix and the given suffix at the same time; if no word qualifies, report -1.
A standard trie method inserts, for every word, each of its suffixes joined to the whole word by a separator, so a single lookup keyed by suffix then separator then prefix resolves each query. All words, prefixes, and suffixes consist of lowercase English letters only.
Input format
Line 1: an integer n.
Line 2: n space-separated catalog words.
Line 3: an integer q.
Each of the next q lines: two space-separated strings, a prefix and a suffix.
Output format
Print q lines; line i is the answer to query i.
Constraints
- 1 <= n <= 3000
- 1 <= q <= 3000
- Each word has length 1..12, lowercase letters.
- Each prefix/suffix has length 1..12, lowercase letters.