Робот-пилосос

Професор для автоматизації прибирання кімнати вирішив змайструвати робот-пилосос. Робот-пилосос за допомогою датчиків сканує приміщення і визначає рівень забруднення у ньому, складаючи матрицю забрудненості.

За заданою матрицею забрудненості визначте, з якого місця потрібно почати прибирання кімнати, щоб зібрати як можна більше бруду. Відомо кількість переміщень, яку може зробити робот-пилосос та циклічний алгоритм роботи робота-пилососа, який задається текстовим рядком, що складається з літер 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).