Word Filter

You are required to implement a word filtering system. The system stores a collection of words and processes queries to search for the first word (in insertion order) that begins with a given prefix and ends with a given suffix. The search should be case-insensitive. If no word matches the conditions, output None.

Note: Input is read from stdin and output is printed to stdout. If a query has multiple valid answers, only the first inserted matching word is returned.

In mathematical notation, for a word w and given prefix p and suffix s, a word matches if:

[ w \text{ starts with } p \quad \text{and} \quad w \text{ ends with } s. ]

All words and queries must be processed in a case-insensitive manner.

inputFormat

The input begins with an integer \(n\) representing the number of words. The next line contains \(n\) words separated by spaces.

The following line contains an integer \(q\) representing the number of queries. Each of the next \(q\) lines contains two strings: a prefix and a suffix.

Input Format:

 n
 word1 word2 ... wordn
 q
 prefix1 suffix1
 prefix2 suffix2
 ...

outputFormat

For each query, output the first word that has the given prefix and suffix (after converting everything to lowercase). If no such word exists, output None.

Output Format:

 result1
 result2
 ...

## sample

3
apple banana grape
4
ap le
ban na
gr ape
gr ple

apple
banana
grape
None

</p>