410229: GYM103987 E 2584

Getting bored with playing 2048, Awson came up with a new game called 2584, and he asks you to simulate the game for him.

There is a board with $$$n\times n$$$ cells, some of which are occupied with Fibonacci numbers or obstacles. Recall that Fibonacci sequence $$$F$$$ is an infinite sequence of numbers in which each number (Fibonacci number) is the sum of the previous two, i.e. $$$$$$ F_n=\begin{cases} 1 & n=1 \\ 2 & n=2 \\ F_{n-1}+F_{n-2} & n\ge 3 \end{cases} $$$$$$

You are given a sequence of $$$Q$$$ operations where each operation is one of "LRUD", indicating the directions: left, right, up and down, respectively. In each operation, you should

• In the corresponding direction, arbitrarily take one of the foremost numbers which is not taken before. Let it be $$$x$$$.
• Move towards the number in that direction, until it reaches the border or a non-empty cell.
• If the cell in front of $$$x$$$ is a number (denoted as $$$y$$$) satisfying
  • $$$y$$$ is not changed in the current operation.
  • $$$y$$$ is adjacent to $$$x$$$ in Fibonacci sequence.
  then add $$$x$$$ to $$$y$$$ (we call that $$$y$$$ is changed), and delete $$$x$$$ ($$$x$$$ will become an empty cell).
• Repeat the instructions above until all numbers have been taken.

You need to show Awson the board after executing all operations. Note that no new numbers will be generated in this game.

The first line contains two integers $$$n\ (1\le n\le 100)$$$ and $$$Q\ (1\le Q\le 100)$$$, the size of the board and the number of operations.

Each of the next $$$n$$$ lines contains $$$n$$$ integers, where the $$$j$$$-th number of the $$$i$$$-th line is $$$a_{i,j}\ (-1\le a_{i,j}\le 2584)$$$. The cell on line $$$i$$$ column $$$j$$$ is empty if $$$a_{i,j}=0$$$, an obstacle if $$$a_{i,j}=-1$$$, or a Fibonacci number otherwise. It is guaranteed that $$$a_{i,j}$$$ is either $$$0$$$, $$$-1$$$ or a Fibonacci number.

The last line is a string of length $$$Q$$$ consisting of "LRUD", representing the direction of operations.

Output $$$n$$$ lines, each line containing $$$n$$$ integers separated by spaces, representing the board after all operations. The output format should be the same with input.

The problem contains several subtasks. You can get the corresponding score for each passed test case.

• Subtask 1 ($$$40$$$ points): for all $$$i$$$ and $$$j$$$, $$$a_{i,j}\ge 0$$$.
• Subtask 2 ($$$60$$$ points): no additional constraints.

4 1
2 3 2 3
3 -1 0 2
1 0 0 1
3 2 3 5
R

0 0 5 5 
3 -1 0 2 
0 0 1 1 
0 0 5 8 

2 6
2584 1597
1597 987
LLDRLD

0 0 
6765 0 

5 2
2 3 5 3 8
3 5 -1 -1 2
1 0 0 2 3
-1 -1 0 2 3
1 1 1 1 3
LU

13 8 8 0 5 
3 3 -1 -1 0 
0 0 5 1 0 
-1 -1 1 0 0 
1 1 0 0 0 

Take operation R and sequence $$$[2,3,2,3]$$$ as an example (the first line in example 1). The operation contains the following $$$4$$$ steps.

• Step $$$1$$$. The rightmost number $$$3$$$ is taken. Since $$$3$$$ is already at the border, the sequence will remain the same.
• Step $$$2$$$. Now the rightmost number is $$$2$$$, because $$$3$$$ is already taken. The number in front of $$$2$$$ is $$$3$$$. Merge the two numbers and it becomes $$$[2,3,0,5]$$$.
• Step $$$3$$$. Move $$$3$$$ to the right and it becomes $$$[2,0,3,5]$$$. Though $$$3$$$ and $$$5$$$ are adjacent in Fibonacci sequence, $$$5$$$ is merged in step $$$2$$$, so $$$3$$$ cannot merge with $$$5$$$.
• Step $$$4$$$. Move $$$2$$$ to the right and merge with $$$3$$$. Finally, the sequence becomes $$$[0,0,5,5]$$$.