#LUOGUP1841. 查单词

查单词

题目背景

滚粗了的 HansBug 在收拾旧英语书,然而他发现了什么奇妙的东西。

题目描述

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

输入格式

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

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

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

输出格式

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

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

提示

样例说明

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

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

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

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

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

数据规模

N<=50000,M<=100