Word Filter

You are given a list of lowercase words and a series of queries. In each query, a prefix and a suffix are provided. Your task is to find the word in the list that has the given prefix and suffix, and output its index. If there is more than one valid answer, return the largest index. If no word matches, return -1.

Note: The index of the words is 0-based.

For example, given the list ["apple", "banana", "apricot"]:

Query: prefix = "ap", suffix = "e"   -> Output: 0
Query: prefix = "ba", suffix = "a"   -> Output: 1
Query: prefix = "ap", suffix = "ot"  -> Output: 2
Query: prefix = "ap", suffix = "p"   -> Output: -1

The solution essentially checks each word to determine whether it starts with the given prefix and ends with the given suffix.

Complexity Analysis: In the worst-case, for each query, you may scan through all words. If there are n words and q queries, a naive solution might run in O(q*n*L) (where L is average word length), which is acceptable given moderate constraints.

Additionally, if any formulas are needed, they should be written in LaTeX format. For example, the time complexity can be expressed as: \(O(q \times n \times L)\).

inputFormat

The input is given in the following format from standard input:

 n
 word_1 word_2 ... word_n
 q
 prefix_1 suffix_1
 prefix_2 suffix_2
 ...
 prefix_q suffix_q

Where:

• n is the number of words (an integer).
• The next line contains n space-separated lowercase words.
• q is the number of queries.
• Each of the following q lines contains two strings representing a prefix and a suffix.

outputFormat

For each query, print the index of the word satisfying the conditions on a new line. If no such word exists, print -1. The output should be sent to standard output.

## sample

3
apple banana apricot
4
ap e
ba a
ap ot
ap p

0
1
2
-1

</p>