J. 2048 Simulator
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
In this world composed of digits, merging is the only way to evolve...
Figure 1: An example of 2048 game grid

You are given an $$$N \times N$$$ grid. Each cell in the grid contains either a positive integer of the form $$$2^k\ (k \ge 1)$$$ or $$$0$$$ (representing an empty space).

You need to process an operation string $$$S$$$ of length $$$M$$$, consisting of characters L (Left), R (Right), U (Up), and D (Down). For each character in $$$S$$$, you must slide the numbers in the grid according to the rules of the game 2048.

The rules for sliding and merging are as follows:

  1. Slide: All numbers slide in the direction of the instruction until they hit the border or another non-zero number. (e.g., $$$[0, 2, 0, 2]$$$ moving Left becomes $$$[2, 2, 0, 0]$$$ before merging).
  2. Merge: If two adjacent numbers (with no other non-zero numbers between them) in the sliding direction have the same value, they merge into a new number with twice the value.
  3. Priority:
    • Single Merge Rule: In a single move, each tile (including those created by a merge) can participate in at most one merge.
    • Directional Priority: Merges always happen from the front of the sliding direction.
    • Example: If a row is $$$[2, 2, 2, 2]$$$ and moves Left (L), the leftmost two 2 merge first, then the remaining two 2 merge. The result is $$$[4, 4, 0, 0]$$$. It is not $$$[8, 0, 0, 0]$$$ nor $$$[4, 2, 2, 0]$$$.
    • Example: If a row is $$$[4, 2, 2, 0]$$$ and moves Left (L), the result is $$$[4, 4, 0, 0]$$$.

Note: Unlike the original game, new tiles are not generated in empty spots after a move.

Input

The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \le N \le 20, 1 \le M \le 100$$$), representing the size of the grid and the length of the operation string.

The next $$$N$$$ lines each contain $$$N$$$ integers $$$A_{i,j}$$$ ($$$0 \le A_{i,j} \le 1024$$$), representing the initial state of the grid. It is guaranteed that all non-zero integers are powers of 2.

The last line contains a string $$$S$$$ of length $$$M$$$, consisting only of the characters L, R, U, and D.

Output

Output $$$N$$$ lines, each containing $$$N$$$ integers, representing the final state of the grid after all operations.

Example
Input
4 4
2 2 2 2
4 2 2 0
0 4 2 2
8 0 0 8
LRLU
Output
16 0 0 0
8 0 0 0
16 0 0 0
0 0 0 0
Note

Visual explanation of the sample case:

Let the state of the grid be denoted by matrices. The transitions are as follows:

$$$$$$ \underbrace{ \begin{pmatrix} 2 & 2 & 2 & 2 \\ 4 & 2 & 2 & 0 \\ 0 & 4 & 2 & 2 \\ 8 & 0 & 0 & 8 \end{pmatrix} }_{\text{Initial State}} \xrightarrow{(1)\ \textbf{L}} \underbrace{ \begin{pmatrix} 4 & 4 & 0 & 0 \\ 4 & 4 & 0 & 0 \\ 4 & 4 & 0 & 0 \\ 16 & 0 & 0 & 0 \end{pmatrix} }_{\text{After L}} \xrightarrow{(2)\ \textbf{R}} \underbrace{ \begin{pmatrix} 0 & 0 & 0 & 8 \\ 0 & 0 & 0 & 8 \\ 0 & 0 & 0 & 8 \\ 0 & 0 & 0 & 16 \end{pmatrix} }_{\text{After R}} $$$$$$

$$$$$$ \xrightarrow{(3)\ \textbf{L}} \underbrace{ \begin{pmatrix} 8 & 0 & 0 & 0 \\ 8 & 0 & 0 & 0 \\ 8 & 0 & 0 & 0 \\ 16 & 0 & 0 & 0 \end{pmatrix} }_{\text{After L}} \xrightarrow{(4)\ \textbf{U}} \underbrace{ \begin{pmatrix} 16 & 0 & 0 & 0 \\ 8 & 0 & 0 & 0 \\ 16 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} }_{\text{Final State}} $$$$$$

Transition Details:

  1. Operation L (Left):
    • Row 1 ($$$[2, 2, 2, 2]$$$): The first two $$$2$$$s merge into $$$4$$$. The next two $$$2$$$s merge into $$$4$$$. Result: $$$[4, 4, 0, 0]$$$.
    • Row 4 ($$$[8, 0, 0, 8]$$$): The zeros are skipped, and the two $$$8$$$s merge. Result: $$$[16, 0, 0, 0]$$$.

  2. Operation R (Right):
    • Row 1 ($$$[4, 4, 0, 0]$$$): They slide to the right. Since they are equal, they merge into $$$8$$$. Result: $$$[0, 0, 0, 8]$$$.
    • Same applies to Rows 2 and 3.

  3. Operation L (Left):
    • All numbers slide back to the left. No merges are possible since each row contains only a single number.

  4. Operation U (Up):
    • Column 1 ($$$[8, 8, 8, 16]^T$$$):
      • The top two $$$8$$$s merge into $$$16$$$.
      • The third $$$8$$$ slides up (cannot merge with the new $$$16$$$ due to the Single Merge Rule).
      • The bottom $$$16$$$ slides up.
    • Result for Col 1: $$$[16, 8, 16, 0]^T$$$.