시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

Гидеон нашел древний свиток, позволяющий активировать мощнейшее заклинание, которое помогает решить любую задачу. Осталось провести ритуал.

На свитке изображена прямоугольная таблица, содержащая $n$ строк и $m$ столбцов, в каждой ячейке которой написана латинская буква. Заклинание представляет собой строку, также состоящую из латинских букв. Чтобы активировать заклинание, необходимо бесконечное число раз произнести эту строку, перемещая при этом конец волшебной палочки по таблице на свитке вдоль подходящей циклической последовательности ячеек.

Назовем циклической последовательностью ячеек такую последовательность ячеек $(x_1, y_1), (x_2, y_2) \ldots (x_k, y_k)$, что каждая пара соседних в последовательности ячеек, а также первая и последняя ячейки в последовательности, не совпадают и имеют общую сторону. Таким образом, при перемещении конца волшебной палочки вдоль последовательности, каждый раз необходимо переместиться в соседнюю ячейку вверх, влево, вправо или вниз, а в конце --- вернуться в начальную ячейку. При этом одна и та же ячейка может встречаться в последовательности несколько раз. 

Для активации заклинания требуется найти такую циклическую последовательность ячеек, что если одновременно делать следующее: произность бесконечное число раз строку заклинания, по одному символу в секунду, и, начав с первой ячейки, каждую секунду до бесконечности перемещать конец волшебной палочки к следующей ячейке в последовательности (после последней ячейки следует снова перейти к первой ячейке), то буквы заклинания и буквы в ячейках таблицы всегда будут сопадать.

Помогите Гидеону найти подходящую циклическую последовательность, либо выясните, что такой последовательности не существует.

입력

Первая строка содержит целые числа $n$, $m$ и $l$ --- высоту и ширину таблицы, а также длину заклинания, соответственно ($2 \le n, m \le 200$, $1 \le l \le 200$).

В следующих $n$ строках содержится по $m$ строчных латинских букв --- содержимое таблицы.

В последней строке содержится строка из $l$ строчных латинских букв --- заклинание.

출력

Если искомой последовательности не существует, в единственной строке выведите <<NO>>.

Иначе, в первой строке выведите <<YES>>. Во второй строке выведите $k$ --- длину последовательности, $k$ не должно превышать $10^7$. Гарантируется, что если ответ существует, то существует ответ с $k$, не превышающим $10^7$.

В третьей строке выведите координаты первой ячейки последовательности: сначала номер строки, а потом номер столбца, на пересечении который находится эта ячейка. Наконец, в последней строке выведите строку длины $k$, состоящую из символов <<U>>, <<L>>, <<D>>, <<R>>, которая описывает последовательность перемещения конца волшебной палочки по ячейкам в искомой циклической последовательности последовательности.

Символ <<U>> соответствует переходу из текущей ячейки в соседнюю сверху, символ <<L>> --- в соседнюю слева, <<D>> --- в соседнюю снизу, а <<R>> --- в соседнюю справа.

После переходов по всем символам необходимо вернуться в исходную ячейку. Выходить за границы поля не разрешается.

Если ответов несколько, выведите любой.

예제 입력 1

3 2 4
aa
bb
cc
abcb

예제 출력 1

YES
4
1 1
DDUU

예제 입력 2

3 3 5
abc
dee
ghi
eeeee

예제 출력 2

YES
2
2 2
RL

예제 입력 3

3 3 5
abc
def
ghi
eeeee

예제 출력 3

NO

예제 입력 4

3 6 16
abegme
ckwass
ichrdq
egassemsdrawkcab

예제 출력 4

YES
16
1 3
RDRRULDDLULLLURR

힌트

Пояснение к третьему тесту. По определению, последовательность из одной ячейки не является циклической, поэтому решения не существует.