E. Судебная экспертиза
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
768 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Государство Ребляндия является заклятым врагом Берляндии на политической карте мира. Буквально на днях власти Берляндии арестовали ребляндского шпиона, пытавшегося несанкционированно провезти на территорию Берляндии различные листовки, предназначенные для агитационной пропаганды и подрыва морали населения. Многие из них содержат подстроки Абсолютно Недопустимого Ругательства, а возможно даже (страшно подумать!) это слово целиком.

Для определения степени вины в берляндской правовой системе используется достаточно сложный алгоритм, который мы не будет приводить в этой задаче целиком. Скажем лишь, что частью экспертизы является следующая процедура.

Каждой из 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