Государство Ребляндия является заклятым врагом Берляндии на политической карте мира. Буквально на днях власти Берляндии арестовали ребляндского шпиона, пытавшегося несанкционированно провезти на территорию Берляндии различные листовки, предназначенные для агитационной пропаганды и подрыва морали населения. Многие из них содержат подстроки Абсолютно Недопустимого Ругательства, а возможно даже (страшно подумать!) это слово целиком.
Для определения степени вины в берляндской правовой системе используется достаточно сложный алгоритм, который мы не будет приводить в этой задаче целиком. Скажем лишь, что частью экспертизы является следующая процедура.
Каждой из m листовок, провезённых шпионом через границу, присваивается порядковый номер от 1 до m. После этого необходимо получить ответы на q запросов следующего вида: «В какой из листовок из диапазона номеров [l, r] подстрока Абсолютно Недопустимого Ругательства [pl, pr] встречается чаще всего?».
Так как в этот раз тексты листовок оказались очень большими, эксперт попросил вас автоматизировать эту часть анализа данных. Помогите ему!
Выходные данные
Выведите q строк, i-я строка должна содержать два целых числа — номер текста, на котором достигается максимум и число вхождений в этот текст подстроки [pl, pr] строки s. Если возможных номеров текстов несколько, выведите наименьший.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
suffixtree
3
suffixtreesareawesome
cartesiantreeisworsethansegmenttree
nyeeheeheee
2
1 2 1 10
1 3 9 10
|
1 1
3 4
|