Robot vacuum cleaner

The professor has decided to create a robot vacuum cleaner to automate the task of cleaning rooms. This robot uses sensors to scan the room and assess the level of dirt, forming a dirtiness matrix.

Your task is to determine the optimal starting location for the robot vacuum to maximize dirt collection, based on the provided dirtiness matrix. You are given the number of moves the robot can make, as well as its movement algorithm, which is defined by a string of characters: R (right), L (left), U (up), and D (down). If the robot reaches the boundary of the room and tries to move into a wall, it will instead move in the opposite direction.

Calculate the maximum amount of dirt the robot can collect and identify the cell where it should start.

Input Data

The first line contains two integers, N and M, representing the height and width of the room (2 ≤ N, M ≤ 100).

The second line contains the integer K, which is the number of steps the robot can take (1 ≤ K ≤ 10,000).

The third line provides the sequence that defines the robot's movement algorithm.The following N lines each contain M integers, representing the dirtiness level in each cell P[ij] (0 ≤ P[ij] ≤ 100).

Output Data

Output a single line with three numbers separated by spaces: the maximum dirt the robot can collect, the row number, and the column number of the starting cell.

If multiple starting cells yield the same maximum dirt collection, choose the one with the smallest sum of indices. If there is still a tie, select the cell closest to the left side of the room.

Examples

Note

For example, placing the robot in cell (4,1) allows it to collect 8 units of dirt immediately. It then moves four steps to the right (RRRR), collecting a total of 34 units of dirt. When the robot reaches the wall and cannot move further right (R), it moves left (L) instead, but this cell has already been cleaned. It then takes the final step to the right (R) into a cell that is also already cleaned.

Example Illustration

The robot will follow this sequence of cells:

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