3066: 彩虹岛上最幸运的人

彩虹岛的居民们相信拥有较大字典序名字的人更幸运，$cnx$得到了她$n$个学生的姓名花名册，这$n$个学生的编号分别为$1,2,\cdots,n$,编号为$i$学生的姓名被表示为字符串$s_i$。为了测试$cnx$对她的班级学生的了解程度，$hyd$打算询问其$m$个问题，每个问题可以用两个数字$q_l$,$q_r$表示，代表查询所有编号在$[q_l,q_r]$的学生中最幸运的学生姓名，换句话说，对于输入的字符串，$cnx$需要回答第$q_l$个至第$q_r$个字符串中字典序最大的字符串是什么。现在请你帮助$cnx$找到合适的算法高效地回答这$m$个问题。

如果你不清楚字典序的含义，你可以联系英语词典的编排顺序参考以下解释：假设现有多个字符串需根据其字典序排序（字典序小的排在前面），显然的做法是先按照第一个字母、以 $a,b,c,\cdots,z$ 的顺序排列；如果第一个字母一样，那么比较第二个、第三个乃至后面的字母。如果比到最后两个单词不一样长（比如$ab$ 和 $abc$），那么把短者排在前。例:将$ac$，$ab$，$abc$ 三者根据字典序排序后将得到$ab$，$abc$，$ac$，其中$ac$是这三者中字典序最大的字符串。

输入第一行包含两个数$n(1 \le n \le 100000)$，$m(1 \le m \le 200000)$，分别表示学生数量与询问数量；

接下来的n行每行有一个字符串，第i行的字符串代表编号为i的学生姓名$s_i$，$s_i$中只包含小写字母，其长度不超过15；

最后m行每行有两个数，代表每个询问的$q_l$，$q_r$。

对于每个询问输出一个字符串，为第$q_l$个至第$q_r$个字符串中字典序最大的字符串。

4 3
ww
lhj
stj
zzy
1 4
2 3
1 2

zzy
stj
ww