호준이는 2048 게임을 발전시킨 2,147,483,648 게임을 하고 있다.</p>

2,147,483,648 게임은 (8 \times 8) 크기의 게임판에서 키보드의 방향키를 통해 (2^k) ((1 \le k \le 30))꼴에 해당하는 정수가 쓰여 있는 타일들을 움직이며 (2,147,483,648(=2^{31}))을 만드는 것이 목적인 게임이다. 이 게임은 방향키가 눌렸을 때 다음과 같은 규칙으로 진행된다.

1. 눌린 방향키와 같은 방향으로 타일들을 벽 끝까지 밀어 넣는다.
2. 만약 밀어넣는 방향으로 같은 수가 두 타일 연속해서 존재한다면 그 두 타일을 합친다. 만약 세 타일 이상 연속해있다면 방향키가 가리키는 쪽의 벽에 가까운 쪽부터 두 개씩 합쳐진다.
3. 한 번의 방향키 입력에 한 타일이 두 번 이상 합쳐지는 경우는 없다.

예를 들어 현재 게임판이 다음 그림과 같은 상태라고 하자.

여기에서 왼쪽 방향키(L)가 눌렸을 때 다음 그림과 같이 게임판이 바뀐다.

호준이는 행동 취소 기능도 없는 이 게임을 며칠 동안 밤새 하다 보니 이젠 키 하나를 눌러도 게임판이 어떻게 바뀔지 전혀 감을 잡지 못하는 상태에 이르렀다. 호준이를 위해 현재의 게임판과 누를 방향키를 주면 위 규칙대로 진행했을 때의 게임판을 출력하는 프로그램을 작성하자.

입력 형식

8줄에 걸쳐 각 줄마다 8개의 정수가 공백으로 구분되어 들어온다. 0은 빈 칸을 의미하고, 나머지 정수는 (2^k) ((1≤k≤30))의 꼴을 만족한다.</p>

9번째 줄에는 U, D, L, R 중 하나의 알파벳이 들어온다. 각각 위쪽, 아래쪽, 왼쪽, 오른쪽 방향키를 누른다는 의미이다.

출력 형식

주어진 게임판에서 방향키를 눌렀을 때의 결과물을 출력하라. 입력으로 주어지는 게임판과 같은 형태로 출력한다.

예제 입력 1

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

예제 출력 1

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

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

예제 출력 2

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