Цепочка слов
시간 제한2초메모리 제한1024 MB
단어 집합과 인덱스 수열이 주어질 때, 각 단어가 다음 단어의 진접두사인 연속 구간 중 가장 긴 것을 찾는다.
문제
Будем называть цепочкой слов длины n последовательность слов w1, w2, …, wn, такую, что для всех i от 1 до n – 1 слово wi является собственным префиксом слова wi+1.
Слово u длины k называется собственным префиксом слова v длины l, если l > k и первые k букв слова v совпадают со словом u. Например, «program» является собственным префиксом слова «programmer».
Задано множество слов S = {s1, s2, …, sm} и последовательность чисел x[1], x[2], …, x[k]. Требуется найти такие числа l и r (l ≤ r), что sx[l], sx[l + 1], …, sx[r – 1], sx[r] является цепочкой слов, и количество слов в цепочке (число r – l + 1) максимально.
입력
Первая строка входного файла содержит целое число m (1 ≤ m ≤ 250 000). Каждая из следующих m строк содержит по одному слову из множества S.
Все слова не пусты, имеют длину, не превосходящую 250 000 символов, и состоят только из строчных букв латинского алфавита. Суммарная длина всех слов не превосходит 250 000.
Следующая строка содержит число k (1 ≤ k ≤ 250 000). Последняя строка входного файла содержит k чисел — последовательность чисел x[1], x[2], …, x[k] (для всех i выполнено 1 ≤ x[i] ≤ m).
출력
Выведите в первой строке выходного файла два числа: l и r. Если оптимальных ответов несколько, выведите любой из них. Разделяйте числа пробелом.