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