시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB0000.000%

문제

Будем называть цепочкой слов длины 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. Если оптимальных ответов несколько, выведите любой из них. Разделяйте числа пробелом.

예제 입력 1

3
a
ab
abc
3
1 2 3

예제 출력 1

1 3

예제 입력 2

6
a
ab
bc
bcd
add
bcde
11
1 1 5 3 2 3 4 4 4 6 5

예제 출력 2

6 7