Imagine an infinite grid where each cell contains 0. However, the cells in a rectangle of size N × M, with the top-left cell at coordinates (1, 1) and the bottom-right cell at (N, M), have their own values a_ij.

A robot starts at cell (1, 1) and is given a program S. This program consists of 4 different command symbols:

• ‘R’ — the robot moves right, meaning from cell (x, y) the robot will move to cell (x, y+1);
• ‘D’ — the robot moves down, meaning from cell (x, y) the robot will move to cell (x+1, y);
• ‘L’ — the robot moves left, meaning from cell (x, y) the robot will move to cell (x, y−1);
• ‘U’ — the robot moves up, meaning from cell (x, y) the robot will move to cell (x−1, y).

Each time the robot enters a cell, it adds the value from that cell to a total sum (including the starting cell (1, 1)). The result of the program is the sum obtained after executing all commands.

There is a hypothesis that the given program for the robot will not yield the minimum possible sum, and we would like the result to be as small as possible. You can move exactly one command from the given program to any position in the same program (including its original position). Among all possible programs that can result from this operation, output the one that yields the smallest result.

The first line contains two integers N and M — the dimensions of the rectangle (1 ≤ N, M ≤ 10⁵, N · M ≤ 10⁵).

The next N lines contain M integers a_ij — the value in cell (i, j) (|a_ij| ≤ 10⁹).

The last line describes the program S, consisting of the symbols ‘R’, ‘D’, ‘L’ and ‘U’ (2 ≤ |S| ≤ 10⁵).

Output the program that can be obtained by moving one command to any position in the program S and whose result will be the smallest. If there are multiple answers, output any of them.