28607번 - Палиндромная шифровка 다국어

Кейтлин Кирамман удалось поймать одного из приспешников Силко и найти у него зашифрованное сообщение из $n$ строк $s_1, s_2, \ldots, s_n$, составленных из маленьких латинских букв. Длина каждой строки $|s_i|$ не превосходит $1000$.

К сожалению, сообщение оказалось неполным, и, не имея всего текста, расшифровать послание нельзя. Известно, что каждая полученная строка $s_i$ является правой долей $i$-й части сообщения, то есть у каждой строки не хватает некоторого префикса (возможно, пустого). Также известно, что изначально каждая часть сообщения была палиндромом. То есть, в конечном итоге, каждая $s_i$ --- это суффикс некоторого палиндрома.

В поисках недостающих частей Кейтлин обратилась в архив, где ей выдали $m$ строк $t_1, t_2, \ldots, t_m$, которые потенциально могут дополнять строки $s_i$ до палиндромов. Каждая строка $t_i$ также состоит из маленьких латинских букв.

Кейтлин хочет проверить, могут ли полученные в архиве материалы быть кусками исходной шифровки. Для этого ей для каждой строки $t_i$ нужно понять, существует ли такое $j$, что $t_i + s_j$ --- палиндром (здесь за знак сложения обозначена операция конкатенации).

В первой строке ввода через пробел даны два целых числа $n$ и $m$ ($1 \leqslant n \leqslant 1000$; $1 \leqslant m \leqslant 10^6$).

Во второй строке перечислены $n$ строк $s_1, s_2, \ldots, s_n$, разделенные пробелами.

Третья строка в том же формате содержит $m$ строк $t_1, t_2, \ldots, t_m$, разделенные пробелами. Гарантируется, что $\sum\limits_{i=1}^m |t_i| \leqslant 10^6$.

Для каждой строки $t_i$ выведите на отдельной $i$-й строке слово <<YES>> (без кавычек), если существует такое $j$, что $t_i + s_j$ --- палиндром, и <<NO>> иначе.