Робот-пылесос

Профессор решил создать робот-пылесос для автоматизации уборки комнаты. Этот робот, используя датчики, сканирует помещение и определяет уровень загрязнения, формируя матрицу загрязненности.

Ваша задача — определить, с какого места в комнате следует начать уборку, чтобы собрать максимальное количество грязи. Известно, сколько перемещений может сделать робот, а также задан циклический алгоритм его работы, представленный строкой из букв R (вправо), L (влево), U (вверх), D (вниз). Если робот достигает границы комнаты и пытается выйти за пределы, он делает шаг в противоположную сторону.

Определите максимальное количество грязи, которое может собрать робот, и координаты клетки, где его следует разместить.

Входные данные

Первая строка содержит числа N и M — высоту и ширину комнаты (2 ≤ N, M ≤ 100).

Вторая строка содержит число K — количество шагов, которые может сделать робот (1 ≤ K ≤ 10 000).

Третья строка задает последовательность движений робота.

Далее следуют N строк, каждая из которых содержит M чисел — уровень загрязненности в соответствующей клетке P[ij] (0 ≤ P[ij] ≤ 100).

Выходные данные

Выведите в одной строке три числа через пробел: максимальное количество грязи, которое может собрать робот, номер строки и номер столбца клетки, где его нужно разместить.

Если таких клеток несколько, выберите ту, у которой наименьшая сумма индексов. Если и таких несколько, выберите ту, что ближе к левой стороне комнаты.

Примеры

Примечание

Разместив робот в клетке (4,1), он сразу собирает 8 единиц мусора, затем выполняет четыре шага вправо (RRRR), собирая в сумме 34 единицы мусора. Когда робот достигает стены и не может двигаться вправо (R), он делает шаг влево (L), но эта клетка уже очищена. Затем выполняется последний шаг вправо (R) в клетку, которая также уже очищена.

Иллюстрация к примеру

Робот пройдет по следующей последовательности клеток:

(4,1) R -> (4,2) R -> (4,3) R -> (4,4) R -> (4,5) R L -> (4,4) R -> (4,5).