Under construction

Still being built. Things may change

2,147,483,648 Game

Interview

Time limit1sMemory limit512 MB

Summary
Given an 8x8 2048-style board and one arrow key, apply the slide-and-merge rules once and print the resulting board.
Level

Medium4 of 10

Topics
Simulation, Implementation, Array, Matrix
Solved
No attempts yet

Problem

Hojun is playing the 2,147,483,648 game, an extension of 2048.

The 2,147,483,648 game is played on an (8 \times 8) board. You move tiles that hold integers of the form (2^k) ((1 \le k \le 30)) using the arrow keys, and the goal is to create (2,147,483,648(=2^{31})). When an arrow key is pressed, the game proceeds by the following rules.

  1. Push all tiles in the direction of the pressed arrow key until they hit the wall.
  2. If two tiles with the same number are adjacent in the pushing direction, merge those two tiles. If three or more are adjacent, merge them two at a time, starting from the pair closest to the wall the arrow key points toward.
  3. In a single arrow key input, no tile is merged more than once.

For example, suppose the current board is in the state shown in the following figure.

When the left arrow key (L) is pressed here, the board changes as shown in the following figure.

Hojun has played this game, which does not even have an undo feature, all night for several days, and now he cannot grasp at all how the board will change even after pressing a single key. Write a program that, given the current board and the arrow key to press, prints the board after the rules above are applied.

Input

Eight lines follow, each containing 8 integers separated by spaces. 0 means an empty cell, and every other integer satisfies the form (2^k) ((1≤k≤30)).

The 9th line contains one letter among U, D, L, R. Each means pressing the up, down, left, and right arrow key, respectively.

Output

Print the result of pressing the arrow key on the given board. Print it in the same format as the input board.

Examples2

  1. Example 1

    Input
    4 0 0 8 0 0 0 0
0 0 0 0 0 0 0 0
0 0 2 2 0 0 0 0
2 0 2 8 0 0 0 0
0 0 0 0 0 16 32 64
0 0 2 8 0 16 32 64
0 0 0 0 0 128 256 512
2 0 2 0 0 1024 2048 4096
U
    Expected output
    4 0 4 8 0 32 64 128
4 0 4 2 0 128 256 512
0 0 0 16 0 1024 2048 4096
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

  2. Example 2

    Input
    16 2 4 8 0 0 0 0
2 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0
16 32 8192 16384 32768 65536 0 0
L
    Expected output
    16 2 4 8 0 0 0 0
2 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0
16 32 8192 16384 32768 65536 0 0