蒟蒻 HansBug 在一本英语书里面找到了一个单词表，包含 N 个单词（每个单词内包含大小写字母）。现在他想要找出某一段连续的单词内字典序最大的单词。

第一行包含两个正整数 N, M，分别表示单词个数和询问个数。

接下来 N 行每行包含一个字符串，仅包含大小写字母，长度不超过 15，表示一个单词。单词大小写不敏感。

再接下来 M 行每行包含两个整数 x, y，表示查询求从第 x 到第 y 个单词中字典序最大的单词。如果有两个单词忽略大小写情况下字典序相同，输出靠后的那个。

输出包含 M 行，每行为一个字符串，分别依次对应 M 个询问的结果

样例说明

第一次操作：在{absi,hansbug,lzn,kkk,yyy}中找出字典序最大的，故为yyy

第二次操作：在{absi}中找出字典序最大的，故为absi

第三次操作：在{absi,hansbug}中找出字典序最大的，故为hansbug

第四次操作：在{hansbug,lzn}中找出字典序最大的，故为lzn

第五次操作：在{kkk}中找出字典序最大的，故为kkk

数据规模