Description

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.

Input Format

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 Format

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

5 5
absi
hansbug
lzn
kkk
yyy
1 5
1 1
1 2
2 3
4 4

yyy
absi
hansbug
lzn
kkk

Hint

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