P2412 Word Lookup

While sorting his old English books, HansBug found something curious.

HansBug found a word list in an English book, containing $N$ words (each word consists of uppercase and lowercase letters). He wants to find the lexicographically largest word within a contiguous segment.

The first line contains two positive integers $N$ and $M$, representing the number of words and the number of queries. The next $N$ lines each contain a string consisting only of uppercase and lowercase letters, with length at most $15$, representing a word. Words are case-insensitive. The next $M$ lines each contain two integers $x$ and $y$, asking for the lexicographically largest word from the $x$-th to the $y$-th word. If two words are the same in lexicographical order when ignoring case, output the one that appears later.

Output $M$ lines, each containing a string, corresponding to the results of the $M$ queries in order.

### Sample Explanation First operation: find the lexicographically largest in $\tt\left\{absi,hansbug,lzn,kkk,yyy\right\}$, which is $\tt yyy$. Second operation: find the lexicographically largest in $\tt\left\{absi\right\}$, which is $\tt absi$. Third operation: find the lexicographically largest in $\tt\left\{absi,hansbug\right\}$, which is $\tt hansbug$. Fourth operation: find the lexicographically largest in $\tt\left\{hansbug,lzn\right\}$, which is $\tt lzn$. Fifth operation: find the lexicographically largest in $\tt\left\{kkk\right\}$, which is $\tt kkk$. ### Constraints  Translated by ChatGPT 5