Папа Васи очень заботится об образовании сына. Особое значение он придает иностранным языкам. Недавно они приступили к изучению английского. Чтобы ускорить процесс, папа разговаривает с Васей исключительно на нем. Разумеется, это создает некоторые трудности при общении. Каждый раз, когда Вася что-нибудь скажет, папе приходится долго гадать, что именно он имел в виду.
Папа знает словарный запас сына. Считается, что Вася мог иметь в виду словарное слово P, если оно входит как подпоследовательность в слово T (то, что он сказал). Другими словами, если существует такая возрастающая последовательность индексов i1 < i2 < ... < im (где m — длина P), что P[j] = T[ij] для всех j = 1..m.
Вам дается словарный запас Васи и сказанное им слово. Для каждого словарного слова надо определить, мог ли Вася иметь его в виду.

Формат входных данных
В первой строке входного файла содержится единственное число K.
В следующих K строках идут слова из словаря, по одному на каждой строке. На последней (K + 2)-й строке входного файла содержится слово, сказанное Васей, длиной не более 100 000. Все слова в словаре непустые.
Все слова состоят из строчных латинских букв. Гарантируется, что суммарная длина слов из словаря не превышает 1 000 000 символов.

Формат выходных данных
В выходной файл выведите K строк. В i-й строке должно быть записано ‘YES’, если Вася мог иметь в виду слово номер i из словаря, и ‘NO’ в противном случае.

Рассмотрим сначала простейший случай K = 1. Как проверить, мог ли Вася, сказав слово T, иметь в виду P? Для этого будем просто бежать по T одним циклом, также используя счетчик j, равный сначала 1. Как только текущий символ T совпадает с P[j], надо увеличить j на единицу. Если J так и не превысил m, то не найдется последовательности, удовлетворяющей определению (иначе алгоритм бы ее нашел), и Вася не мог иметь P в виду. В противном случае --- последовательность существует и ответ положительный. Такой алгоритм работает за O(n), где n --- длина T.

Если применять этот способ для каждого словарного слова, может получиться так, что по T вы пробежимся K раз --- а это слишком долго.

Для решения данной задачи используется идея, позволяющая проверять слово P длины m за m действий (конечно, с некоторой предподготовкой для T).

Пусть next[i][x] --- минимальная (самая правая позиция) вхождения символа x в T, начиная с i + 1 (здесь 0 < i < n + 1). Другими словами,

next[i][x] = min{ j: j > i и T[j] = x }.

Если такого символа нет правее позиции i, то будем считать next[i][x] = -1.
Чтобы вычислить next, будем бежать c конца T, поддерживая в массиве last[‘a’..‘z’] искомые ближайшие позиции для каждого символа:

for c := ‘a’ to ‘z’ do last[c] := -1;
for i := n downto 0 do begin
for c := ‘a’ to ‘z’ do next[i][c] := last[c];
if (i > 0) then last[T[i]] := i;
end;

С помощью next легко модифицировать старый алгоритм, чтобы он уже работал за O(m):

j := 1;
I := 0;
While (j <= m) do begin
I := next[i][P[j]];
If (I = -1) then break;
J := j + 1;
End;

Аналогично, если j получилось больше m, то найдется последовательность, удовлетворяющая определению, то есть Вася мог иметь в виду P. В противном случае (j <= m) такой последовательности нет.

Чтобы проверить все K словарных слов, потребуется S (суммарная длина всех слов) + T*26 (расходы по вычислению next), получаем 3.6*10^6 в худшем случае. Как известно, такая оценка для алгоритма приемлема.