Будем называть цепочкой слов длины n последовательность слов w
1, w
2, …, w
n, такую, что для всех i от 1 до n – 1 слово w
i является собственным префиксом слова w
i+1.
Слово u длины k называется собственным префиксом слова v длины l, если l > k и первые k букв слова v совпадают со словом u. Например, «program» является собственным префиксом слова «programmer».
Задано множество слов S = {s
1, s
2, …, s
m} и последовательность чисел x[1], x[2], …, x[k]. Требуется найти такие числа l и r (l ≤ r), что s
x[l], s
x[l + 1], …, s
x[r – 1], s
x[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. Если оптимальных ответов несколько, выведите любой из них. Разделяйте числа пробелом.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
zngs
rjzr
zng
3
3 1 1
|
1 2
|
|
2
|
6
gjnuitvaowpy
gjnuitvaowpym
gjnuitvaowp
rjzrociinzeco
tgbotnzepnvm
aigqbzpnerv
9
2 3 1 2 3 1 2 3 1
|
2 4
|